The induction stuff:
Most got it right but still many people are struggling with the formalities (like missing the base step for n=0 or n=1, and going from n to n+1). The idea of induction is that you prove a statement to be true by showing that :
1. Some base statement is true; usually for n=0 or n=1, or in some cases n being some small integer like 2 or 5.
2. You assume that S(n) is true, and based on this taken as a fact you
3. prove that S(n+1) is true.
The steps 2 and 3 indicate that "IF" the statement is true for some index n "THEN" it is true for the next index n+1. So if it is true for some base n=1 (step 1), then it follows that it is true for n=2, and from n=2 it follows it is also true for n=3, and then for n=4, etc. Thus true for all n. In a way it is like having an (infinite) list of statements S(1), S(2), S(3)..... and you show that if something on the list is true then the next thing on the list is also true. So if the first thing on the list is proven true (base statement) then all of them are. The key is to do a base statement (which does not always need to start from 0 or from 1 - it can be 2 or something else- but it usually does). Then you need to assume S(n) and using this assumption show that S(n+1) is true. In a way you have to express S(n+1) in terms of S(n) and then substitute for S(n) the assumed fact, and show that the whole substitute amounts to what you are trying to prove.
Common mistakes are to assume that S(k) is true and then try to show S(n) be true without having any way to relate k to n.
As an example: prove that 20+21+22+23+...+2h is equal to 2h+1-1. The statement that we are trying to prove is
S(n): 20+21+22+23+...+2n =2n+1-1
For n=0 we have S(0): 20=1=2-1=20+1-1 which is correct and showing that the form which S(n) takes for n=0 : 20=20+1-1 is indeed true.
Now we assume that S(n): 20+21+22+23+...+2n =2n+1-1 is true.
Next we have to show that S(n+1) is also true based on S(n). So here we go:
We have to show that S(n+1): 20+21+22+23+...+2n+1 =2n+2-1. (**)
We observe that the first part 20+21+22+23+...+2n+1 can be transformed using the assumption 20+21+22+23+...+2n =2n+1-1 to the following form:
20+21+22+23+...+2n+1 = 2n+1-1 + 2n+1 so all that we have to do to show that
(**) is valid is to show that 2n+1-1 + 2n+1 =2n+2-1 which is done as follows:
2n+1-1 + 2n+1 =2*2n+1 -1 = 2n+2 -1 , done!
The other part with the binary search is similar:
1. Assume a tree with 1 node. There is no searching to do, it is only one comparison to give an answer.
2. Assume that for a tree with n nodes the time in number of divisions is log(n).
3. For n+1 nodes, after the first division we will end up with two parts one of which will be exactly the same as one of the two that you would get if you had n elements and the other will contain one more than in the case with n elements. If your search directs you in the same section then your time will be as before <=log(n). If it directs you in the other section then you will need the same as before and perhaps one more, so again <=log(n)+1 which is <=(log(n+1). Or, you could simply say that the time to search a tree t(n+1) is 1+time to search t(n) in the worst case so t(n+1) <=1+(tn)=1+log(n)<=log(n+1).
The Towers problem is in the book as I mentioned in class.
The problem with the polynomial hashing was a disaster. I assume that you all know that a polynomion looks like this:
axn + bxn-1 +...+kx0 , yet I did not see any polynomion in the answer. The short answer is that a number like 2437 would be hashed as2*23+4*22 +3*21+ 7*20 if we use a base 2 polynomion. It is in your book look it up if you have not already.
The difference with open addressing and separate chaining is that the first is a simple structure for primitive data whereas the second involves bins that are structured themselves as either lists or trees or heaps etc.