Computer Science 477/677
Automata and Formal Languages

CSC 477/677 Study Guide for the Final Examination Spring 2004

Under Construction

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. Graph algorithms:
      1. Data structures used to represent graphs.
      2. Topological sorting.
      3. Dijkstra's algorithm.
      4. Minimum spanning trees, including Kruskal's and Prim's algorithms.
   2. Sorting (all algorithms given in class)
   3. Huffman's algorithm.
   4. Backtracking, dynamic programming, divide and conquer, greedy algorithms.
   5. Practice dynamic programming by working prolems 8.31 and 8.32 in your textbook.
   6. Preorder, inorder, and postorder traversals of a binary tree.
   7. Hashing.
   8. Fast addition in parallel.
   Review Chapter 5 in your textook, except for Section 5.8.