Lecture Time and Location. Tue/Thu 7:00 pm  8:20 pm, Frey Hall Room 102, West Campus (classes will be livestreamed with Echo360).
Instructor.
Rezaul Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
office hours: Tue/Thu 12:00 pm  1:30 pm, via Zoom (link available on Brightspace)
Teaching Assistants.
Course Description. We will explore techniques for designing and analyzing efficient algorithms, including recurrence relations and divideandconquer algorithms, dynamic programming, graph algorithms (e.g., network flow), amortized analysis, cacheefficient and externalmemory algorithms, high probability bounds and randomized algorithms, parallel algorithms and multithreaded computations, NPcompleteness 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).
Recommended Textbooks.
Course Requirements. There will be 4 homework assignments (mainly theory problems) and two inclass exams (the first one on Oct 12 and the second one on Nov 30; 75 minutes each). Each student will be responsible for scribing one lecture. The course grade will be based on the following.
Brightspace. Some course documents (e.g., scribe notes, homework solutions, etc.) will be available through Brightspace.
Students with Disabilities. If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact the Student Accessibility Support Center, Stony Brook Union Suite 107, (631) 6326748, or at sasc@stonybrook.edu. They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential.
Lecture Schedule.
Date  Topic  Notes / Reading Material 
Tue, Aug 29  Introduction 

Thu, Aug 31  Introduction (continued)   
Tue, Sep 5  Introduction (continued)   
Thu, Sep 7  Introduction (continued) Integer Multiplication & Karatsuba's Algorithm 

Tue, Sep 12  Integer Multiplication & Karatsuba's Algorithm (continued) Matrix Multiplication & Strassen's Algorithm 

Thu, Sep 14  Matrix Multiplication & Strassen's Algorithm (continued) Polynomial Multiplication & the Fast Fourier Transform 

Tue, Sep 19  Polynomial Multiplication & the Fast Fourier Transform (continued) 

Thu, Sep 21  Polynomial Multiplication & the Fast Fourier Transform (continued) 

Tue, Sep 26  Polynomial Multiplication & the Fast Fourier Transform (continued)   
Thu, Sep 28  The Master Theorem 

Tue, Oct 3  The Master Theorem (continued) 

Thu, Oct 5  AkraBazzi Recurrences 

Tue, Oct 10  No Class (Fall Break) 
 
Thu, Oct 12  Midterm Exam 1 (7:05pm  8:20pm, Frey Hall Room 102) 
 
Tue, Oct 17  AkraBazzi Recurrences (continued) 

Thu, Oct 19  Generating Functions 

Tue, Oct 24  Generating Functions (continued) 

Thu, Oct 26  Generating Functions (continued) Amortized Analysis 

Tue, Oct 31  Binomial Heaps 

Thu, Nov 2  Binomial Heaps (continued) 

Tue, Nov 7  Binomial Heaps (continued) Dijkstra's SSSP & Fibonacci Heaps 

Thu, Nov 9  Dijkstra's SSSP & Fibonacci Heaps (continued) 

Tue, Nov 14  Dijkstra's SSSP & Fibonacci Heaps (continued) High Probability Bounds and Randomized Algorithms 

Thu, Nov 16  High Probability Bounds and Randomized Algorithms 

Tue, Nov 21  High Probability Bounds and Randomized Algorithms 

Thu, Nov 23  No Class (Thanksgiving Break) 
 
Tue, Nov 28  Analyzing Parallel Algorithms 

Thu, Nov 30  Midterm Exam 2 (7:05pm  8:20pm, Frey Hall Room 102) 
 
Tue, Dec 5  Analyzing Parallel Algorithms (continued)   
Thu, Dec 7  Analyzing I/O and Cache Performance 

Prerequisites Review Slides (from CSE373/MAT373).
Homework Assignments.
Old Homework Assignments.
Exams.
Old Exams.
Additional Resources in SBUCS.