Each homework question is out of a total of ten points.

Question 1 - Erran
1pt  - part a
3pts - part b
3pts - part c
3pts - part d

Common Mistakes:
- Note that the problem referred to a MIN-heap, not a MAX-heap

Question 2 - Erran
6pts - algorithm
2pts - recurrence relation
2pts - recurrence solution

Common Mistakes:
- Note that isomorphism implies similar tree structure/node placement,
  not that nodes must be in the same places and have teh same VALUES
- If you use the DFS algorithm, you must first put the tree in canonical
  form. Two trees can be isomorphic even if they are not identical in
  structure.
- For the DQ algorithm, note that if you place your second recursive call
  within the if statement of the first recursive call, you can save
  yourself time.  This format will enable you to always do at most 3 calls
  and not 4.  See solution for more information.

Question 3 - Kai
6pts - algorithm
2pts - recurrence relation
2pts - recurrence solution

Common Mistakes:
-Points were taken off if the base case of the correct algorithm were not 
 mentioned.
-Missing proof of runtime. You need to show that the algorithm is correct.

Question 4 - Erran
3pts - representing and merging the skyline
3pts - algorithm
2pts - recurrence relation
2pts - recurrence solution
5pts - extra credit for non-D/Q solution, which still runs in O(nlg(n)).

Common Mistakes:
- The key to this problem was getting the merge algorithm correct.  You
  must go point by point along the x-axis of the 'sub-skylines' to merge
  correctly.  People who did not explain their merge algorithm or 
  specified an incorrect algorithnm lost points.

Question 5 - Kai
6pts - part a
2pts - part b
2pts - part c

Common Mistakes:
-Incomplete proof.  Missing proof of the base case, or only proof the base
 case.
-For part a, simply claim that sorting the first 2/3, last 2/3 and then the 
 first 2/3 of the array will end up with a fully sorted array.
-Incorrect recurrence relation.

Question 6 - Erran
4pts - skyline analogy
4pts - take solution from skyline
2pts - correct runtime analysis
5pts - extra credit for non-D/Q solution, which still runs in O(nlg(n)).

Common Mistakes:
- Simply alluding to the skylines problem without proper explanation was
  not a sufficient answer

Question 7 - Kai
2pts - part a: naive n^2 algorithm or something else correct
3pts - part b: lower bound
5pts - part c: efficient algorithm
 
Common Mistakes:
-Most people got part a correct.
-Points were taken off if you simply mention the quick sort algorithm
 without actually explaining how to apply it to this specific problem. 
-Have a correct efficient algorithm but without the worst case running 
 time analysis.