Solution to Microsquishy vs. Mashmatica

WARNING: You should seriously try to answer this question before looking at the solution -- it's just a good study skill. Also, some answers on this page may be more brief than you would want to put down in an actual exam. If you want any type of partial credit, you should write more than just the solution.

1. No. They both run in O(n) time.
2. We wish to prove that f is equivalent to new-f
   Proof by Induction on the Structure of Lists
   Base Case

From the left:

(f g1 g2 empty)
(map g1 (map g2 empty))
(map g1 empty)
empty

From the Right:

(new-f g1 g2 empty)
(map (lambda (i) (g1 (g2 i))) empty)
empty

Inductive Step

Assume that (f g1 g2 x) = (new-f g1 g2 x)
Prove that (f g1 g2 (cons v x)) = (new-f g1 g2 (cons v x))

From the left:

(f g1 g2 (cons v x))
(map g1 (map g2 (cons v x)))
(map g1 (cons (g2 v) (map g2 x)))
(cons (g1 (g2 v)) (map g1 (map g2 x)))
(cons (g1 (g2 v)) (f g1 g2 x))
(cons (g1 (g2 v)) (new-f g1 g2 x))      [by IH]

From the Right:

(new-f g1 g2 (cons v x))
(map (method (i) (g1 (g2 i))) (cons v x))
(cons ((method (i) (g1 (g2 i))) v)
      (map (method (i) (g1 (g2 i))) x))
(cons (g1 (g2 v)) (new-f g1 g2 x))

Thus we have proven that f is equivalent to new-f for all list.
QED

3. Consider:

   (define (foo x) (echo "foo") (+ 1 x))
   (define (bar x) (echo "bar") (* x x))

   A call to (f foo bar '(1 2 3)) is not the same as (new-f foo bar '(1 2 3)) since the order in which the "foo"s and "bar"s are displayed is different.

Question

Return to CS 212 Final - Spring 1998