i have a 2 small program due in a few hrs:
1. Write a procedure that computes elements of pascals triangle by means of a recursive proces. This must be written in Lisp, and show an inductive proof.
2. define (*a b)
(if (=b 0)
( +a (*a (-b 1)))))
This algorithm takes a number of steps that is linearin b. Suppose we include , together with addition, operations *double*, which doubles an integer and *halve,* which divides an ( even) integer by 2. Using these , design a multiplication procedure analagous to **fast-expt** that uses a logarithmic # of steps. SHow the code and inductive proof.
note: fast-exp procedure
(define ( fast-expt b n)
( cond (( = n 0) 1)
(( even? n) (square ( fast-expt b ( / n 2))))
( else ( * b ( fast-expt b ( - n 1 ))))))
1 txt file is sufficient
a text file application