CS 161: Design and Analysis of Algorithms – Spring 2015

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

Description:

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.

Prerequisites:

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:
Exams:

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.

Homework:

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


Lectures:
(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 Order 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]