Final Study Guide
CSE 373: Data Structures and Algorithms
Winter 2003

Final Exam, Wednesday March 19

• Exam policies
  • The final is closed book. No notes allowed either.
  • You will be provided with the text of the exam and enough paper (back pages) to do you work. You can bring scratch paper if you wish so. Please no "cheating".
  • The exam begins promptly at 2:30 and ends at 4:20.
• Topics covered (in lecture order)
  • Look first at the midterm study guide. Remember that I did not ask extensive questions on hashing and binary heaps in the Midterm so be warned!
  • Binomial Queues
    Lecture 12. Weiss Section 6.8
  • Sorting. Inversion based sort (bubblesort; Insertionsort). Comparison based sort (Mergesort, Heapsort, Quicksort). Lower bound on comparison-based sorting. Radix Sort.
    Lectures 13, 14, 15. Weiss Chapter 7 (except Sections 7.4 and 7.10) amd Chapter 3 Section 2.6
  • Disjoint Set ADT (Union-Find)
    Lecture 16. Weiss Chapter 8 (except Section 6)
  • Graphs. Terminology. Representations.
    Directed graph algorithms (topological sort). Breadth-first and Depth-First Search. Single-source shortest-path (Dijkstra's algorithm). All pairs shortest-path. Transitive closure. Warshall and Floyd algorithms.
    Undirected graph algorithms. Mimimal Cost Spanning Trees (Prim, Kruskal). Euler paths and circuits.
    Lectures 16, 17, 18, 19, 20, 21, 22. Weiss Chapter 9 Sections 9.1, 9.2, 9.3 (except 9.3.3), 9.5, 9.6.3, 10.3.4
  • Huffman encoding
    Weiss 10.1.2
• Study suggestions
  • Review the HW and their solutions.
  • I will not ask "problems" on anything in graphs that was not covered on the homeworks. However, I can ask factual questions such as: "Can I find Euler circuits in linear time".
  • Do more concrete problems from the book. In additions to the suggestions from the midterm study guide, from Chapter 7: 7.17, 7.18, 7.20, 7.23, 7.30 (look at page 249), 7.39; From Chapter 8: 8.6; From Chapter 9: 9.5; From Chapter 10: 10.6