CSE 331: Introduction to Algorithm Analysis and Design

Instructor

Atri Rudra

Email:
Phone:	(716) 645-2464
Office:	123 Bell Hall
Office Hours:	Wednesdays, 11:00-11:50am Fridays, 2:00-2:50pm

TA

Jeff Delmerico

Email:
Office:	Commons 19 (CSE suite)
Office Hours:	Wednesdays, noon-12:50pm

Class Meetings

Monday, Wednesday, Friday. 1:00-1:50pm.

205 NSC

Recitations

Monday, 9:00-9:50am (120 BALDY).

Monday, 11:00-11:50am (213 NORTON).

Tuesday, 8:00-8:50am (260 CAPEN).

Course Syllabus

Course Blog

We will be using a blog for the course in lieu of a course newsgroup. All announcements will be made on the blog. If you are attending the course, you must check the blog regularly (and consider subscribing to the RSS feed).

Homeworks

Important: Please refer to this document for homework policies.

Homework 1. (Due: Friday, Sep 18)
Homework 2. (Due: Friday, Sep 25)
Homework 3. (Due: Friday, Oct 2)
Homework 4. (Due: Friday, Oct 9 except the last problem, which is due on Oct 16)
Homework 6. (Due: Friday, Oct 30)
Homework 7. (Due: Friday, Nov 6)
Homework 8. (Due: Friday, Nov 13)
Homework 9. (Due: Friday, Nov 20)
Homework 10. (Due: Friday, Dec 11)

Handouts

Syllabus, Feedback form 1. (August 31)
Homework policies. (September 11)
Feedback form 2. (September 16) [Feedback Statistics]
Sample mid-term. (October 7)
Solutions to sample mid-term. (October 10)
Feedback form 3. (October 28)
Sample Final. (December 8)
Solutions to sample final. (December 15)

Textbook

We will be using the following textbook:

Jon Kleinberg and Eva Tardos, Algorithm Design. (Addison-Wesley, 2005)

Occasionally, we will cover topics outside of the textbook: in such cases, supplementary material will be provided.

The following references could also be useful

Donald Knuth, The Art of Computer Programming Volumes 1, 2, 3, 4. (Addison Wesley)
Alfred V. Aho, John E. Hopcroft and Jeffrey Ullman, Data Structures and Algorithms. (Addison Wesley, 1983)
Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein, Introduction to Algorithms (2e). (MIT Press, 2001)

Schedule

We will have roughly 13 weeks worth of classes. Here is a tentative list of topics that we will cover (KT refers to the textbook):

Introduction [KT, Chap 1]-- 1 week.
Asymptotic Analysis [KT, Chap 2]-- 1 week.
Graph Basics [KT, Chap 3]-- 1 week.
Greedy Algorithms [KT, Chap 4]-- 3 weeks.
Divide and Conquer Algorithms [KT, Chap 5]-- 3 weeks.
Dynamic Programming [KT, Chap 6]-- 4 weeks.
NP-completeness and other advanced topics [KT, Chap 8]-- 1 week.

Academic Honesty

We have zero tolerance for cheating and will follow the CSE Department Policies on Academic Integrity.