6.001 Recitation 5: More Orders of GrowthRI: Gerald Dalley, [email protected] Feb 2007Announcements / Notes• Deity and Lisp– http://www.gnu.org/fun/jokes/eternal-flame.html (lyrics)– http://www.prometheus-music.com/audio/eternalflame.mp3 (music)– http://xkcd.com/c224.html (last Friday’s xkcd comic)• The “One λ” (useless brownie points for interpreting the inscription!)• Documentation Resources– DrScheme’s help system– http://www.drscheme.org (when the webserver is working)– Tutor: http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/index.html• Personal edification: last Friday’s prime? problemlet Special Form: (let bindings body)Binds the given bindings for the duration of the body. The bindings is a list of (name value) pairs. Thebody consists of one or more expressions which are evaluated in order and the value of last is returned.Desugaring example:(let ((a 10)(b 20))(+ a b))is exactly equivalent to:((lambda (a b)(+ a b))10 20)This will be handy in project 1. C++ programmers: Scheme’s way of making const local variables (laterwe’ll talk ab out modifying the values).1How to identify recursive and iterative processesBy staring at code (rules of thumb):Recursive Iterative ProcessProcess (tail recursive)Is there a RECURSIVE CALL?(it may be indirect)Is there something “wrapped” around the recursive call?(deferred operations)Is there an extra variable that stores theINTERMEDIATE RESULT?Is there a COUNTER variable?Are there helper functions(often needed to keep track of these other variables)By putting an example through the substitution model:What is the ”shape” of the rewrites?By analysis of space and time, i.e. order of growth (the real way):Space – width of the substitution model (characters haveto be stored s ome where... )Time – length of substitutions (each simplification/rewritetakes 1 unit of time)Analysis ProblemConsider the following problem:( define ( bar a b)( ba r- he lp er 0 a b ))( define ( b ar -h el pe r c a b )( if ( > a b )c( ba r- he lp er (+ c a) (+ a 1) b )))What’s the order of growth in space A and time A ?Is it recursive or iterative? AWrite the other:( define ( b ar- re c a b)2Cubic RootsWe are now going to create and analyze some methods of finding the zeros of a cubic equation, i.e. given a,b, c, and d find values of x for which ax3+ bx2+ cx + d = 0.Assume we’ve been supplied with two guesses for x and the coefficients. If either guess gives a solution thatis close enough to zero, return the guess. If not, then you have lots of choices. One is to move each guesstowards the other by a slight amount and continue, another is to split the domain in two and try both halves(e.g. if the guesses are g1and g2, then try g1and (g1+ g2)/2 and (g1+ g2)/2 and g2.In class, we ’ll now go through the process of designing the above two versions of find-cubic-root, discussingmodularity, orders of growth, recursion vs. iteration, accuracy, and other fun concepts. Your instructor’ssolution will be posted at http://people.csail.mit.edu/dalleyg/6.001/SP2007/index.html.; ;; fi n d -c u b ic- r o ot solu tio ns ...3Challenge Problem;; C ha lle nge P rob le m :;; a) Is th is f un ct i on ite rat iv e or r ec u rs ive ?;; b) Wh at is its o r der - o f- g r owt h in t ime ? sp ac e ?;; c) Wh at does this th ing ac tu a ll y do ( hint : 1 8. 02 )?;; d) Rew r it e as re cur si v e / i t er a ti v e ( w hich ever this is not ).;; e) Wh at is the or der of growth for your new ve rsi on in time ? s pa ce ?( define ( baz n)( d efi ne ( qux a b c)( if ( > a b )c( qux (+ a 1)b(( if ( even ? a ) - +)c (/ (- (* a 2) 1 )) ))) )( qux 1 n 0))46.001 Recitation 5: More Orders of GrowthRI: Gerald Dalley, [email protected] Feb 2007Announcements / Notes• Deity and Lisp– http://www.gnu.org/fun/jokes/eternal-flame.html (lyrics)– http://www.prometheus-music.com/audio/eternalflame.mp3 (music)– http://xkcd.com/c224.html (last Friday’s xkcd comic)• The “One λ” (useless brownie points for interpreting the inscription!)• Documentation Re sources– DrScheme’s help system– http://www.drscheme.org (when the webserver is working)– Tutor: http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/index.html• Personal edification: last Friday’s prime? problemlet Special Form: (let bindings body)Binds the given bindings for the duration of the body. The bindings is a list of (name value) pairs. Thebody consists of one or more expressions which are evaluated in order and the value of last is returned.Desugaring example:(let ((a 10)(b 20))(+ a b))is exactly equivalent to:((lambda (a b)(+ a b))10 20)This will be handy in project 1. C++ programmers: Scheme’s way of making const local variables (laterwe’ll talk ab out modifying the values).5How to identify recursive and iterative processesBy staring at code (rules of thumb):Recursive Iterative ProcessProcess (tail recursive)Is there a RECURSIVE CALL? yes yes(it may be indirect)Is there something “wrapped” around the recursive call?(deferred operations)yes noIs there an extra variable that stores the no oftenINTERMEDIATE RESULT?Is there a COUNTER variable? yes yesAre there helper functions rarely often(often needed to keep track of these other variables)By putting an example through the substitution model:What is the ”shape” of the rewrites? wide (deferred ops)and long (recursivecalls)narrow (nodeferred ops,doesn’t get widerwith “larger”inputs) and long(recursive calls)By analysis of space and time, i.e. order of growth (the real way):Space – width of the substitution model (characters haveto be stored s ome where... )not Θ(1) Θ(1)Time – length of substitutions (each simplification/rewritetakes 1 unit of time)anything anything, same asrecursiveAnalysis ProblemConsider the following problem:( define ( bar a b)( ba r- he lp er 0 a b ))( define ( b ar -h el pe r c a b )( if ( > a b )c( ba r- he lp er (+ c a) (+ a 1) b )))What’s the order of growth in space Θ(1) and time Θ(a) ?Is it recursive or iterative? iterativeWrite the other:( define ( b ar- re c a b)( if ( < a b ) 0(+ a ( bar -r ec (+ a 1) b ))))6Cubic RootsWe are now going to create and analyze some methods of finding the zeros of a cubic equation, i.e. given a,b, c, and d find values of x for which ax3+ bx2+ cx + d = 0.Assume we’ve been supplied with two guesses for x and the coefficients. If either guess gives a solution thatis close enough to zero, return the guess. If not,
View Full Document
Unlocking...