Spring 2005
CS 336: Design and Analysis of Algorithms
Department of Computer Science
Northwestern University

9:30--10:45, Tuesday and Thursday
Room 381, 1890 Maple Avenue, Evanston

Copyright (c) 1989--2005 Ming-Yang Kao
(last updated 3/27/2005)

Important Announcements. Please Check Daily.

Problem Set #8 has been posted to the section of Week Assignments below. (5/25/2005)

Synopsis:

This course will discuss fundamental concepts and techniques for designing efficient algorithms and analyzing their performance. Topics include recurrences; sorting and order statistics; dynamic programming; greedy strategies; amortized analysis; advanced data structures; linear programming; efficient reductions and computational hardness.

Instructor:

Professor Ming-Yang Kao
Office: Room 346
Phone: 847-563-0426; Fax: 847-556-0892

Email: kao@cs.northwestern.edu
Class URL: www.cs.northwestern.edu/~kao/cs336-algorithms
Office Hours: 12:00-2:00 Thursday or by appointment (see my general schedule for appointment slots)

Teaching Assistant:

Robbie Schweller (3rd-year Graduate Student)
Office: Room 344
Phone: 847-491-3799

Email: schwellerr@cs.northwestern.edu
Office Hours: 10:45--11:45 Tuesday and Thursday or by appointment

Prerequisites:

CS 310 Mathematical Foundations of Computer Science
CS 311 Data Structures and Data Management

Course Work and Grading Policy:

Your grade will be based on weekly reading assignments (0%), eight weekly problem sets (7.5% each, 60% in total), one midterm examination (15%), and one final examination (25%).

Weekly Reading Assignments: Reading assignments will be posted on the class web page. You are responsible for the materials that are assigned but are not covered in detail or at all in class. Some of such materials are covered in the prerequisite or even earlier courses.
Weekly Problems Sets: Starting the second week, a problem set will be posted on the class web page each Thursday and will be due at the start of class on the following Thursday. You will have one week to work on each problem set. A total of 8 problem sets will be assigned.
Midterm Examination: The midterm examination will be held in class on Tuesday, 5/3/2005.
Final Examination: The final examination will be held in our usual classroom 12:00--2:00 on Friday, 6/10/2005.

Without a Dean's excuse, no late problem set will be accepted, nor will early or make-up examinations be given.

Textbooks:

Required: T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. 2nd Edition, 2001, MIT Press.
Recommended: J. Kleinberg and E. Tardos. Algorithm Design. 2005, Addison Wesley.

Supplemental Course Materials:

Tentative Discussion and Event Schedule:

This schedule is subject to modification. More details will be added as they become available.

Topic 1 (1 meeting): Examples of Efficient Algorithms and Performance Analysis (Chapters 1--3).

Topic 2 (2 meetings): Recurrences (Chapter 4).

Topic 3 (2 meetings): Sorting and Order Statistics (Chapters 7 and 9).

Topic 4 (2 meetings): Dynamic Programming (Chapter 15).

Topic 5 (2 meetings): Greedy Strategies (Chapter 16).

Midterm Examination (1 meeting): Monday, 5/3/2005.

Topic 6 (3 meetings): Amortized Analysis (Chapter 17).

Topic 7 (2 meetings): Advanced Data Structures (Chapters 19 and 21).

Topic 8 (2 meetings): Linear Programming (Chapter 29).

Topic 9 (2 meetings): Efficient Reductions and Computational Hardness (Chapter 34).
Final Examination: The final examination will be held in our usual classroom 12:00--2:00 on Friday, 6/10/2005.

Weekly Assignments:

Week 1.
- Reading Assignment: Chapters 1, 2, and 3 for Thursday's discussion.
- There is no weekly problem set for this Thursday. The first problem set will be assigned next week.
Week 2.
- Reading Assignment: Section 4.3 for Tuesday's discussion; Sections 4.1 and 4.2 for Thursday's.
- Weekly Problem Set #1: posted 8:37PM, 4/6/2005.
Week 3.
- Reading Assignment: Chapter 7 for Tuesday's discussion; Chapter 9 for Thursday's.
- Weekly Problem Set #2: posted 00:06AM, 4/14/2005.
Week 4.
- Reading Assignment: Chapter 15.
- Weekly Problem Set #3: posted 22:41PM, 4/20/2005.
Week 5.
- Reading Assignment: Chapter 16.
- Weekly Problem Set #4: posted 23:00PM, 4/27/2005.
Week 6.
- Reading Assignment: the midterm examination on Tuesday; Sections 17.1 through 17.3 for Thursday's discussion.
- Weekly Problem Set #5: posted 23:00PM, 5/4/2005.
Week 7.
- Reading Assignment: Chapter 17.
- Weekly Problem Set #6: posted 22:12PM, 5/11/2005.
Week 8.
- Reading Assignment: Chapter 19 for Tuesday's discussion; Chapter 21 for Thursday's.
- Weekly Problem Set #7: posted 21:14PM, 5/18/2005.
Week 9.
- Reading Assignment: Chapter 29.
- Weekly Problem Set #8: posted 23:10PM, 5/25/2005.
Week 10.
- Reading Assignment: Chapter 34.

Spring 2005 CS 336: Design and Analysis of Algorithms Department of Computer Science Northwestern University 9:30--10:45, Tuesday and Thursday Room 381, 1890 Maple Avenue, Evanston Copyright (c) 1989--2005 Ming-Yang Kao (last updated 3/27/2005)