Lecture Time and Location. MW 7:00 pm  8:20 pm, Javits Lecture Hall 102, West Campus
Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. MW 5:00 pm  6:30 pm, room 239 (New Computer Science Building)
Teaching Assistants.
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 ).
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 toward the end; 75 minutes each). 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.
Students with Disabilities. Please check the DSS website for assistance.
Lecture Schedule.
Date  Topic  Notes / Reading Material 
Mon, Aug 28  Introduction 

Wed, Aug 30  Introduction (continued)   
Mon, Sep 4  No Class (Labor Day) 
 
Wed, Sep 6  Introduction (continued) Integer Multiplication & Karatsuba's Algorithm Matrix Multiplication & Strassen's Algorithm 

Mon, Sep 11  Matrix Multiplication & Strassen's Algorithm (continued) Polynomial Multiplication & the Fast Fourier Transform 

Wed, Sep 13  Polynomial Multiplication & the Fast Fourier Transform (continued) Additional Slides 

Mon, Sep 18  Polynomial Multiplication & the Fast Fourier Transform (continued) 

Wed, Sep 20  The Master Theorem AkraBazzi Recurrences 

Mon, Sep 25  AkraBazzi Recurrences 

Wed, Sep 27  AkraBazzi Recurrences (continued) 

Mon, Oct 2  AkraBazzi Recurrences (continued) Linear Recurrences with Constant Coefficients (selfstudy) Generating Functions 

Wed, Oct 4  Class Canceled   
Mon, Oct 9  Generating Functions (continued) 

Wed, Oct 11  Exam 1   
Mon, Oct 16  Generating Functions (continued) Amortized Analysis 

Wed, Oct 18  Amortized Analysis (continued) Binomial Heaps 

Mon, Oct 23  Binomial Heaps (continued) 

Wed, Oct 25  Binomial Heaps (continued) 

Mon, Oct 30  Dijkstra's SSSP & Fibonacci Heaps 

Wed, Nov 1  Dijkstra's SSSP & Fibonacci Heaps (continued) High Probability Bounds and Randomized Algorithms 

Fri, Nov 3  High Probability Bounds and Randomized Algorithms (continued) 

Mon, Nov 6  High Probability Bounds and Randomized Algorithms (continued) 

Fri, Nov 10  High Probability Bounds and Randomized Algorithms (continued) 

Mon, Nov 13  High Probability Bounds and Randomized Algorithms (continued) 

Wed, Nov 15  High Probability Bounds and Randomized Algorithms (continued) Analyzing Parallel Algorithms 

Mon, Nov 20     
Wed, Nov 22  No Class (Thanksgiving Break) 
 
Mon, Nov 27     
Wed, Nov 29  Exam 2   
Mon, Dec 4     
Wed, Dec 6     
Homeworks.
Old Homeworks.
Exams.
Old Exams.
Additional Resources in SBUCS.