Lecture Time and Location. TuTh 11:30 am  12:50 pm, Melville Library E4320, West Campus
Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. TuTh 1:30 pm  3:00 pm, 1421 Computer Science Building
Course Description. We will explore techniques for designing and analysing efficient algorithms, including recurrence relations and divideandconquer algorithms, dynamic programming, graph algorithms (e.g., network flow), amortized analysis, cacheefficient and externalmemory algorithms, high probability bounds and randomized algorithms, parallel algorithms and multithreaded computations, NPcompleteness and approximation algorithms, the alpha technique, and FFT ( Fast Fourier Transforms ).
This course is supported by an educational grant from XSEDE (Extreme Science and Engineering Discovery Environment). We will use the computing environment provided by XSEDE for some of the homework problems.
Prerequisites. Some background in algorithms analysis (e.g., CSE 373) and programming languages (e.g., C/C++) is required (or consent of instructor).
Textbooks. Only the first one is required.
Course Requirements. There will be 4 homework assignments (mainly theory problems, but may include some programming assignments, too) and two inclass exams (one midterm, and one final). Each student will be responsible for scribing one lecture. The course grade will be based on the following.
Blackboard. Some course documents (e.g., scribe notes, homework solutions, etc.) will be available through Blackboard. The following documents have already been uploaded.
Lecture Schedule.
Date  Topic  Notes / Reading Material 
Tue, Aug 28  Introduction 

Thu, Aug 30  Introduction ( Continued: Growth of Functions ) Integer Multiplication & Karatsuba's Algorithm 

Thu, Sep 6  Matrix Multiplication & Strassen's Algorithm 

Tue, Sep 11  Polynomial Multiplication & the Fast Fourier Transform 

Thu, Sep 13  Polynomial Multiplication & the Fast Fourier Transform ( Continued ) 

Tue, Sep 18  Some Applications of the Fourier Transform & the Master Theorem 

Thu, Sep 20  AkraBazzi Recurrences 

Tue, Sep 25  AkraBazzi Recurrences ( Continued ) Linear Recurrences with Constant Coefficients 

Thu, Sep 27  Linear Recurrences with Constant Coefficients ( Continued ) Generating Functions 

Tue, Oct 2  Generating Functions ( Continued ) Amortized Analysis 

Thu, Oct 4  Amortized Analysis ( Continued ) Binomial Heaps 

Tue, Oct 9  Binomial Heaps ( Continued ) 

Thu, Oct 11  Binomial Heaps ( Continued ) 

Tue, Oct 16  Midterm Exam   
Thu, Oct 18  Dijkstra's SSSP & Fibonacci Heaps 

Tue, Oct 23  Dijkstra's SSSP & Fibonacci Heaps ( Continued ) 

Thu, Oct 25  The Alpha Technique ( Analyzing UnionFind ) 

Tue, Oct 30  Class Suspended ( Hurricane Sandy )  HW3 out 
Thu, Nov 1  Class Suspended ( Hurricane Sandy )   
Tue, Nov 6  The Alpha Technique ( Continued: Analyzing UnionFind ) 

Thu, Nov 8  The Alpha Technique ( Continued: Partial Sums ) High Probability Bounds and Randomized Algorithms 

Tue, Nov 13  High Probability Bounds and Randomized Algorithms ( Continued: Coloring and MinCut ) 

Thu, Nov 15  High Probability Bounds and Randomized Algorithms ( Continued: Chernoff Bounds ) 

Tue, Nov 20  High Probability Bounds and Randomized Algorithms ( Continued: Quicksort and Skip Lists ) 

Tue, Nov 27  Analyzing Parallel Algorithms 

Thu, Nov 29  Analyzing Parallel Algorithms ( Continued ) 

Tue, Dec 4  Analyzing I/O and Cache Performance 

Thu, Dec 6  Final Exam   
Homeworks.
Exams.