Lecture Time and Location. MW 2:30 pm - 3:50 pm, NCS 120 (New Computer Science Building), West Campus (occasionally in Harriman Hall 104, West Campus)
Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. Mon 4:00 pm - 5:30 pm, Fri 6:00 pm - 7: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, Jan 28 | Introduction |
|
Wed, Jan 30 | Introduction (continued) | - |
Mon, Feb 4 | Integer Multiplication & Karatsuba's Algorithm Matrix Multiplication & Strassen's Algorithm |
|
Wed, Feb 6 | Matrix Multiplication & Strassen's Algorithm |
|
Mon, Feb 11 | Polynomial Multiplication & the Fast Fourier Transform Additional FFT Slides |
|
Wed, Feb 13 | Polynomial Multiplication & the Fast Fourier Transform (continued) |
|
Mon, Feb 18 | Polynomial Multiplication & the Fast Fourier Transform (continued) |
|
Wed, Feb 20 | Polynomial Multiplication & the Fast Fourier Transform (continued) More Additional FFT Slides The Master Theorem |
|
Mon, Feb 25 | The Master Theorem (continued) Akra-Bazzi Recurrences |
|
Wed, Feb 27 | Akra-Bazzi Recurrences (continued) |
|
Mon, Mar 4 | Akra-Bazzi Recurrences (continued) |
|
Wed, Mar 6 | Akra-Bazzi Recurrences (continued) Linear Recurrences with Constant Coefficients (self-study) Generating Functions |
|
Mon, Mar 11 | Generating Functions (continued) |
|
Wed, Mar 13 | Exam 1 | - |
Mon, Mar 18 | Spring Break | - |
Wed, Mar 20 | Spring Break | - |
Mon, Mar 25 | Generating Functions (continued) Amortized Analysis |
|
Wed, Mar 27 | Amortized Analysis (continued) Binomial Heaps |
|
Mon, Apr 1 | Binomial Heaps (continued) |
|
Wed, Apr 3 | The Alpha Technique (Guest Lecturer: Shih-yu Tsai) |
|
Mon, Apr 8 | Binomial Heaps (continued) |
|
Wed, Apr 10 | Binomial Heaps (continued) Dijkstra's SSSP & Fibonacci Heaps |
|
Mon, Apr 15 | Dijkstra's SSSP & Fibonacci Heaps (continued) |
|
Wed, Apr 17 | High Probability Bounds and Randomized Algorithms (continued) |
|
Mon, Apr 22 | High Probability Bounds and Randomized Algorithms (continued) |
|
Wed, Apr 24 | High Probability Bounds and Randomized Algorithms (continued) |
|
Mon, Apr 29 | High Probability Bounds and Randomized Algorithms (continued) Analyzing Parallel Algorithms |
|
Wed, May 1 | Exam 2 | - |
Mon, May 6 | Analyzing Parallel Algorithms (continued) |
|
Wed, May 8 | Approximation Algorithms (Guest Lecturer: Shih-yu Tsai) |
|
Homeworks.
Old Homeworks.
Exams.
Old Exams.
Additional Resources in SBUCS.