Homework 3

Details

1. (10) Solve the instance of the optimal binary search tree problem that contains items A, B, C, D, E, F with probabilities .15, .1, .23, .12, .33, .07 by using the algorithm from the textbook. Give the final tables and draw the tree. Show all of your work.
2. (10)
   1. Ask chatGPT to solve Problem 1 for you. Include in your solution the question you asked and the entire response.
   2. Evaluate chatGPT's solution. Did it get the correct solution? Did it explain it in a coherent way?
3. (10) Find a solution to the optimal binary search tree using items A-J with frequencies 1/2, 1/4, 1/8, 1/16, 1/32, 1/64, 1/128, 1/256, 1/512, 1/512 (assigned in that order). You may do it by hand, find help online, or use your intuition. In any of these cases, justify your solution. If you use chapGPT, you might want to double check to make sure it got it correct!
4. (20) Ask chatGPT for a Java implementation of an algorithm to solve the optimal binary search tree problem.
   1. Look at it and see if you can figure out how the algorithm works (which might be easier if it gives you an algorithm similar to the one from our book). Evaluate whether or not you think it computes the correct solution.
   2. Test the algorithm by running it on the textbook example, the example from Problems 1 and 3 above. Show the output of the algorithm! How did it do on these instances? Was it correct, close, or way off?
   3. What is the efficiency of the algorithm? Is it more or less efficient than the algorithm given in the textbook?
   4. Are there more efficient algorithms possible to solve this problem? Justify your answer. (Hint: Look at the exercises for section 8.3.)