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 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 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 Akra-Bazzi Recurrences |
|
Fri, Sep 18 | Akra-Bazzi Recurrences (continued) |
|
Mon, Sep 21 | Akra-Bazzi Recurrences (continued) Linear Recurrences with Constant Coefficients (self-study) 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 | In-class 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 | In-class Exam 2 | - |
Homeworks.
Old Homeworks.
Exams.
Old Exams.
Additional Resources in SBUCS.