Description

Assignment 4 (100%)
Question 1 (60%)
Develop a program to create an optimal BST by using the technique of dynamic programming (described in section 8.3 in the textbook). You are required to calculate the “average number table” and “root table”. After creating the tree, the program prompts the user to enter a word (key) and searches the tree for the word. Whenever the program compares user input K with word W at node V , it displays word W, the minimum average number of comparisons of the subtree rooted at V (three digits after the decimal point), and the subtree to go (left or right). If the program fails to find the K in the tree, it displays “not found” after comparisons.
Question 2 (40%)
Develop a program to create an optimal BST by using the greedy technique. After creating the tree, the program prompts the user to enter a word (key) and searches the tree for the word. Whenever the program compares user input K with word W at node V , it displays word W, the probability of W (three digits after the decimal point), and the subtree to go (left or right). If the program fails to find the K in the tree, it displays “not found” after comparisons.
1