----------------------------------------
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 answers
What will its running time be?
;-> Theta(a), not Theta(log a) as Louis hoped
How 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 3
What 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 corners
2. ;-> 2 points, any diagonally opposite corners
3. ;-> lower-left corner, width, height
For 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.