1.(a) Total: 3 marks
--------------------
Well done.

-1 for not stating the condition that x is not same as y

-1 for not stating that the probability is over random choice of hash
   function h



1.(b) Total: 7 marks
--------------------
Not very well done.

Note that the following statement is false: Let H be a universal class of
hash functions. For all x and i, if we pick h uniformly at random from H,
then the probability that h(x)=i is 1/m.  

Those who tried to use the above statement got at most 2 marks. If you
can't see it, try to decide if it holds for the class H from lecture.

Marking scheme:
1 mark for any attempt to prove the claim.
2 marks for attempting to disprove the claim with incorrect argument. 

If you used the universal class H that was introduced in lecture probably
you got 4 or more marks. I gave 4 marks if your argument works for
specific h and h' from H. You received full marks if your argument works
for any h and h' that are randomly chosen.

Note that calculating the probability that h=h' does not help much, since
it simply gives a lower bound for the probability of h(x)=h'(x). (Because
h(x)=h'(x) can happen even if h and h' are distinct.)


2.  Total: 10 marks
----------------------
If they do not mention anything about x or their analysis does not invlude
it (the do the same analysis as in the book starting from 0) then they get
at most 3.

If they additionaly mention something about x but just say that it changes
the cost without specifying  or explaining how, then they may get one more
(total 4 at most only if their analysis is very good)

Some gave the trivial bound of O(mk) they get 2

Some gave lower bounds omega(k) of one specific operation in the case
where only one insertion may happen and all the k bits change. (they get 0
for that)

For small typos in the agrregate analysis
(cost(from 0 to m+x) - cost(from 0 to x) some people did not
calculate this exaclty right (they forgot to add x at particular
places...) they lost 1 point.







3.(a) Total: 6 marks
----------------------
This question was not very well done.

1 mark for methods that do not ensure n/m <= 3.

Many of you correctly used dynamic arrays as hash tables. 
-2 if you did not clearly explain what happens when a new table of larger
size is created. You need to rehash everything using an *new* has
function. Otherwise no elements will be allocated to the new slots. 

-1 if you created a new table whenever an element is inserted into a slot
with 3 elements. This is very inefficient since a new table may have to be
created after every 3 INSERTs.

You may have lost a couple more marks depending on the clarity of your
description.



3.(b) Total: 4 marks
---------------------
Poorly done.

I looked for a "reasonable" argument.

If your method in (a) required a new table whenever a slot has to have 4
elements, then the amortized cost is O(k), where k is the number of
operations in a sequence. If you claimed that the amortized cost is O(1),
I gave 1 mark here.

I gave 2 or 3 marks if you gave a reasonable argument, such as correctly
identifying the costs for each operation, etc.