Algorithms and Complexity

[ News | CIS | UO | CIS621 ]

CIS 621 Assignment 3

due next Wednesday, March 4

Winter 2009

  1. Construct the OBST for two data items, where the first item is accessed twice as frequently as the other and there are no failed searches. Give the probabilities of failed searches that will cause the other BST to be optimal.

  2. Specify the recursive solution to construct an OBST with non-zero probabilities of failed searches q0, q1, ..., qn in addition to probabilities of access p1, p2, ..., pn..

  3. Apply the resulting dynamic programming algorithm to the probabilities of successful searches p: .3, .1, .1, .1 and failed searches q: .05, .10, .10, .10, .05

  4. Specify the recursive solution to construct an OBST where the data elements are in the leaves only. Show the computation leading to the construction of such an OBST for search probabilities as in problem 3. above.

  5. Let r(i,j) be the position of the root of an optimal BST for the subproblem involving data items ai,...aj. Show the complexity of an DP algorithm relying on the property r(i,j-1) \leq r(i,j) \leq r(i+1,j).