Analysis of Algorithms I, Fall 2025

General Information

• Instructor: Xi Chen, CSB 503
• Location: 428 Pupin Laboratories
• 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

• Alena Chan, Office hours: Thursday 3pm--4pm in the CS TA room, Email: ac5477@columbia.edu
• Ethan Chang, Office hours: Tuesday 4:30pm--5:30pm on zoom (links on courseworks), Email: ec3665@columbia.edu
• Christopher Connor Henry, Office hours: Thursday 4pm--5pm in the CS TA room, Email: cch2201@columbia.edu
• Caden Lin, Office hours: Wednesday 4:30pm--5:30pm on zoom (links on courseworks), Email: cl4319@columbia.edu
• Emma Yin, Office hours: Monday 4:30pm--5:30pm in the CS TA room, Email: jy3442@columbia.edu

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

• Six homework assignments (best five out of six) 20%
• Midterm evaluation 40%
• Final evaluation 40%
• Midterm will be on Oct 20, and final will be held in the exam week.

Homeworks

• Six problem sets will be assigned during the semester. They will be assigned here. Only the five best of your six 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 five out of six 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.
• You are expected to adhere to the Academic Honesty Policy of the Department of Computer Science. You are not allowed to use the Internet for homeworks and midterm / final evaluations. You can consult the instructor and the TAs or collaborate with your fellow students, but you must acknowledge these sources by listing names of TAs and / or students you collaborate with at the beginning of each problem. Collaboration without acknowledgment is considered cheating. Erase records (whiteboard pictures or your own notes, etc) at the end of a group discussion so that you can write solutions in your own words by yourself.
• Every student caught cheating will be referred to Colubmia's office of Student Conduct and Community Standards, as well as subject to academic penalty in the class.