Analysis of Algorithms I, Spring 2022

General Information

• Instructor: Xi Chen, CSB 503
• Location: 614 Schermerhorn Hall
• Time: MW 8:40am--9:55am
• Office hours: Thursday 9am-10am in the fifth floor open area of CS Building
• Textboook: Introduction to Algorithms (third 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

• Andrei Coman, Office hours: Friday 11am-12pm in TA room, Email: ac4808@columbia.edu
• Eumin Hong, Office hours: Friday 2:30pm-3:30pm in fifth floor open area of CS Building, Email: eh2890@columbia.edu
• Cindy Wang, Office hours: Wednesday 11am-12pm in fifth floor open area of CS Building, Email: bw2596@columbia.edu
• Rockwell Jacob Weiner, Office hours: Tuesday 3pm-4pm in TA room, Email: rjw2164@columbia.edu
• Yunya Zhao, Office hours: Thursday 4:30pm-5:30pm on zoom (links can be found on courseworks), Email: yz3754@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) 30%
• Midterm evaluation 35%
• Final evaluation 35%
• Midterm will be on March 9 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 30% 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.