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.