Final Exam Study Guide
CSE 421: Introductions to Algorithms
Autumn 2010

Final Exam, Monday, December 13, 2010, 2:30 - 4:20

• Final Exam Policies
  • The Final Exam allows for open book and open notes. Bring the text book and your own personal notes. Nothing else.
  • The exam begins promptly at 2:30 and ends at 4:20.
• Topics covered
  • Basics of Algorithms: Example of stable matching problem. Common running times and elementary analysis of algorithms. Chapters 1 and 2, all sections.
  • Graph algorithms: Breadth-first search, shortest path, connectivity, topological sorting. Chapter 3, all sections.
  • Greedy Algorithms: Interval scheduling, minimizing lateness, optimal caching, Dijkstra's Algorithm, minimum spanning tree (Prim's and Kruskal's algorithms), simple clustering. Chapter 4, all sections except sections 4.8 and 4.9.
  • Divide and Conquer Algorithms: Mergesort, counting inversions, closest pair of points, integer multiplicaiton, matrix multiplication, Fast Fourier Transform. Chapter 5, all sections
  • Dynamic Programming: Weighted interval scheduling, memoization or iteration solutions, segmented least squares, subset sums and knapsacks, RNA secondary structure, string alignment, Bellman-Ford Algorithm, detecting negative cycles. Chapter 6, all sections.
  • Network Flow: Ford-Fulkerson Algorithm, choice of augmenting paths, reduction of problems to network flow (bipartite matching, disjoint paths), applications (survey design, image segmentation, project selection, baseball elimination, Extensions of network flow (circulation, lower bounds on flows). Chapter 7, all sections ex 7.4 and 7.3.
  • NP and Computational Intractability: polynomial time reductions, NP, NP-Complete, Co-NP, proofs of NP-completeness, taxonomy of hard problems. Chapter 8, all sections.
  • Linear Programming: Duality, Simplex Algorithm, reductions to LP, LP relaxation.
  • Contiguous Ordering and PQ-trees
• Study suggestions
  • Work in study groups to help each other out in preparation. Give each other problems to do in an exam setting. After doing the problems alone, critique each others answers.
  • Practice each algorithm on small examples.
  • Practice analysis and solving recurrences.
  • Practice finding polynomial time reductions.
  • Practice discovering which algorithmic approach to take on a problem.