Lecture Time and Location. MoFr 1:00 pm  2:20 pm, Earth & Space Sciences Building (069), West Campus
Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. Mo 11:00 am  12:30 pm, Fr 3:00 pm  4:30 pm, Room 239 (New Computer Science Building)
Grader. Srikant Aggarwal (sraggarwal{at}cs{dot}stonybrook{dot}edu)
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 at 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.
Lecture Schedule.
Date  Topic  Notes / Reading Material 
Mon, Aug 24  Introduction 

Fri, Aug 28  Introduction (continued) Integer Multiplication & Karatsuba's Algorithm 

Mon, Aug 31  Integer Multiplication & Karatsuba's Algorithm (continued) Matrix Multiplication & Strassen's Algorithm 

Fri, Sep 4  Polynomial Multiplication & the Fast Fourier Transform 

Mon, Sep 7  No Class (Labor Day)   
Fri, Sep 11  Polynomial Multiplication & the Fast Fourier Transform (continued) 

Mon, Sep 14  The Master Theorem AkraBazzi Recurrences 

Fri, Sep 18  AkraBazzi Recurrences (continued) 

Mon, Sep 21  AkraBazzi Recurrences (continued) Linear Recurrences with Constant Coefficients (selfstudy) Generating Functions 

Fri, Sep 25  Generating Functions (continued) 

Mon, Sep 28  Amortized Analysis 

Fri, Oct 2  Amortized Analysis (continued) Binomial Heaps 

Mon, Oct 5  Binomial Heaps (continued) 

Fri, Oct 9  Binomial Heaps (continued) 

Mon, Oct 12  Inclass Exam 1 (Midterm)   
Fri, Oct 16  Binomial Heaps (continued) Dijkstra's SSSP & Fibonacci Heaps 

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

Fri, Oct 23  Dijkstra's SSSP & Fibonacci Heaps (continued) High Probability Bounds and Randomized Algorithms 

Mon, Oct 26  High Probability Bounds and Randomized Algorithms (continued) 

Fri, Oct 30  High Probability Bounds and Randomized Algorithms (continued) 

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

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

Mon, Nov 9  Approximation Algorithms 

Fri, Nov 13  Approximation Algorithms (continued) 

Mon, Nov 16  Approximation Algorithms (continued) 

Fri, Nov 20  Approximation Algorithms (continued) 

Mon, Nov 23  Analyzing Parallel Algorithms 

Fri, Nov 26  No Class (Thanksgiving Break)   
Mon, Nov 30  Analyzing I/O and Cache Performance 

Fri, Dec 4  Inclass Exam 2   
Homeworks.
Old Homeworks.
Exams.
Old Exams.
Additional Resources in SBUCS.