- Q: Will formulas for summations such as the following be provided?
1+M+M^2+M^3+...+M^k ?
A: IF a question

*requires*that you use a summation formula, it will be provided in the question. However, for many of the questions, you can reason-out the answer without having to use such a formula. - Q: Will we be given the formula about the height of a binary tree?
A: No. I will expect you to know that a binary tree with n nodes has height proportional to log(n) (when the tree is as short and fat as possible). (Note: that is log base 2.)

- Q: Will you give the Birthday Paradox formula?
A: No. Any question on this will be similar to the one on the sample exam (but not identical).

- Q: Will you give the formulas for hashing?
A: No. I do not expect you need to plug into any of those formulas to find answers. HOWEVER, some questions are related to those formulas, and I expect you know how they are derived, so that you can reason out the answers (for the ones we did in detail in class.)

- Q: Regarding Huffman Coding. Let's say we had the
following values and frequencies: A=5, B=3, C=2, D=4. We would group B and
C and add 5 to the list so we get: A=5, D=4, and 5 (from grouping B and C).
What value would I group with D? Do i use the 5 from B and C or A?
A: If such a situation comes up in the exam, the question would tell you which one to use. IF the question did not tell you, you could choose either. IF this means two answers are now correct, then both will be marked correct.

- Q: Can we use a calculator?
A: No calculators allowed. I have tried to keep the math manageable.

- Q: On notes H2 we truncate by discarding the first digits, but on H2.1
we sometimes discarded the last digits. Which should I use on the final?
A: If the question does not tell you which way to truncate, then you must discard the first digits, consistent with the examples on H2, and with only the FIRST truncation example on H2.1. where h(382650) = 50 and h(125) = 25.

Note that when you are doing folding, and you need to truncate, you should always truncate by discarding the first digits (as on H2), unless the question specifically asks you to truncate the other way. - Q: Is each multiple-choice question worth one mark, or will each question have
a different mark assigned to them?
A: One mark each for all questions.

- Q: For Lab09, question 3, how did you calculate the insertion collisions and get the load factor?
A:

For Linear Probe:

9 gets slot 9.

61 gets slot 10.

95 tries 10 (collision), 9 (collision), gets slot 8.

78 tries slot 10 (collision), 9 (collision), 8 (collision), gets slot 7

44 tries slot 10 (collision), 9 (collision), 8 (collision), 7 (collision), gets slot 6

That's a total of 9 collisions.

For Double Hashing:

9 gets slot 9.

61 gets slot 10.

95 tries 10 (collision), (Note 95/17=5) gets slot 5

78 tries slot 10 (collision), (Note 78/17=4) slot 6

44 tries slot 10 (collision), (Note 44/17=2) slot 8

That's a total of 3 collisions.

The load factor for both is 5/17=29%.

- Q: A Sample Question says: "For unsuccessfully retrieving a record (with key K) with
separate chaining, the number of comparisons between K and other keys is,
in the worse case:" And the answer is: (A) N, the number of keys in the table.

On H9 for unsuccessful searching of the Chain method, the case is the load factor (N/M). This conflicts with the answer to the Sample Question.A: The Analysis of Hashing in the notes pages H9-H12 finds the average number of probes. But the Sample Question asks for the worst case. In the worst case, all the keys in the table would happen to be hanging off the table slot of interest, so you would have to check every key in order to be sure the one you are looking for is not there.

Also note that for chaining questions on the final, we will assume the entries on the chains are lists in no particular order (i.e., we cannot speed up the search by doing a binary search on a chain.) - Q: Are recurrence relations on the final?
A: No, they are not necessary for any question on the final.

- Q: In the class notes I see that a root may have between 1 and m-1 keys.
Is this also the case for a leaf node? Or should I assume that a leaf node
can have between m/2-1 and m-1 keys? (note there should be ceiling brackets around m/2).
A: The root is the only special case. All other nodes, including leafs, must be at least half full. The only situation where a leaf can have between 1 and m-1 keys is when the B-Tree consists of a single node, because then the root IS a leaf.

- Q: Are we allowed to ask you questions during the final?
A: No, we don't answer questions. Note that there is at least one typo on the exam (duplicated word). Just ignore such typos. If you think one of them is going to affect your answer, then leave a note about it on the cover page of your exam questions.

- Q: For lab10, why does the 16 (pivot) end up at the end of the array after the
first call to partition?
A: I posted a program qsort1.c which has printf statements showing the pivot and modified array (subsection) and i,j values after each call to partition. In case you aren't in a position to run it, I am including the output below. It shows that for/after the first call to partition,

pivot is: 16 modified array is: 1, 2, 3, 4, 6, 5, 11, 9, 24, 27, 16, i,j are 8,7

Here is the full output for the whole quicksort:

a.out 1 2 3 4 6 16 27 24 9 11 5 Original: 1, 2, 3, 4, 6, 16, 27, 24, 9, 11, 5, Partition pivot 16 starts: Partition from 0 to 10 starts: 1, 2, 3, 4, 6, 16, 27, 24, 9, 11, 5, Partition ends with i,j 8 7 : 1, 2, 3, 4, 6, 5, 11, 9, 24, 27, 16, Partition pivot 4 starts: Partition from 0 to 7 starts: 1, 2, 3, 4, 6, 5, 11, 9, Partition ends with i,j 4 2 : 1, 2, 3, 4, 6, 5, 11, 9, Partition pivot 2 starts: Partition from 0 to 2 starts: 1, 2, 3, Partition ends with i,j 2 0 : 1, 2, 3, Partition pivot 5 starts: Partition from 4 to 7 starts: 6, 5, 11, 9, Partition ends with i,j 5 4 : 5, 6, 11, 9, Partition pivot 11 starts: Partition from 5 to 7 starts: 6, 11, 9, Partition ends with i,j 7 6 : 6, 9, 11, Partition pivot 6 starts: Partition from 5 to 6 starts: 6, 9, Partition ends with i,j 6 4 : 6, 9, Partition pivot 27 starts: Partition from 8 to 10 starts: 24, 27, 16, Partition ends with i,j 10 9 : 24, 16, 27, Partition pivot 24 starts: Partition from 8 to 9 starts: 24, 16, Partition ends with i,j 9 8 : 16, 24, Final array: 1, 2, 3, 4, 5, 6, 9, 11, 16, 24, 27,