CSE 331: Introduction to Algorithm Analysis and Design

Instructor

Atri Rudra

Email:
Phone:	(716) 645-2464
Office:	123 Bell
Office Hours:	MF 2:00- 2:50pm

TAs

Jesse Hartloff

Email:	hartloff "at" buffalo.edu
Office:	Bell 232
Office Hours:	R 1:00-1:50pm

Jiun-Jie Wang

Email:	jiunjiew "at" buffalo.edu
Office:	Bell 232
Office Hours:	T 1:00- 1:50pm and W 2:00- 2:50pm

Class Meetings

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

107 TALBRT

Recitations

Monday, 12:00-12:50pm (06 CLEMEN).

Tuesday, 8:00-8:50am (138 BELL).

Friday, 9:00-9:50am (218 NSC).

Previous Offerings: Fall 09, Fall 10

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 or signing up for email notifications).

Homeworks

Important: Please refer to this document for homework policies.

Homework 0. (Due: Friday, Sep 2 ) [Solutions]
Homework 1. (Due: Friday, Sep 16)
Homework 2. (Due: Friday, Sep 23)
Homework 3. (Due: Friday, Sep 30)
Homework 4. (Due: Friday, Oct 7)
Homework 5. (Due: Friday, Oct 21)
Homework 6. (Due: Friday, Oct 28)
Homework 7. (Due: Friday, Nov 4)
Homework 8. (Due: Friday, Nov 11)
Homework 9. (Due: Friday, Nov 18)
Homework 10. (Due: Friday, Dec 9)

Handouts

Sample mid-term. (September 29)
Solutions to sample mid-term. (October 5)
Sample Final. (November 29)
Solutions to sample final. (December 8)

Textbook

We will be using the following textbook:

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

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

The following references could also be useful

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein, Introduction to Algorithms (2e). (MIT Press, 2001)
Sanjoy Dasgupta, Christos H. Papadimitriou and Umesh Vazirani, Algorithms. (McGraw Hill, 2007)
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)
Richard E. Neapolitan and Kumarss Naimipour, Foundations of Algorithms (4e). (Jones and Bartlett, 2009)

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.5 weeks.
Asymptotic Analysis [KT, Chap 2]-- 1 week.
Graph Basics [KT, Chap 3]-- 2.5 weeks.
Greedy Algorithms [KT, Chap 4]-- 3.5 weeks.
Divide and Conquer Algorithms [KT, Chap 5]-- 2.5 weeks.
Dynamic Programming [KT, Chap 6]-- 2 weeks.
NP-completeness and other advanced topics [KT, Chap 8]-- 1 lecture.

Academic Honesty

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