CSC 477/677 Study Guide for the Final Examination Fall 2005

1. Study homework questions.
2. There will be true/false questions.
3. There will be some definitions and fill-in-the-blank questions.
4. Review reccurrences.
5. Review your class notes, in particular:
   1. Asymptotic classes and solving recurrences.
   2. Union-find.
   3. Graham's scan.
   4. Data structures used to represent graphs.
   5. Topological sorting.
   6. Using depth first search and breadth first search. Finding components of a graph. Finding strong components of a directed graph.
   7. Dynamic programming.
   8. Matrix representations of graphs, directed graphs. weighted graphs, and weighted directed graphs, and (min,+) matrix multiplication.
   9. Dijkstra's algorithm.
   10. Minimum spanning trees, including Kruskal's and Prim's algorithms.
   11. Sparse array representations, including using search structures.
   12. Sorting (all algorithms given in class)
   13. Huffman's algorithm.
   14. Dynamic programming, divide and conquer, greedy algorithms.
   15. Search structures, including binary search structures, AVL trees, tries, B-trees, 2-3 trees, and hash tables.
6. One question that will require serious thinking. There will be no way to answer this question by having simply memorized material. (I will flag that question on the test.)