In this course, we will study the design and analysis of efficient algorithms. The focus will be on fundamental design techniques such as greedy approaches, divide and conquer, dynamic programming, network flow, and randomized algorithms. We will study measuring program performance using asymptotic notation.

The principle focus of the lectures will be theoretical. In addition to the lectures and their associated homework assignments, there will be a number of programming assignments, in which you will be required to implement algorithms.
Office Hours:

Monday 1-2pm, ENS 112-B

Razieh Nokhbeh Zaeem, TA
Office Hours:

Monday 4-6pm, ENS 122

Xi (James) Zheng, TA
Office Hours:

Wednesday 2-4pm, ENS 122

Course Information

Class meetings

MWF 11:30am–12:45pm, ENS 116


Targeted to undergraduate students who have taken a programming course and are comfortable writing code in some programming language.

Required text


Optional text



24%Homework assignments (8 assignments)
16%Programming assignments (4 assignments)
40%Midterm Examinations
20%Final Examination

Tentative Schedule

Topic 1: Foundations

Introduction, Administrivia

Stable Matching

Stable matching analysis and implementation

Asymptotic growth

Topic 1: Graphs

Basic concepts and traversal

Directed graphs

Exam I - 10% - CPE 2.208

Topic 1: Greedy Algorithms

Interval scheduling

Shortest path algorithm

Minimum spanning trees

Implementing Kruskal’s algorithm

Topic 1: Divide and Conquer


Recurrence relations

Integer multiplication

Fast fourier transform

Exam II - 15% - CPE 2.208

Topic 1: Dynamic Programming

Weighted interval scheduling


Sequence alignment

Shortest Paths

Topic 1: Network Flow

Maximum-flow problem

Flows and Cuts

Bipartite matching

Exam III - 15% - CPE 2.208

Topic 1: Revision




Topic 1: NP-Completeness





Final Version 1 Version 2 Version 3 - 20% - 9AM-12PM