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 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 ).
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 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 Akra-Bazzi Recurrences |
|
Mon, Sep 25 | Akra-Bazzi Recurrences |
|
Wed, Sep 27 | Akra-Bazzi Recurrences (continued) |
|
Mon, Oct 2 | Akra-Bazzi Recurrences (continued) Linear Recurrences with Constant Coefficients (self-study) 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) |
|
Mon, Nov 20 | Analyzing Parallel Algorithms |
|
Wed, Nov 22 | No Class (Thanksgiving Break) |
- |
Mon, Nov 27 | Analyzing Parallel Algorithms (continued) |
|
Wed, Nov 29 | Exam 2 | - |
Fri, Dec 1 | Analyzing Parallel Algorithms (continued) Approximation Algorithms |
|
Fri, Dec 1 | Approximation Algorithms (continued) |
|
Homeworks.
Old Homeworks.
Exams.
Old Exams.
Additional Resources in SBUCS.