COSC 511  Algorithms
Topic for 11/2014 November Test

I. Homework and other assignments have covered the mechanics of the various
algorithms. You should be able to exercise any of the algorithms that have been
covered.

II. A final exam from a previous offering of this class is available on the web.
See http://emunix.emich.edu/~haynes/511 and look around.

III. Chapters covered:K & T: 1 - 6. Other topic: recurrences

IV. This test will ask questions about the meaning, purpose, and general principles
of the various topics we have covered. That is, it is more than just mechanics.

Consider the following:
1. What is a greedy algorithm?
2. What does it mean to say a solution is "optimal"?
3. Why will a greedy algorithm fail to give an optimal solution?
4. What happens to a MST algorithm (such as Kruskal's) when the initial
graph has multiple connected components?
5. Is the shortest path in an undirected graph also a shortest path in a directed
graph?
6. Give an informal explanation for the Big-Oh of the stable matching (Gale-Shipley)
algorithm.
7. Suppose in the stable matching problem, there are more women then men.
How could you extend the Gale-Shipley algorithm to accomodate that? 
8. Is G-S a greedy algorithm? Is it a divide-and-conquer algorithm?
9. Consider the problem of storing data in a binary search tree. Does this
data structure lend itself to greedy algorithms or to divide and conquer algorithms?
10. Consider a divide-and-conquer algorithm where the data set is divided into
four smaller data sets, each 1/4 the size of the original. What is the general
form of a recurrence that will give the running time?
11. How would you describe a divide and conquer algorithm?
12. What is memoization?
13. What is the difference between dynamic programming and divide-and-conquer?