Lecture Time and Location. MoWe 2:30 pm - 3:50 pm, Humanities 1003, West Campus
Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. MoWe 11:30 am - 1:00 pm, 1421 Computer Science Building
TA. Oleksii Starov (ostarov{at}cs{dot}stonybrook{dot}edu)
Office Hours. TuTh 10:00 am - 11:30 am, 1207 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 ).
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.
Lecture Schedule.
Date | Topic | Notes / Reading Material |
Mon, Jan 27 | Introduction Integer Multiplication & Karatsuba's Algorithm |
|
Wed, Jan 29 | Matrix Multiplication & Strassen's Algorithm |
|
Mon, Feb 3 | All SBU Classes Canceled (Winter Storm) | - |
Wed, Feb 5 | All SBU Classes Canceled (Winter Storm) | - |
Mon, Feb 10 | Polynomial Multiplication & the Fast Fourier Transform |
|
Wed, Feb 12 | Polynomial Multiplication & the Fast Fourier Transform (continued) |
|
Mon, Feb 17 | The Master Theorem |
|
Wed, Feb 19 | Akra-Bazzi Recurrences |
|
Mon, Feb 24 | Akra-Bazzi Recurrences (continued) |
|
Wed, Feb 26 | Linear Recurrences with Constant Coefficients Generating Functions |
|
Mon, Mar 3 | Generating Functions (continued) |
|
Wed, Mar 5 | Amortized Analysis Binomial Heaps |
|
Mon, Mar 10 | Binomial Heaps ( continued: covered binary heaps ) |
|
Wed, Mar 12 | Midterm Exam | - |
Mon, Mar 24 | Binomial Heaps ( continued ) |
|
Wed, Mar 26 | Binomial Heaps ( continued ) |
|
Mon, Mar 31 | Dijkstra's SSSP & Fibonacci Heaps |
|
Wed, Apr 2 | Dijkstra's SSSP & Fibonacci Heaps ( continued ) |
|
Mon, Apr 7 | High Probability Bounds and Randomized Algorithms |
|
Wed, Apr 9 | High Probability Bounds and Randomized Algorithms ( continued ) |
|
Mon, Apr 14 | High Probability Bounds and Randomized Algorithms ( continued ) |
|
Wed, Apr 16 | High Probability Bounds and Randomized Algorithms ( continued ) |
|
Mon, Apr 21 | Analyzing Parallel Algorithms |
|
Wed, Apr 23 | Analyzing Parallel Algorithms ( continued ) |
|
Mon, Apr 28 | Analyzing Parallel Algorithms ( continued ) |
|
Wed, Apr 30 | Analyzing Parallel Algorithms ( continued ) |
|
Mon, May 5 | Analyzing I/O and Cache Performance |
|
Wed, May 7 | Analyzing I/O and Cache Performance ( continued ) |
|
Mon, May 12 | Final Exam | - |
Homeworks.
Exams.