EXAM 1 Study Guide

Topic List:

Divide and Conquer
MergeSort
counting inversions
closest pair of points
Tree representation

Dynamic Programming
Weighted interval scheduling
Knapsack problem
Optimal Substructure
Matrix and Tree representations

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.

S O R T R E A L L Y F A S T

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.

1 2 4 3 5 6 7 1

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. What is your optimal first move?