6.001 Tutorial 2Lambdas ReviewSubstitution ModelRecursion and IterationProblemsGeneral ProblemsBiggie Size6.001 Tutorial 2Gerald Dalley14/15 February 2005Web location: http://people.csail.mit.edu/ ~dalleyg/6.001/tutorial2.htmlLambdas Review What do lambdas return? Is the body in a lambda expression evaluated?Substitution Model What is the substitution model? According to the substitution model, what happens when a combination is evaluated? 1)2)3)Recursion and Iteration What is a recursive procedure? What are the 3 parts to a recursive procedure?1)2)3) What are the design steps for a recursive procedure? What is a deferred operation? What is an iterative process? Give an example of a procedure that evokes an iterative process. What is a recursive process?ProblemsGeneral Problems Implement using inc and dec. Recursive or iterative? (define (add x y) Time order of growth:Space order of growth: Write a recursive slow-mul, which multiplies two numbers by repeated addition. It need not handle negative numbers, though a simple extension would allow them.(define (slow-mul x y) Time order of growth:Space order of growth: Rewrite slow-mul as an iterative procedure.(define (slow-mul-iter x y) Time order of growth:Space order of growth: What is the order of growth of prime? if sqrt takes Θ(1) time? (define mod (lambda (x y) (if (< x y) x (mod (- x y) y))))(define divisible? (lambda (x y) (= (mod x y) 0))) (define prime? (lambda (p) (define helper (lambda (n) (cond ((> n (sqrt p)) #t) ((divisible? p n) #f) (else (helper (+ n 1)))))) (helper 2)))Biggie SizeSuppose we're designing an point-of-sale andorder-tracking system for Wendy's†. Luckily theÜber-Qwuick drive through supports only 4options: Classic Single Combo (hamburger withone patty), Classic Double With Cheese Combo(2 patties), and Classic Triple with CheeseCombo (3 patties), Avant-Garde Quadruple withGuacamole Combo (4 patties). We shall encodethese combos as 1, 2, 3, and 4 respectively.Each meal can be biggie-sized to acquire alarger box of fries and drink. A biggie-sizedcombo is represented by 5, 6, 7, and 8respectively. †6.001 and MIT do not endorse and are not affiliated with Wendy'sin any way. They merely capitalize on the pleasant way "biggie-size" rolls off the tongue. Write a procedure named biggie-sizewhich when given a regular combo returns abiggie-sized version. Write a procedure named unbiggie-sizewhich when given a biggie-sized comboreturns a non-biggie-sized version. Write a procedure named biggie-size?which when given a combo, returns true if thecombo has been biggie-sized and falseotherwise. Write a procedure named combo-pricewhich takes a combo and returns the price of thecombo. Each patty costs $1.17, and a biggie-sized version costs $.50 extra overall. An order is a collection of combos. We'llencode an order as each digit representing acombo. For example, the order 237 represents aDouble, Triple, and biggie-sized Triple. Writea procedure named empty-order which takesno arguments and returns an empty order. Write a procedure named add-to-orderwhich takes an order and a combo and returns anew order which contains the contents of the oldorder and the new combo. For example, (add-to-order 1 2) → 12. Write a procedure named order-sizewhich takes an order and returns the number ofcombos in the order. For example, (order-size 237) → 3. You may find quotient(integer division) useful. Write a procedure named order-costwhich takes an order and returns the total cost ofall the combos. In addition to quotient, youmay find remainder (computes remainder ofdivision)
View Full Document
Unlocking...