CSE 202,
Winter 2008
Algorithm Design and Analysis
Lecturer: Professor
Fan Chung Graham
fan@ucsd.edu
TA: Nan Zang
nzang@cs.ucsd.edu
Time & Place: Lectures M W 5-6:20pm EBU3 2154
Office Hours: Fan Chung Graham, EBU3, 2136 W 3:00-4:00 pm.
Nan Zang, EBU3 B250A, Th 4:00-6: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 tentative schedule
-
Weeks 1-2, Chapter 1, Introductory problems (Reading: Chapters 2-3. Also
check the reading list)
-
Weeks 2-3,
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 Feb 13 Wednesday
-
Weeks 7-8, Chapter 7, Network Flow (covering 7.1-7.3, 7.5-7.10) Note the change of coverage.
-
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 Mar. 17, 7-10 pm
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. Jan. 16) Note the change from Jan. 14.
Homework #2 (Mon. Jan. 28)
Homework #3 (Mon. Feb. 11)
Homework #4 (Mon. Feb. 25) Note that this is cancelled.
Homework #5 (Mon. March. 10)
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.
Final exam is a take-home exam which will be handed out on Wednesday March 12th 6pm
and be handed in by 3pm, Thursday March 20 at EBU3 2136.
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
/HTML>