Last update: July 20, 5:00PM.

Warning: Dan may not be quick to answer email this weekend. Start early.

Note: You are responsible for reading and understanding the course policy on academic integrity.

1. Describe an initial arrangement of n elements in an array such that when build-heap is called on that array it exhibits its worst-case behavior. Argue why your arrangement is at least as bad as any other.
   
   
2. Suppose we have n total elements divided into m sorted lists. Explain how to produce a single sorted list of all n elements in time O(n log m). Hints: Keep the lists in a heap as your alogorithm runs. Remove list items as necessary.
   
   
3. How could we lower the worst-case time for a hash table with chaining to O(log n) where n is the number of elements in the table? Why don't we care? [Short question]
   
   
4. Exercise 12.3-1 on page 231. [Another short question]
   
   
5. Exercise 12.4-1 on page 240.
   
   
6. In red-black trees, insertion is O(log n). It takes O(log n) time to find the right place to insert and O(log n) time to rebalance the tree. Finding the right place is Omega(log n) since we always insert at a leaf, so we can't provide any tighter analysis there. But it turns out that the amortized time for rebalancing is O(1). That is, over a sequence of m insertions, the total time spent on rebalancing is O(m). Ignoring deletes (the claim is still true, but deletes are just more cases to consider), give an amortized analysis that proves the O(1) claim above.
   
   Hint: Look at the cases for insert. They are all constant time except one which recurs. Decide where you can store chips so that there is always enough saved up to recur as much as necessary. Hint for the hint: what decreases in the case that recurs?
   
   
7. In the Kevin Bacon game, one attempts to connect an actor to Kevin Bacon through a series of actors who were in movies together. For example, "A was in movie x with B who was in movie y with C who was in movie z with (melodramatic pause) Kevin Bacon". Do not ask Dan for a real example; he is very bad at this game. In a simpler version of the game, we only want a boolean: true if Kevin Bacon is connected to an actor by some sequence and false otherwise. According to many people the following algorithm suffices:

   boolean KevinBacon(Actor a) {
        return true;
   }

   I am a bit more skeptical. Describe a program that efficiently handles the following inputs:
   • void Together(Actor a, Actor b) informs the program that a and b have been in a movie together.
   • boolean KevinBacon(Actor c) returns true iff given all previous information given to the program, there is a sequence from c to Kevin Bacon.