CS 337 Project 1 Minimum Weight Binary Search Trees September 6 2006 1 Preliminaries Let X denote a set of keys drawn from some totally ordered universe U such as the set of all integers or the set of all real numbers Let n denote X and assume that the elements of X are x1 x2 xn Suppose we would like to process queries of the following form Given a key u in U determine whether u belongs to X A standard data structure for supporting such search queries is the familiar binary search tree BST For n 1 there is more than one BST containing the set of keys X For example for n 2 there are exactly two such BSTs one with x1 at the root and x2 at the right child of the root and one with x2 at the root and x1 at the left child of the root The n keys in X partition U into 2n 1 sets as follows the set of keys less than x1 which we denote U0 the singleton set of keys x1 which we denote U1 the set of keys greater than x1 and less than x2 which we denote U2 the singleton set of keys x2 which we denote U3 the set of keys greater than xn which we denote U2n Given a BST T containing X we search for a key u in U by performing a sequence of 3 way comparisons beginning at the root A 3 way comparison between two keys u and v determines whether u v u v or u v The sequence of 3 way comparisons performed in such a search is completely determined by the index i of the unique set Ui to which u belongs For any index i let w T i denote the number of 3 way comparisons used to search T for a key in Ui Further assume that for any index i the frequency with which we search for a key in Ui is known and is equal to fi Then we define the weight of BST T denoted w T as follows w T X w T i fi 0 i 2n In this assignment we explore several efficient methods for computing a minimum weight BST It is worth remarking that the particular values of the xi s have no impact on the structure of the minimum weight BST Thus we can represent an instance of the minimum weight BST problem by an odd length sequence of nonnegative frequency values hf0 f2n i 2 Dynamic Programming There is some similarity between the minimum weight BST problem and the optimal prefix code problem discussed in the lectures Accordingly one might hope to devise a greedy 1 algorithm similar to Huffman s algorithm for solving the minimum weight BST problem However no such greedy algorithm is known In this section we instead consider somewhat more complex algorithms based on a technique called dynamic programming 2 1 An O n3 Algorithm The key observation underlying the dynamic programming approach to the minimum weight BST problem is as follows Suppose we are given an instance I equal to hf0 f2n i of the minimum weight BST problem For all integers i and j such that 0 i j n let I i j denote the instance of the minimum weight BST problem given by length 2 j i 1 sequence of frequency values hf2i f2i 1 f2i 2 f2j i We define the size of an instance I i j as j i since the solution to instance I i j is a BST containing j i nodes Our plan will be to solve the given instance I I 0 n by successively solving all of the instances I i j in nondecreasing order of size But how do we go about solving a general instance I i j If i j the instance is trivial to solve so let us assume that i j The key observation underlying our approach is as follows Suppose that instance I i j admits a minimum weight BST T in which the left subtree T0 of the root contains n0 nodes and the right subtree T1 of the root contains n1 nodes Note that j i n0 n1 1 since the size of instance I i j dictates that T contains j i nodes Then we claim that T0 is a minimum weight solution to instance I i i n0 and T1 is a minimum weight solution to instance I j n1 j We will argue the correctness of this claim in the lecture associated with this programming assignment and also in the discussion sections The basic idea is that if either T0 or T1 is not minimum weight then T could be improved by replacing T0 and T1 with minimum weight solutions to I i i n0 and I j n1 j respectively such an improvement contradicts our assumption that T is a minimum weight solution to instance I i j Programming Exercise 1 35 points Use the foregoing claim to develop an algorithm for the minimum weight BST problem with running time O n3 Implement your algorithm in Java Your program should be contained in a single source file named CubicBST java The input to your algorithm is a sequence of minimum weight BST instances one per line The line of input encoding a particular minimum weight BST instance consists of a nonnegative integer n followed by 2n 1 nonnegative integers representing the sequence of frequencies hf0 f2n i The input is terminated by a line consisting of a single negative integer For each minimum weight BST instance your program should produce a single line of output indicating the weight of a minimum weight BST Note To simplify the coding task we are not asking you to output a minimum weight BST just the weight of such a BST 2 2 An O n2 Algorithm For all integers i and j such that 0 i j n let T i j denote the set of all minimumweight solutions to instance I i j and let i j denote the minimum over all T in T i j of the number of nodes in the left subtree of the root of T We claim that the following lemma holds The proof of the lemma is somewhat challenging and beyond the scope of this course Lemma 1 For all integers i and j such that 0 i j n and j i 2 we have i j 1 i j i 1 j 2 Paper Pencil Exercise 1 5 points Make use of Lemma 1 to justify the correctness of an improved version of the O n3 algorithm developed in Section 2 1 The improved version should run in O n2 time Programming Exercise 2 10 points Implement your O n2 algorithm in Java using a single source file named QuadraticBST java The input output behavior of QuadraticBST java should be the same as that of CubicBST java 3 A Greedy Algorithm for a Special Case In this section we develop algorithms for the special case of the minimum weight BST problem …