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 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).
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 inclass 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  AkraBazzi Recurrences 

Mon, Feb 24  AkraBazzi 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.