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

Time order of growth by counting basic

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)
          (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 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
       (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)))
         (+ 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
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
This would make it Θ(n^2).