CS 161: Design and Analysis of Algorithms – Spring 2016

Instructor: Virginia Vassilevska Williams

Time: Tuesdays and Thursdays 3-4:20p

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.

• Course Staff / Office Hours
• Tentative Syllabus
• Grading and Homework Policies
• Piazza Forum
• Gradescope, code: MN2K3M
• Useful Mathematical Terms
• Homework Advice

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.

• Homework 6: [pdf], due May 27, 12pm. (Please follow this post for clarifications/updates. ) Solution: [pdf]
• Homework 5: [pdf], due May 20, 12pm. ( Please follow this post for clarifications/updates. Last update: May 13th at 8:50pm.) Solution: [pdf]
• Homework 4: [pdf], due May 13, 12pm. Solution: [pdf]
• Homework 3: [pdf], due April 29, 12pm. (Clarification for Q2 is added to PDF as of 4/25 11am.) Solution: [pdf] (We updated solutions after the midterm -- last update: May 10, 10am.)
• Homework 2: [pdf], due April 22, 12pm. Solution: [pdf]
• Homework 1: [pdf], due April 15, 12pm. (please see this post for a clarification on Q4-d.) Solution: [pdf]
• Homework 0: [pdf], due April 8, 12pm. Solution: [pdf]

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]