Lecture Time and Location. TuTh 4:00 pm  5:20 pm, Computer Teaching Lab (CS 2120), West Campus
Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. TuTh 12:00 pm  1:30 pm, 1421 Computer Science Building
Teaching Assistants.
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 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  
Tue, Jan 26  All SBU Classes Canceled (Winter Storm)    
Thu, Jan 29  Introduction 


Tue, Feb 3  Integer Multiplication & Karatsuba's Algorithm Matrix Multiplication & Strassen's Algorithm 


Thu, Feb 5  Polynomial Multiplication & the Fast Fourier Transform 


Tue, Feb 10  Polynomial Multiplication & the Fast Fourier Transform (continued) 


Thu, Feb 12  The Master Theorem AkraBazzi Recurrences 


Tue, Feb 17  AkraBazzi Recurrences (continued) 


Thu, Feb 19  AkraBazzi Recurrences (continued) Linear Recurrences with Constant Coefficients 


Tue, Feb 24  Linear Recurrences with Constant Coefficients (continued) Generating Functions 


Thu, Feb 26  Generating Functions (continued) Amortized Analysis 


Tue, Mar 3  Amortized Analysis Binomial Heaps 


Thu, Mar 5  All SBU Classes Canceled (Winter Storm)    
Tue, Mar 10  Binomial Heaps (continued) 


Thu, Mar 12  Inclass Exam 1 (Midterm)    
Tue, Mar 17  Spring Break    
Thu, Mar 19  Spring Break    
Tue, Mar 24  Binomial Heaps (continued) 

 
Thu, Mar 26  Dijkstra's SSSP & Fibonacci Heaps 


Tue, Mar 31  Dijkstra's SSSP & Fibonacci Heaps (continued) 


Thu, Apr 2  High Probability Bounds and Randomized Algorithms 


Tue, Apr 7  High Probability Bounds and Randomized Algorithms ( continued ) 


Thu, Apr 9  High Probability Bounds and Randomized Algorithms ( continued ) 


Tue, Apr 14  Approximation Algorithms ( lecturer: Pramod Ganapathi ) 


Thu, Apr 16  Approximation Algorithms ( lecturer: Pramod Ganapathi ) 


Tue, Apr 21  High Probability Bounds and Randomized Algorithms ( continued ) 


Thu, Apr 23  Analyzing Parallel Algorithms 


Tue, Apr 28  Analyzing Parallel Algorithms ( continued ) 


Thu, Apr 30  Analyzing Parallel Algorithms ( continued ) 


Tue, May 5  Analyzing Parallel Algorithms ( continued ) Analyzing I/O and Cache Performance 


Thu, May 7  Inclass Exam 2   
Lectures on Competitive Programming for Solving Algorithmic Problems. These lectures are delivered by Prof. Yonghui Wu of Fudan University (China) every Friday from 5:00 pm to 7:00 pm in CS 2129 (Advanced Programming Lab). Though the primary goal is to help CSE548/AMS542 students with their extracredit programming problems, the lectures are designed for a more general audience interested in competitive programming for solving algorithmic problems (e.g., ACM ICPC, Topcoder). Prof. Wu was the coach of Fudan University Programming Contest teams from 2001 to 2011. Under his guidance Fudan University won three medals (bronze medal in 2002, silver medal in 2005, and bronze medal in 2010) in ACM ICPC World Finals. He is the current chair of ICPC Asia Programming Contest 1st Training Committee.
Date  Topic  Notes / Reading Material 
Fri, Feb 20  Experiments for Data Structures,
Algorithms and Strategies for Solving Problems based on Programming Contests Programming Skills 
 
Fri, Feb 27  Programming by Tree Structure Simulation 
 
Fri, Mar 6  No meeting (University following Monday schedule)   
Fri, Mar 13  Applications of Binary Trees   
Fri, Mar 20  Spring Break   
Fri, Mar 27  No meeting (University following Monday schedule)   
Fri, Apr 3  Applications of Classical Trees   
Fri, Apr 10  Graph Traversal   
Fri, Apr 17  Algorithms for Minimum Spanning Trees   
Fri, Apr 24  Algorithms for Best Paths   
Fri, May 1  Connectivity and Bipartite Matching   
Fri, May 8  Flow Networks   
Homeworks.
Old Homeworks.
Exams.
Old Exams.
Additional Resources in SBUCS.