Link Search Menu Expand Document

Design and Analysis of Algorithms

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 (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.