Link Search Menu Expand Document

Design and Analysis of Algorithms

Stanford University, Winter 2022

Instructors: Nima Anari and Moses Charikar

Time: Mon & Wed 9:45 am - 11:15 am

Location: Zoom for the first three weeks, then 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, randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Possible additional topics: network flow, string searching, amortized analysis, stable matchings, and approximation algorithms. 

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.

  • 8 Homework assignments: 50% (that is 7.143% per homework, see below)

    • The lowest homework score will be dropped, so each of your 7 graded homework assignments comprise 7.143% of the course grade.
  • Midterm Exam: 20%
  • Final Exam: 30%