CS 161

Welcome to CS 161!

Design and Analysis of Algorithms, Stanford University, Winter 2020.

Course Overview

Instructor: Mary Wootters

When and where? M/W 10:30 - 11:50am, NVIDIA Auditorium.

Course Description: This course will cover the basic approaches and mindsets for analyzing and designing algorithms and data structures. Topics include the following: 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. Possible additional topics: network flow, string searching.

Prerequisites: CS 103 or CS 103B; CS 109 or STATS 116.

What do I need to do? Eight homework assignments, a midterm, and a final. See the Course Policies for more details.

Announcements: Please check Piazza for course announcements.

Quick Links

  • Gradescope: Click here. Access code 9ZGBZZ.
  • Piazza: Click here.
  • Canvas (lecture videos): Click here.

Contact

To get in touch with the teaching team, please email cs161-win1920-staff@lists.stanford.edu or post privately on Piazza.

Schedule

(The future is mutable).
Monday Wednesday
1/6. Lecture 1: Why are you here? 1/8. Lecture 2: Asymptotics, Worst-Case Analysis, and MergeSort (AI Part 1, Ch. 1 and 2).
Homework 1 Assigned
1/13. Lecture 3: Solving Recurrences and the Master Theorem (AI Part 1, Ch. 4) 1/15. Lecture 4: Median and Selection (AI Part 1, Ch. 6.1, 6.3, 6.4)
Homework 1 Due; Homework 2 Assigned
1/20. MLK Day. No class. 1/22. Lecture 5: Randomized Algorithms and QuickSort (AI Part 1, Ch. 5.1--5.5)
Homework 2 Due; Homework 3 Assigned
1/27. Lecture 6: BucketSort and Lower Bounds for Sorting (AI Part 1, Ch. 5.6; CLRS 8.2 and 8.3) 1/29. Lecture 7: Binary Search Trees and Red-Black Trees (AI Part 2, Ch. 11.)
Homework 3 Due; Homework 4 Assigned.
2/3. Lecture 8: Hashing (AI Part 2, Ch. 12.1-12.4) 2/5. Lecture 9: Graphs and BFS and DFS (AI Part 2, Ch 8.1-8.5)
Homework 4 Due; study for the midterm next week!
2/10. Lecture 10: Strongly Connected Components (AI Part 2, Ch. 8.6) 2/12. Lecture 11: Dijkstra and Bellman-Ford (AI Part 2, Ch. 9)
Homework 5 Assigned.
2/17. President's Day. No class. 2/19. Lecture 12: Dynamic Programming: Bellman-Ford (again) and Floyd-Warshall (AI Part 3, Ch. 16,18)
Homework 5 Due; Homework 6 Assigned.
2/24. Lecture 13: More dynamic programming: LCS, Knapsack, Independent Set (AI Part 3, Ch. 17) 2/26. Lecture 14: Greedy Algorithms (AI Part 3, Ch. 13,14)
Homework 6 due; Homework 7 Assigned
3/2. Lecture 15: Minimum Spanning Trees (AI Part 3, Ch. 15) 3/4. Lecture 16: Min Cuts and Karger's algorithm (Kleinberg and Tardos Ch. 13.2)
Homework 7 Due; Homework 8 Assigned.
Note: HW8 will be on the short end! Almost there!
3/9. Lecture 17: Max-Flow and the Ford-Fulkerson Algorithm. (CLRS Ch. 26.1, 26.2, 26.3) 3/11. Lecture 18: What's next? (No reading).
Homework 8 Due; Study for the final!
3/16. Final Exam, 3:30-6:30pm.

Anonymous Feedback

Comments? Concerns? Please leave your (constructive) feedback here and help us make the course better!