6.001, Spring 2006—Recitation 5 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsSpring 2006Recitation 5More Orders of GrowthSpecial Forms1. begin - (begin expr1 expr2 ... exprn)First evalutate expr1, then expr2, and so on. The value of the begin statement is the valueof the last expression in the sequence.2. let - (let ((name1 val1) (name2 val2) ... (namen valn)) body)Syntactic sugar for the following:((lambda (name1 name2 ... namen) body) val1 val2 ... valn).Used to bind additional names inside a procedure body.Typical Orders of Growth: Review• Θ(1) - Constant growth. Simple, non-looping, non-decomposable operations have constantgrowth.• Θ(log n) - Logarithmic growth. At each iteration, the problem size is scaled down by aconstant amount: (call-again (/ n c)).• Θ(n) - Linear growth. At each iteration, the problem size is decremented by a constantamount: (call-again (- n c)).• Θ(n log n) - Nifty growth. Nice recursive solution to normally Θ(n2) problem.• Θ(n2) - Quadratic growth. Computing correspondence between a set of n things, or doingsomething of cost n to all n things both result in quadratic growth.• Θ(2n) - Exponential growth. Really bad. Searching all possibilities usually results in expo-nential growth.Problems1. (define (fact n)(if (= n 0)1(* n (fact (- n 1)))))Running time? Space?6.001, Spring 2006—Recitation 5 22. (define (find-e n)(if (= n 0)1.(+ (/ (fact n)) (find-e (- n 1)))))Running time? Space?3. Assume you have a procedure (divisible? n x) which returns #t if n is divisible by x. Itruns in O(n) time and O(1) space. Write a procedure prime? which takes a number andreturns #t if it’s prime and #f otherwise. You’ll want to use a helper procedure.Running time? Space?4. Write an iterative version of find-e.Running time? Space?5. Write a version of sum-by-halves (from your problem set) that only computes the midpointbetween a and b once per iteration.Running time?
View Full Document
Unlocking...