CS 161: Design and Analysis of Algorithms – Spring 2016

Instructor: Virginia Vassilevska Williams
Time: Tuesdays and Thursdays 3-4:20p
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 Tuesday, May 3th, in class: 3-4:20pm.. The final exam will be on Saturday, June 4, 7-10pm, as specified by the registrar.
Midterm Location: NVidia Auditorium, Hewlett 200 (please see this post on Piazza. If you do not have a Piazza account, you can see the announcements here. )
Final Location: TBA
There will NOT be an alternate final exam, so plan accordingly.

Homework:

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


Lectures:
  1. Introduction, Why are you here? [pdf]
  2. MergeSort, Recurrences, Asymptotic Analysis [pdf]
  3. Divide And Conquer, Solving Recurrences, Integer Multiplication [pdf]
  4. Median and Selection [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 [pdf]
  10. Graphs, DFS and Topological Sort [pdf]
  11. Single Source Shortest Paths: BFS and 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]
  15. Minimum Cut: Karger's Algorithm [pdf]
  16. Max Flow / Min st-Cut [pdf]