Stanford University, Winter 2021
Instructors: Nima Anari and Moses Charikar
Time: Mon & Wed 10:00 am - 11:20 am
Location: Zoom. See Canvas for all Zoom lecture/section information (e.g. meeting links and authentication details).
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.
Staff Contact: The best way to reach the staff is by making a private post on Ed. You may also reach us by email at firstname.lastname@example.org (this mailing list is monitored by the Student Liaison) with any questions or concerns that you do not wish to post on Ed.
Course Grade: The course grade will be based on the following components.
- 7 Homework assignments: 55% (that is 7.857% per homework, see below)
- HW 1-6 and HW 8 will be graded. HW 7 is removed and replaced with a set of ungraded practice problems.
- 4 Exams: 45% (that is 15% per exam, see below)
- From the first three exams, the exam with the lowest grade will be dropped. The last exam cannot be dropped.