CS 161: Design and Analysis of Algorithms – Spring 2015

Instructor: Virginia Vassilevska Williams
Time: Mondays and Wednesdays 11:00a-12:15p
Location: NVIDIA Auditorium


Worst and average case analysis. Recurrences and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis, randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Introduction to network flows and graph matchings.


Before taking CS 161, it is important that you complete CS 103 and CS 109/STATS 116, or the equivalents.
In particular, you should be comfortable with proofs, discrete mathematics, basic graph and set theory, and introductory probability theory.

Useful Information:

There will be two exams for the course: one midterm and one final.
The midterm will be on Monday, May 4th at 7:00-8:15p. The final exam will be on Friday, June 5 from 8:30-11:30a, as specified by the registrar.
Midterm Location: Hewlett 200 and 201 [solutions]
Final Location: TBD
There will NOT be an alternate final exam, so plan accordingly.


Before working on the homework, please read the homework policy.

(Lightly edited by professor and head TA)
  1. Introduction, Why are you here? [pdf]
  2. MergeSort, Recurrences, Asymptotic Analysis [pdf]
  3. Median and Selection [pdf]
  4. Divide And Conquer, Solving Recurrences, Integer Multiplication [pdf]
  5. Quicksort [pdf]
  6. Sorting Lower Bounds and Counting Sort [pdf]
  7. Binary Search Trees [pdf]
  8. Red-Black Trees and Hashing [pdf]
  9. Open Addressing and DFS [pdf]
  10. DFS, Topological Sort and BFS [pdf]
  11. Shortest Paths: Dijkstra's Algorithm [pdf]
  12. Shortest Paths and Dynamic Programming: Bellman-Ford and Floyd-Warshall [pdf]
  13. Dynamic Programming: Longest Common Subsequence, Greedy Algorithms: Activity Selection [pdf]
  14. Minimum spanning tree: Boruvka, Kruskal, Prim [pdf]