15-451 Mini #3: due midnight Tuesday March 7

Submit this assignment by email to Lea Kissner <leak@cs.cmu.edu>.
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.