Lecture Time and Location. MW 7:00 pm  8:20 pm, Harriman Hall (137), 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 29  Introduction 

Wed, Aug 31  Introduction (continued) Integer Multiplication & Karatsuba's Algorithm 

Mon, Sep 5  No Class (Labor Day) 
 
Wed, Sep 7  Integer Multiplication & Karatsuba's Algorithm (continued) Matrix Multiplication & Strassen's Algorithm 

Mon, Sep 12  Polynomial Multiplication & the Fast Fourier Transform 

Wed, Sep 14  Polynomial Multiplication & the Fast Fourier Transform (continued) 

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

Wed, Sep 21  The Master Theorem 

Mon, Sep 26  The Master Theorem (continued) AkraBazzi Recurrences 

Wed, Sep 28  AkraBazzi Recurrences (continued) 

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

Wed, Oct 5  Generating Functions (continued) 

Mon, Oct 10  Generating Functions (continued) Amortized Analysis 

Wed, Oct 12  Exam 1   
Mon, Oct 17  Amortized Analysis (continued) Binomial Heaps 

Wed, Oct 19  Binomial Heaps (continued) 

Mon, Oct 24  Binomial Heaps (continued) 

Wed, Oct 26  Binomial Heaps (continued) Dijkstra's SSSP & Fibonacci Heaps 

Mon, Oct 31  Dijkstra's SSSP & Fibonacci Heaps (continued) 

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

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

Wed, Nov 9  High Probability Bounds and Randomized Algorithms (continued) 

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

Wed, Nov 16  High Probability Bounds and Randomized Algorithms (continued) 

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

Wed, Nov 23  No Class (Thanksgiving Break) 
 
Mon, Nov 28  Approximation Algorithms (continued) 

Wed, Nov 30  Exam 2   
Mon, Dec 5  Approximation Algorithms (continued) Analyzing Parallel Algorithms 

Wed, Dec 7  Analyzing Parallel Algorithms (continued) 

Homeworks.
Old Homeworks.
Exams.
Old Exams.
Additional Resources in SBUCS.