### PPL (201-1289101)

#### Solution to HW1

```;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Question 1. Call: (targ1 b n)
;;
;; This version of exponentiation is iterative and takes time logarithmic in n
;;

(define (targ1 b n)
(exp-log-iter 1 b n ))

(define (exp-log-iter a b n)
(cond ((= n 0) a)
((even? n)
(exp-log-iter a (* b b) (/ n 2)))
(else (exp-log-iter (* a b) b (- n 1)))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Question 2. Transformation: p' = pp + qq; q' = qq + 2pq. Call: (fib n)
;;
;; This version of fib is iterative and takes time logarithmic in n.
;;

(define (fib n)
(fib_iter 1 0 0 1 n))

(define (fib_iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib_iter a
b
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))
(/ count 2)))
(else (fib_iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Question 3. Product & factorial
;;

;; recursive version of product

(define (product-r term a next b)
(if (< b a)
1
(* (term a) (product-r term (next a) next b))))

;; iterative version of product

(define (product-i term a next b)
(define (iter a result)
(if (< b a)
result
(iter (next a) (* result (term a)))))
(iter a 1))

;; Using product to compute factorial:

(define (identity x) x)

(define (fact-prod-i n)
(product-i identity 1 1+ n))

(define (fact-prod-r n)
(product-r identity 1 1+ n))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Question 4. Accumulate
;;
;; Accumulate is a generalization of sum and product.

;; iterative  accumulate

(define (accumulate-i combiner null-value term a next b)
(define (acc-iter a result)
(if (< b a)
result
(acc-iter (next a) (combiner result (term a)))))
(acc-iter a null-value))

;; recursive accumulate

(define (accumulate-r combiner null-value term a next b)
(if (< b a)
null-value
(combiner (term a)
(accumulate-r combiner null-value term (next a) next b))))

;; Using accumulate to redefine sum

(define (sum-acc-i term a next b)
(accumulate-i + 0 term a next b))

(define (sum-acc-r term a next b)
(accumulate-r + 0 term a next b))

;; Using accumulate to redefine product

(define (prod-acc-i term a next b)
(accumulate-i * 1 term a next b))

(define (prod-acc-r term a next b)
(accumulate-r * 1 term a next b))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; That's all folks
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
```