Homework assignments

Problem 3c) on assignment 1 was changed as follows:

• You only need to solve the problem in full detail for n<8.
• Any work beyond this on significant special cases (not just the next few n) will result in extra credit. In order to receive extra credit you must include proofs of optimality and not just give the structure.
• Since there was insufficient time for some people to properly do question 3c) of assignment 1, all marks on this problem will count as bonus marks -- assignment 1 is now worth a total of 60.

• The input consists of n equal numbers. So in 1.a)-c) there there is no difference between average case and worst case behavior, since there is only one case!
• The sentence in parenthesis after 1a) means: repeat the same instructions before line 11 that are to be written before line 5, except that in these instructions every x is to be replaced by y. Here are the MODIFIED ALGORITHMS for 1b) and d).

• Remarks on question 1:
  The sequence of operations are INSERTs and DELETEs -- but since we already know that these can take O(lg n) in the worst case it doesn't make much sense do study those by themselves.
  What we study instead is what the amortized complexity of the FIXUP part of the operations are (since there is at most one FIXUP per INSERT/DELETE, this makes sense).
  So what you are essentially showing is that when we do a sequence of INSERTs and DELETEs, then the amount of time spent on FIXUP's is basically irrelevant -- most of the time is spent on searching down the tree to perform the insert/delete like you would in a regular BST.
• The programming part is to be turned in as follows.
• Here are sample files that you can use to test your program:
  • parameters.dat
  • insert.dat
  • search.dat
  • random.dat
• Here is a ps-file of the perfect hashing example from class that could be useful when you are working on the homework.

• O(log k) in 1c) is not a typo, and with the hint this is doable.
• For 1a) on the third data structure you may assume that you can do PREDECESSOR in time O(log k).
• For 2a) it is more efficient to give a formula for the j-th child of i, that is child(j,i) where j is between 1 and d. The left_child is then the 1st child, and the right_child is the d-th child.
• Hint on problem 3: start with the assumption that states q_1 and q_2 are equivalent -- this may or may not lead to a contradiction.

• The TWO-SIDED-BFS algorithm should start with instruction 0: if s=t then return 0
• The tree in 1c)-e) is a binary tree (the "search" is unnecessary)
• In 3 a) the search is supposed to start at vertex 0. Furthermore, the sum of keys is the sum of the labels on the nodes, that is for the edge (1,3) this sum is 1+3=4.