Exam 2 is closed book and closed notes. Here are the topics covered:
Huffman coding Divide and Conquer MergeSort counting inversions closest pair of points Tree representation Dynamic ProgrammingWeighted interval schedulingKnapsack problem Optimal Substructure Matrix and Tree representations +String Edit Distance Substring Search Boyer-Moore
Sample Questions:
1. (Divide and Conquer) Perform the Merge Sort algorithm on the following string to order it alphabetically. Show the arrays returned from each recursive call.
2. (Dynamic Programming) You have to study for a test that is in 50 hours. You want to study the most important material in those 50 hours. You rank importance of a topic by how many lectures there were on that topic. Also each topic will take time depending on how many slides you need to review because each slide takes you 30 minutes to study. You have these rankings: (rank,slides), (2,10), (3,20), (6.6,30), (4,40), (6, 50). Apply the Knapsack Dynamic Programming solution to this problem to find the optimal set of things to study. What are the optimal set of things to study? Show the table you compute. What should you study if it takes you 40 hours to compute this table?
3. (Divide and Conquer) How many inversions are there in the following string. Draw the D&C tree showing the inversion count at each step.
4. (Dynamic Programming) You go to a casino and see a game called NIM. In this game each player selects 1, 2, or 3 elements from stacks and avoids being the player to select the final element. You learn this game and realize that there are not that many unique game states. You think to yourself that if you used dynamic programming you could memoize states and calculate the solution very fast. This version is using two stacks. Draw the game tree for NIM with two stacks starting at 4 and 3. Identify the redundant states. Do you go first or second? What move do you make first and why?
5. What is the optimal prefix free tree for the string (Remember that spaces are characters):
Also compress this string using that prefix free code.