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, APM 7101 W 2:00-3:00 pm. 

                      Olivia Simpson, M 9:30-11:30am, CSE B240A. 

Syllabus: 

This course covers two main themes -- basic algorithms and some recent developments on Internet algorithms. 

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.7)
• Midterm May 6, Wednesday at WLH 2205
• 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 (take home). The problem set will be handed out June 3 and is due June 9, Tuesday 5pm.

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 For example, if the best algorithm has running time O(log n) but your algorithm is O(n²), you will only get a very partial score. 

Reading | Homework | Announcements |Slides