Analysis of Algorithms I, Fall 2026

General Information

• Instructor: Xi Chen, CSB 503
• Location: TBA
• Time: MW 8:40am--9:55am
• Office hours: Tuesday 8:30pm--9:30pm on zoom (links on courseworks)
• Textboook: Introduction to Algorithms (third or fourth edition), by Cormen, Leiserson, Rivest and Stein
• Please follow this link to sign up on Piazza.
• Lecture topics and homeworks are posted on the Lectures page
• Supplementary Reading:
  • The Design and Analysis of Computer Algorithms, by Aho, Hopcroft, and Ullman
  • Data Structures and Algorithms, by Aho, Hopcroft, and Ullman
  • Algorithms, by Dasgupta, Papadimitriou, and Vazirani
  • Algorithm Design, by Kleinberg and Tardos

Instructional Assistants

• TBA

Course Description

• In this course, we focus on principles and techniques that are widely used in the design and analysis of efficient computer algorithms. Topics covered include:
  • Asymptotics and recurrences
  • Sorting and searching
  • Greedy algorithms
  • Amortized analysis
  • Dynamic programming
  • Graph algorithms
  • Randomized algorithms
  • Approximation algorithms
  • NP-completeness

Prerequisites

• COMS 3137/3139: Data Structures and Algorithms and COMS 3203: Discrete Mathematics.

Grading

• Five homework assignments (best four out of five) 20%
• Quiz on Sep 30: 20%
• Midterm evaluation on Oct 21: 20%
• Quiz on Nov 18: 20%
• Final evaluation on Dec 14: 20%

Homeworks

• Five problem sets will be assigned during the semester. They will be assigned here. Only the four best of your five problem sets will be counted. The aggregate score of these five assignments will constitute 20% of your final grade. Homeworks must be typed or legibly written and scanned (LaTeX is preferred but not required). Post your solutions on Gradescope before 11:59pm on the due date.
• Since only four out of five assignments will be counted, this policy will allow you to skip one problem set for whatever reason you choose. Late assignments will not be accepted. In the case of a serious medical or family emergency, please provide necessary documentation to your advising dean and have the dean contact me to discuss appropriate accommodations.
• We will not police or attempt to detect the use of AI on homework assignments. Instead, to encourage you to engage with the problems and work on them independently, we will adopt the following policy: as long as you submit your homework, you will automatically receive 50% of the credit for each problem. Your earned credit will then be added on top of this 50%, up to the full credit for the problem. For example, on a 10-point problem, if your solution earns 3 points (or 6 points), your final score will be 8 points (or 10 points).