CSE 202,
Spring 2010
Algorithm Design and Analysis
Lecturer: Professor
Fan Chung Graham
fan@ucsd.edu
TA: Alex Tsiatas
atsiatas@cs.ucsd.edu
TA: Wenbo Zhao
w3zhao@cs.ucsd.edu
Time & Place: Lectures M W 56:20pm Peterson Hall 102
Discussion Section Th 44:50pm Warren Lecture Hall 2111
Office Hours: Fan Chung Graham, APM 7101 W 2:303:30 pm.
Alex Tsiatas, EBU3B (CSE Building) B250A, T 12:001:30pm.
Wenbo Zhao, EBU3B (CSE Building) 4232, T 5:006:00pm.
Syllabus:
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.
A schedule:

Weeks 12, Chapter 1, Introductory problems (Reading: Chapters 23. Also
check the reading list)

Weeks 23,
Chapter 4, Greedy Algorithms (covering 4.44.6)

Weeks 45, Chapter 5, Divide and conquer (covering 5.15.4)

Weeks 56, Chapter 6, Dynamic Programing (covering 6.16.4 and 6.66.8)
Note the coverage has been changed.

Midterm May 5, Wednesday

Weeks 78, Chapter 7, Network Flow (covering 7.17.3, 7.57.10)

Week 9, Chapter 11, Approximation Algorithms (covering 11.111.3)
(Reading: Chapter 8, NP and Computational Intractability )

Week 10, Local Search with additional material on PageRank algorithms
 Final Exam June 11, Friday, 710pm Peterson 102
Grading: 5 homework sets (20%), 1 midterm (30%) and 1 final (50%)
Homework: All homework assignments should be handed in class
(before the lecture starts) at the
specified due dates:
Homework #1 (Wed. April 7)
Homework #2 (Wed. April 21)
Homework #3 (Mon. May 3)
Homework #4 (Wed. May 19)
Homework #5 (Wed. June 2)
The midterm and final will include problems very similar to those in homework assignments.
No
late homework will be accepted.
Due to the heavy load for our TA, not all of the homework problems will be
graded.
At least one problem from each set will be randomly chosen for grading.
Only the best four scores out of five homework assigments will be taken into account.
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(n^{2}),
you will
only get a very partial score.
Reading
Homework

Announcement
Review slides