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.