Midterm Study Guide
CSE 421: Introductions to Algorithms
Autumn 2010

Midterm Exam, Friday, November 5, 2010

• Midterm Policies
  • The midterm allows for open book and open notes. Bring the text book and your own personal notes. Nothing else.
  • The exam begins promptly at 1:30 and ends at 2: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.
• 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 discovering which algorithmic approach to take on a problem.