Computer Science 302
Data Structures

CSC 302 Study Guide for the Second Midterm Examination Spring 2006, April 6

1. Review your homework assignments.
2. There will be true/false questions.
3. There will be some fill-in-the-blank questions.
4. Dijkstra's Algorithm an example.
5. Work a min-plus matrix multiplication problem.
6. Questions about preorder, postorder, etc.
7. Work an example using polyphase mergesort.
8. Possibly a question to see whether you understand
   1. Heapsort
   2. Quicksort
   3. Kruskal's Algorithm
   4. Loop invariants (example)
   5. Hashing
      1. Separate chaining, vs. What?
      2. What makes a good hash function?
      3. Perfect Hashing ... when would you use it?
9. Graphs
   1. Components and strong components
   2. Cycles and directed cycles
   3. Neighbor list representations and matrix representations
   4. Sparse graphs (Are planar graphs sparse?)
10. Dynamic programming an example problem
11. Greedy Algorithms
    1. When is Greedy good? Bad?
    2. Huffman's algorithm for prefix coding
    3. Kruskal's algorithm