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 divide-and-conquer algorithms, dynamic programming, graph algorithms (e.g., network flow), amortized analysis, cache-efficient and external-memory algorithms, high probability bounds and randomized algorithms, parallel algorithms and multithreaded computations, NP-completeness 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 in-class 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 | Akra-Bazzi Recurrences |
|
| Tue, Sep 25 | Akra-Bazzi 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 Union-Find ) |
|
| Tue, Oct 30 | Class Suspended ( Hurricane Sandy ) | HW3 out |
| Thu, Nov 1 | Class Suspended ( Hurricane Sandy ) | - |
| Tue, Nov 6 | The Alpha Technique ( Continued: Analyzing Union-Find ) |
|
| 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 Min-Cut ) |
|
| 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.