Fan Chung Graham
Algorithm Design and Analysis
TA: Olivia Simpson
Time & Place: Lectures T Th 12:30 - 1:50pm Peterson Hall 102
Office Hours: Fan Chung Graham, APM 7101 W 2:00-3:00 pm.
Olivia Simpson, CSE B240A TuTh 11:00am-12:00pm.
This couses covers two main themes --
basic algorithms and
some recent developments on Internet algorithms. Also see the
Departmental CSE202 page.
The text book is
Algorithm Design by J. Kleinberg and E. Tardos,
supplemented by other material included in
by Dasgupta, Papadimitriou and Vazirani.
A tentative schedule
Grading: 4 homework sets (20%), 1 midterm (30%) and 1 final (50%)
Weeks 1-2, Chapter 1, Introductory problems (Reading: Chapters 2-3. Also
check the reading list)
Chapter 4, Greedy Algorithms (covering 4.4-4.6)
Weeks 4-5, Chapter 5, Divide and conquer (covering 5.1-5.4)
Weeks 5-6, Chapter 6, Dynamic Programing (covering 6.1-6.4 and 6.6-6.7)
Midterm May 8, Thursday
Weeks 7-8, Chapter 7, Network Flow (covering 7.1-7.3, 7.5-7.10)
Week 9, Chapter 11, Approximation Algorithms (covering 11.1-11.3)
(Reading: Chapter 8, NP and Computational Intractability )
Week 10, Local Search with additional material on PageRank algorithms
- Final Exam
June 9, Monday 11:30am -- 2:30pm
take-home exam, handing out after the last
lecture and due noon June 9 Monday at APM 7101.
Homework: All homework assignments should be handed in class
(before the lecture starts) at the
specified due dates:
Homework #1 (Tuesday April 15)
Homework #2 (Tuesday April 29)
(Tuesday May 20) (Thursday May 22)
(Tuesday June 3) (Thursday June 5)
The midterm and final will include problems very similar to those in homework assignments.
late homework will be accepted.
Due to the heavy load for our TA, not all of the homework problems will be
At least one problem from each set will be randomly chosen for grading.
Note that the exam scores depend on the efficiency of your algorithm. For example, if the best
algorithm has running time O(log n) but your algorithm is O(n2), you will
only get a very partial score.