Computational Modeling
Fall 2008

For today, you should:

1) read your swappy book and write a summary/commentary

2) read Chapter 3 and think about what exercises you want to do

   (we'll start on Tuesday)


Today:

1) quiz notes: order of growth analysis

2) finish your Chapter 2, if you haven't

3) work on Chapter 3



For next time you should:

1) work on Chapter 3, aim to finish next Tuesday

2) clean up the wiki, and
   get ready for book reports: identifying themes


Q: should we do 1-2 more rounds with the swappy books?




Quiz notes
----------

1) The wikipedia page says

   O(n!) = O(n^n)

   If we interpret O(f) to be the set of functions that grow
   no faster than f, then this relationship claims that
   O(n!) and O(n^n) are the same set, which is FALSE.

   Actually, n! is in O(n^n), but n^n is not in O(n!).

   In other words, O(n!) is a subset of O(n^n)

   Proof sketch: write out n! and n^n as products and characterize
   their ratio.

   Corollary: O(n log n) =? O(n!)


2) Lookup in a BST is O(h), where h is the height of the tree.

   IF the tree is reasonably balanced, then h is O(log n),
   so lookup is O(log n).

   BUT in the worst case, h is O(n) and lookup is O(n).

   Which is the motivation for red-black trees.


3) A correct implementation of mergesort is O(n log n).

   Proof sketch:

   a) The number of levels of recursion is O(log n).

   b) The total amount of work at each level is O(n).

   HOWEVER: this implementation is broken, because merge is O(n^2)
   (because pop(0) is O(n))

def merge(t1, t2):
    ts = []
    while t1 and t2:
        t = min(t1, t2)
        ts.append(t.pop(0))
        
    ts.extend(t1)
    ts.extend(t2)
    return ts

   (BTW, I should have renamed "t" something like "winner")

   a) So what's the order of growth for the broken one?

   b) Write a correct version of merge.