---------------------------------------- Tutorial notes #2 for 2/20/2007 TA: Stephen McCamant Email: smcc@mit.edu Location: 36-113A or 36-115 ---------------------------------------- Review of asymptotic notation: f(n) is Θ(g(n)) ("big theta") if f(n) and g(n) differ by only a constant factor for sufficiently large n. In other words, if there exist positive k1, k2, and N such that k1*g(n) <= f(n) <= k2*g(n) for n > N ---------------------------------------- Give simple big-theta approximations for the following functions: f1(n) = 0 ;-> Θ(0) f2(n) = 42 ;-> Θ(1) f3(n) = 3*n^2 + 2n + 5 ;-> Θ(n^2) f4(n) = 5*3^(n + 4) ;-> Θ(3^n) f5(n) = n - 2^(-n) ;-> Θ(n) f6(n) = log n + log(log n) ;-> Θ(log n) True or false? - For any f, f(n) is Θ(f(n)) ;-> true - fib(n) is Θ(c^n) for some constant c ;-> true (c =~ 1.618) - n! is Θ(c^n) for some constant c ;-> false (n! >> c^k) - n! is Θ(n^n) ;-> false (n^n >> n!) - If f(n) is Θ(g(n)), then g(n) is Θ(f(n)) ;-> true ---------------------------------------- Review of recursive and iterative definitions Time order of growth by counting basic operations Why running time of recursive Fibonacci is Θ(fib(n)) ---------------------------------------- Examples: digits (define (last-digit n) (remainder n 10)) (define (butlast-digits n) (quotient n 10)) (define (append-digit n d) (+ (* 10 n) d)) ;; (digit-sum 104) -> 5 (define (digit-sum n) (if (< n 10) _____ (+ ______ (________ (___________)))) (define (digit-sum n) (if (< n 10) n (+ (last-digit n) (digit-sum (butlast-digits n))))) Running time of digit-sum is Θ(________) ;-> log(n) The digital root of an integer (also called "casting out nines") is formed by taking the digital sum of the number, and then the digital sum of that, and so on until you have a single digit. (define (digital-root n) ;; fill in using digit-sum ;; The standard answer: (define (digital-root n) (if (< n 10) n (digital-root (digit-sum n)))) ;; This one will actually work for any number that would fit in ;; the computer's memory: (define (digital-root n) (digit-sum (digit-sum (digit-sum (digit-sum n))))) ;(reverse-digits 617) -> 716 ;(reverse-digits 5) -> 5 ;(reverse-digits 42) -> 24 ;(reverse-digits 31415) -> 51413 (define (reverse-digits n) ;; fill in (define (reverse-digits-help from to) (if (= from 0) to (reverse-digits-help (butlast-digits from) (append-digit to (last-digit from))))) (define (reverse-digits n) (reverse-digits-help n 0)) Examples: cube roots (define (cube n) (* n n n)) ;; true if i is the cube root of n, ;; rounding down (define (try-cube-root i n) (and (<= (cube i) n) (< n (cube (+ i 1))))) (define (slow-cbrt-help _______) (if __________ __________ (slow-cbrt-help _____________))) (define (slow-cube-root n) (slow-cbrt-help _____________)) (define (slow-cbrt-help i n) (if (try-cube-root i n) i (slow-cbrt-help (+ i 1) n))) (define (slow-cube-root n) (slow-cbrt-help 0 n)) Running time is Θ(_____________) ;-> cbrt(n) Faster idea: binary search Running time is Θ(_____________) ;-> log(n) (define (fast-cbrt-help i j n) (cond ((try-cube-root i n) i) ((try-cube-root j n) j) (else (subdivide i (quotient (+ i j) 2) j n)))) (define (subdivide i m j n) (if (> (cube m) n) (fast-cbrt-help i m n) (fast-cbrt-help m j n))) (define (fast-cube-root n) (fast-cbrt-help 0 n n)) ---------------------------------------- Helping Louis Based on the repeated squaring example of exponentiation, Louis wrote the following implementation of multiplication in terms of addition: (define (fast-mult a b) (cond ((= a 0) 0) ((< a 0) (- (fast-mult (- a) b))) ((even? a) (+ (fast-mult (/ a 2) b) (fast-mult (/ a 2) b))) (else (+ b (fast-mult (- a 1) b))))) Will this work correctly? What will its running time be? How can you fix it? We'll come back to this next week, so stay tuned Pythagorean triples A Pythagorean triple is three integers (a, b, c) such that a^2 + b^2 = c^2. We'd like to count all such triples with 0 < a,b,c <= max. (define (pythag-triple? a b c) (= (+ (* a a) (* b b)) (* c c))) (define (try-triple a b c) (if (pythag-triple? a b c) 1 0)) (define (try-c a b c) (if (= c 0) 0 (+ (try-triple a b c) (try-c a b (- c 1))))) (define (try-b a b max) (if (= b 0) 0 (+ (try-c a b max) (try-b a (- b 1) max)))) (define (try-a a max) (if (= a 0) 0 (+ (try-b a max max) (try-a (- a 1) max)))) (define (count-triples max) (try-a max max)) The running time is Θ(_____________) ;-> Θ(n^3) How can we make this go faster? There are many possibilities. You could only check for where cases a < b, then count each one as two. This would increase the speed by about a factor of 2. Rather than using a loop in try-c, you could compute sqrt(a^2 + b^2), and see whether it's an integer in the right range. This would make it Θ(n^2).