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 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 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) Akra-Bazzi Recurrences |
|
Wed, Sep 28 | Akra-Bazzi Recurrences (continued) |
|
Mon, Oct 3 | Akra-Bazzi Recurrences (continued) Linear Recurrences with Constant Coefficients (self-study) 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.