1. Dijkstra's algorithm takes time O(m + n log n) = O(n^{3/2} + n log n) = O(n^{3/2}).  With a d-ary heap, the optimal choice of d is d=m/n, for which the time is O(m log_d n) = O(n^{3/2} log_{n^{1/2}} n) = O(n^{3/2} * 2) = O(n^{3/2}). Therefore, in terms of O-notation both are equal.

2. (a) When we start the second search for x, we have just completed a search for y, and therefore y must be at the root.

(b & c) There are either two nodes (x and y) or three nodes (x, y, and another node between them) on the path. So the minimum is two and the maximum is three.

3. Both cuckoo hashing and hash chaining use constant average time per operation, but in cuckoo hashing the lookup operations are guaranteed to always take constant time, whereas in hash chaining a small number of lookups might take much longer than constant time. Therefore, cuckoo hashing is better in situations where fast lookups are essential. An example application in which this is true is internet packet routing: many internet routers do not have enough memory to buffer data for long periods of time, so they need to respond very quickly to each incoming packet of data.

4. (a) C/32
(b) 1 - (1 - 1/C)^{kn}
(c) C - C(1 - 1/C)^{kn}