## 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. Midterm Solutions: [pdf]

The final exam will be on Saturday, June 4, 7-10pm at Dinkelspiel Auditorium, as specified by the registrar.
There will NOT be an alternate final exam, so plan accordingly.

PRACTICE FINAL Solution: [pdf]

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, Red-Black trees [pdf]
8. (More) Red-Black Trees and Hashing with Chaining [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: (More) Dijkstra's, Bellman-Ford, Amortized Analysis and Incrementing a Binary Counter [pdf]
13. Dynamic Programming: Floyd-Warshall, Longest Common Subsequence [pdf]
14. Greedy Algorithms: Activity Selection, Minimum spanning tree: Boruvka, Kruskal, Prim [pdf]
15. Minimum Cut: Karger's Algorithm [pdf]
16. Max Flow / Min st-Cut, Ford-Fulkerson [pdf]
17. Max Flow: Edmonds-Karp, Bipartite Perfect Matching [pdf]