---------------------------------------- Tutorial notes #3 for 2/26 or 2/27/2007 TA: Stephen McCamant Email: smcc@mit.edu Location: 36-113A or 36-115 ---------------------------------------- By popular demand, I'll be posting the answers to these and other handouts at: http://people.csail.mit.edu/smcc/6.001-sp07/ ---------------------------------------- About project 1 - Start early - You can use the textbook - Put everything in one file - (load "rsa.scm") - Test as you go - Comment out tests once they work - Don't submit late Questions? ---------------------------------------- Helping Louis Based on the repeated squaring example of exponentiation, Louis wrote the following implementation of multiplication in terms of addition: (define (louis-mult a b) (cond ((= a 0) 0) ((< a 0) (- (louis-mult (- a) b))) ((even? a) (+ (louis-mult (/ a 2) b) (louis-mult (/ a 2) b))) (else (+ b (louis-mult (- a 1) b))))) Will this work correctly?;-> Yes, it gives the right answersWhat will its running time be?;-> Theta(a), not Theta(log a) as Louis hopedHow can you fix it?Use let: (define (louis-mult2 a b) (cond ((= a 0) 0) ((< a 0) (- (louis-mult2 (- a) b))) ((even? a) (let ((half-prod (louis-mult2 (/ a 2) b))) (+ half-prod half-prod))) (else (+ b (louis-mult2 (- a 1) b)))))Louis has also been trying to solve quadratic equations, and wrote the following code: (define (solve-quadratic a b c) (let ((discrim (- (* b b) (* 4 a c))) (sqrt (sqrt discrim)) (denom (* 2 a)) (numer1 (+ (- b) sqrt)) (numer2 (- (- b) sqrt))) (list (/ numer1 denom) (/ numer2 denom)))) What error message does Louis get when he tries to run this?;-> Undefined variable "discrim" on line 3What should he have done instead?Nested lets: (define (solve-quadratic a b c) (let ((discrim (- (* b b) (* 4 a c)))) (let ((sqrt (sqrt discrim))) (let ((denom (* 2 a)) (numer1 (+ (- b) sqrt)) (numer2 (- (- b) sqrt))) (list (/ numer1 denom) (/ numer2 denom)))))) Having a variable named "sqrt" is arguably bad style, but it runs fine, because we don't need to use the sqrt procedure inside the scope of the "sqrt" variable.---------------------------------------- Cons, list and append In (cons a b): a can be anything b should be a list (if it isn't, you'll get something weird with a dot in it) The result has one more element than b does. In (list a b): a and b can be anything The result has two elements. In (append a b): a must be a list b must be a list The length of the result is the sum of the lengths of a and b. For each of the following groups of results, I passed the same arguments to cons, list, and append. Which one was which? (1 2);-> (append (list 1) (list 2))((1) 2);-> (cons (list 1) (list 2))((1) (2));-> (list (list 1) (list 2))(3 4);-> (cons 3 (list 4))(3 (4));-> (list 3 (list 4))error;-> (append 3 (list 4))(5 6);-> (list 5 6)(5 . 6);-> (cons 5 6)error;-> (append 5 6)---------------------------------------- Windows Microsoft has hired this year's 6.001 class to re-implement Windows Vista from scratch. To start out, let's design what is obviously the most important data abstraction in Windows, a "window". A window is a rectangle whose sides are parallel to the coordinate axes. From talking with the other developers, we know we'll need to implement the following operations: (window-area w) (window-perimeter w) (empty? w) (overlaps? w1 w2) (contains? w1 w2) (intersection w1 w2) ;; The intersection is the largest ;; window contained in both w1 and w2: +----------+ | w2| | | +-----|-----+ | | |*****| | | |*****| | | |*****| | | +----------+ | | |w1 | +-----------+ (union w1 w2) ;; The union is the smallest window ;; containing both w1 and w2: ******+----------+ ******|********w2| ******|**********| +-----|-----+****| |*****|*****|****| |*****|*****|****| |*****|*****|****| |*****+----------+ |***********|***** |w1*********|***** +-----------+***** Since Prof. Grimson is working on the project too, we can use the following abstractions we saw in lecture Thursday: make-point, point-x, point-y make-seg, start-point, end-point Brainstorm at least 3 different ways we could represent a window: 1.;-> 2 points, lower-left and upper-right corners2.;-> 2 points, any diagonally opposite corners3.;-> lower-left corner, width, heightFor each operation listed above, which representation would make it easiest to write?Area and perimeter are easiest when you have width and height. Intersection and union are easier with the lower-left and upper-right corners. There are other examples.What should we do if the answer to all the above questions wasn't the same?Write more constructors and accessors, in terms of whichever constructors and accessors you've picked as fundamental. For instance, if you represent a window by the corners, you can write window-height that gets the y coordinates of the two corners and subtracts them. Then you can use whatever set of constructors and accessors makes the operation you're writing easiest.---------------------------------------- Cons-end Cons is nice for putting things at the beginning of a list. But suppose we want to put them at the end instead. Let's write a procedure (cons-end l elt) that makes a list like l but with elt at the end. Write cons-end as a recursive procedure:(define (cons-end l e) (if (null? l) (list e) (cons (car l) (cons-end (cdr l) e))))Write cons-end without recursion, using list manipulation procedures we've already seen:(define (cons-end l e) (append l (list e)))What are the time orders of growth of these two implementations?They're both Theta(n). For the recursive version, you can see this because it uses Theta(n) iterations. For the version with append, this is because append takes time linear in the length of its first argument. The version of append we saw in lecture has this property, and the real version does too even though it is a primitive.Now, use cons-end to implement a function "reverse": (reverse (list 1 2 3)) -> (3 2 1)(define (reverse l) (if (null? l) '() (cons-end (reverse (cdr l)) (car l))))What's the running time of this?;-> Theta(n^2)---------------------------------------- A weird kind of cons (define (sqrt-ceil k) (inexact->exact (ceiling (sqrt k)))) (define (tip tier) (+ (* tier (+ tier 1)) 1)) ;; if m, n >= 0, (my-cons m n) >= 1 (define (my-cons m n) (+ (tip (max m n)) (- m) n)) ;; (my-car (my-cons a b)) = a (define (my-car k) (let ((tier (- (sqrt-ceil k) 1))) (+ tier (min (- (tip tier) k) 0)))) ;; (my-cdr (my-cons a b)) = b (define (my-cdr k) (let ((tier (- (sqrt-ceil k) 1))) (- tier (max (- (tip tier) k) 0)))) (define my-null 0) (define my-null? zero?) Take for granted that the procedures shown above have the listed properties for nonnegative arguments. By using them in place of the regular procedures with similar names, we can do lots of list operations. So, why can't we just use these instead of the primitive pairs? (there are several reasons)- We can't implement "pair?" - We can't change the "read" and "print" of the read-eval-print-loop to use them, so lists still print out as numbers - These operations aren't fast enough. (Multiplication and square root take more time when their arguments are big) - (Looking ahead:) Once we see mutation, we won't be able to do that on these pairs.---------------------------------------- Brain teaser: cycles As we saw in recitation, by reusing temporary values you can make lots of weird-looking box and pointer diagrams. Can you make a cycle? A cycle is a series of pairs p_1, p_2, ..., p_k where p_1 points to p2, p2 points to p3, ..., p_k-1 points to p_k, and p_k points back to p_1.No, we can't make cycles yet. If you imagine we assigned a number to each cons pair in sequence as we create it, all of the pointers we have go from a higher-numbered pair to a lower-numbered pair, but to make a cycle, you'd need at least one pointer that went in the opposite direction. Later on, we'll see how to replace the pointers in existing pairs, which will allow us to make cycles.