15-451 Mini #3: due midnight Tuesday March 7
Submit this assignment by email to Lea Kissner .
When submitting, please use the subject line "15-451 MINI #4" in your
email. If you have a question, please use the subject line "15-451
MINI #4 QUESTION" in your email.
------------------------------------------------------------------------
1. Optimal Binary Search with Unsuccessful Searches
In class we gave an algorithm that takes a set of frequencies f[1],
f[2], ... f[n] for the n keys that are stored in a binary search tree,
and constructed the binary search tree with the minimum average
cost over the sequence of accesses. Here's the algorithm.
Define f[i,j] to be the sum f[i] + f[i+1] ... + f[j].
C[i,j] = f[i,j] + Min C[i,k-1] + C[k+1,j] if i <= j
i <= k <= j
C[i,j] = 0 if i > j
(a) Explain how to compute all the f[i,j]s in O(n^2) time.
(b) Generalize this algorithm to also take as input frequencies of
unsuccessful searches U[0], U[1]...U[n] where U[i] is the number
of unsuccessful searches for the range between key i and key i+1.
(U[0] means searches left of key 1 and U[n] means searches to the
right of key n.)
2. Random Relaxation
Let G be a directed graph with costs c(i,j) on the edges. Each vertex
v has a variable d[v], all of which start at infinity, except at the
source s, where d[s] = 0. The following relaxation step is applied
until it cannot be applied any longer:
Find any edge (i,j) such that d[i] + c(i,j) < d[j]. Now
replace d[j] by d[i] + c(i,j).
(a) Prove that if the graph has no negative cycles, then the process
must terminate.
(b) At the end, d[i] is the shortest path distance from s to i.
Give some intuition for why this is the case.