CSE 202,
Spring 2015
Algorithm Design and Analysis
Lecturer: Professor
Fan Chung Graham
fan@ucsd.edu
TA
Olivia Simpson
osimpson@ucsd.edu
Time & Place: Lectures M W 5:00 - 6:20 pm WLH 2205
Office Hours: Fan Chung Graham,
W 2:00-3:00 pm,
CSE 2126.
Olivia Simpson, F 9:30-11:30am, CSE B240A.
Syllabus:
This course 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
is as follows:
-
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.9)
-
Midterm May 6, Wednesday at WLH 2205
-
Weeks 7-8, Chapter 7, Network Flow (covering 7.1-7.3, 7.5-7.10)
We will add a midterm 2, Wednesday May 27 at WLH2205.
Your midterm score will be the maximum of midterm 1 and midterm 2 so that
you do not have to take midterm 2 if you did well at midterm 1 or by choice.
The coverage of midterm 2 will be Chapter 4--7.
-
Week 9 -- 10, Chapter 11, Approximation Algorithms (covering 11.1-11.8)
(Reading: Chapter 8, NP and Computational Intractability )
- Final Exam (take home). The problem set will be handed out June 3 and is due June 9, Tuesday 4--5pm at APM7101. This is a strict deadline. Late paper will not be accepted. Early submissions can be placed under the door of APM7101.
Grading: 4 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 (Wednesday April 15)
Homework #2 (Wednesday April 29)
Homework #3 (Wednesday May 20)
Homework #4 (Wednesday June 3)
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.
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.
Reading
|
Homework
|
Announcements
|Slides