University of Toronto CSC 270F - Fall 1996 Assignment 4: Dynamic Programming Due Wednesday, December 4, 1996, at 12:00 noon in the box in SF4306D. Solve the following two dynamic programming problems. The problems should be solved by hand. For full marks provide all the intermediate steps. If you wish, you may write programs against which to verify your own results, but you may not hand in the output of these programs. We won't be able to tell if your output comes from a program, of course, but it'll be to your advantage for the final exam to do the dynamic programming by hand. Question 1 You have been given the job of organizing a spell checker for a very small language stored as a binary search tree. You know the frequency of occurrence of each of the words in the language. a) For simplicity, assume that you are only concerned with constructing the optimal tree for correctly spelled words. The problem is different if misspelled words must be considered. Construct the optimal binary search tree for these words and frequencies (these words were gleaned from the CSC270 newsgroup): asymptotic 19% engrossed 12% independent 8% irrelevant 10% its 4% misspell 2% necessary 3% receive 11% sentence 18% slaughtered 13% b) If you were to construct an optimal binary search tree that considered misspelled words, what other statistics would you need to know? Explain why these statistics are necessary. Describe how you would use dynamic programming to determine the optimal binary tree, taking into account misspelled words and given the apropriate statistics about misspelled words. Question 2 Examinations are fast approaching and you know how much time you can allot to studying. You have been able to estimate the influence that an hour of studying in each of your courses will influence your final marks. Based on the following table of courses and benefits, how should you best allocate your study time to maximize the absolute increase in the sum of your final marks? There may multiple strategies that produce the same optimal increase. Report all such strategies. You have 11 hours of time available for study. Some of your courses are in better shape than others. Each has a certain startup cost which is proportional to the number of hours needed to catch up on readings and organize notes. This is a one time cost if you decide to invest the time studying for this course. The startup cost is (unintuitively) measured as a number of marks so that it fits into the ``mark increase'' function: mark_inc = hours_spent * inc_per_hour - startup_cost The increase in mark is 0 if no time is spent on a course. There is one restriction: The different courses have different productive study block sizes measured in hours and you may only allocate whole blocks of time to a course, not parts of a block of time. For example, for CSC258 (below), you may only study in blocks of three hours: 3, 6, 9, ... Course Increase in mark Block size Start up cost per hour of study time (hours) (marks) CSC 270 3 1 0 CSC 258 7 3 15 CSC 238 9 4 30 CSC 228 5 2 5 CSC 209 4 1 2