CSE 548-01 (#84542), AMS 542-01 (#84639): Analysis of Algorithms, Spring 2014

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.

  1. Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms (3rd Edition), MIT Press, 2009.
  2. Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms (1st Edition), McGraw-Hill, 2006.
  3. Jon Kleinberg and Éva Tardos. Algorithm Design (1st Edition), Addison Wesley, 2005.
  4. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms (1st Edition), Cambridge University Press, 1995.
  5. Vijay Vazirani. Approximation Algorithms, Springer, 2010.
  6. Joseph JáJá. An Introduction to Parallel Algorithms (1st Edition), Addison Wesley, 1992.

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.

Download the Latex template for scribe notes.

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
  • Chapter 3 (Growth of Functions), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • Chapter 2 (Divide-and-Conquer Algorithms), Section 2.1 (Multiplication), Algorithms (1st Edition) by Dasgupta et al.
  • [optional] Anatolii A. Karatsuba, “The Complexity of Computations”, Proceedings of the Steklov Institute of Mathematics, 211:169-183, 1995.
Wed, Jan 29 Matrix Multiplication & Strassen's Algorithm
  • Chapter 4 (Divide-and-Conquer), Section 4.2 (Strassen’s Algorithm for Matrix Multiplication), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • [optional] Chapter 9 (Algebraic and Numeric Algorithms), Section 9.5.2 (Strassen’s Algorithm), Introduction to Algorithms - A Creative Approach (1st Edition) by Udi Manber.
  • Volker Strassen, “Gaussian Elimination is not Optimal”, Numerische Mathematik, 13:354-356, 1969.
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
  • Chapter 2 (Divide-and-Conquer Algorithms), Section 2.6 (The Fast Fourier Transform), Algorithms (1st Edition) by Dasgupta et al.
  • Chapter 30 (Polynomials and the FFT), Introduction to Algorithms (3rd Edition) by Cormen et al.
Wed, Feb 12 Polynomial Multiplication & the Fast Fourier Transform (continued)
Mon, Feb 17 The Master Theorem
  • Chapter 4 (Divide-and-Conquer), Section 4.5 (The Master Method for Solving Recurrences) and Section 4.6 (Proof of the Master Method), Introduction to Algorithms (3rd Edition) by Cormen et al.
Wed, Feb 19 Akra-Bazzi Recurrences
  • Chapter 9 (Medians and Order Statistics), Section 9.3 (Selection in Worst-case Linear Time), Introduction to Algorithms (3rd Edition) by Cormen et al.
  • Mohamad Akra and Louay Bazzi, “On the Solution of Linear Recurrence Equations”, Computational Optimization and Applications, 10(2):195–210, 1998.
Mon, Feb 24 Akra-Bazzi Recurrences (continued)
Wed, Feb 26 Linear Recurrences with Constant Coefficients
Generating Functions
  • [optional] Chapter 7 (Advanced Counting Techniques), Section 7.2 (Solving Linear Recurrence Relations), Discrete Mathematics and its Applications (6th Edition) by Kenneth Rosen.
  • [optional] Chapter 7 (Generating Functions), Concrete Mathematics (2nd Edition) by Ronald Graham, Donald Knuth, and Oren Patashnik.
Mon, Mar 3 Generating Functions (continued)
  • [optional] Chapter 10 (Ordinary Generating Functions), Section 10.3 (Manipulating Generating Functions), Example 10.12 (The Average Time for Quicksort), Foundations of Combinatorics with Applications by Edward A. Bender and S. Gill Williamson.
Wed, Mar 5 Amortized Analysis
Binomial Heaps
  • Chapter 17 (Amortized Analysis), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Mar 10 Binomial Heaps
( continued: covered binary heaps )
  • Chapter 6 (Heapsort), Introduction to Algorithms (3rd Edition) by Cormen et al.
Wed, Mar 12 Midterm Exam -
Mon, Mar 24 Binomial Heaps ( continued )
Wed, Mar 26 Binomial Heaps ( continued )
  • [optional] Chapter 8 (Binomial Heaps), The Design and Analysis of Algorithms (1992) by Dexter Kozen.
  • [optional] Chapter 19 (Binomial Heaps), Introduction to Algorithms (2nd Edition) by Cormen et al.
Mon, Mar 31 Dijkstra's SSSP & Fibonacci Heaps
  • Chapter 19 (Fibonacci Heaps), Introduction to Algorithms (3rd Edition) by Cormen et al.
Wed, Apr 2 Dijkstra's SSSP & Fibonacci Heaps ( continued )
Mon, Apr 7 High Probability Bounds and Randomized Algorithms
  • [optional] Chapter 6 (Algorithms Involving Sequences and Sets), Section 6.9.2 (A Coloring Problem), Introduction to Algorithms - A Creative Approach (1st Edition) by Udi Manber.
Wed, Apr 9 High Probability Bounds and Randomized Algorithms ( continued )
  • [optional] Chapter 1 (Introduction), Section 1.1 (A Min-Cut Algorithm), Randomized Algorithms (1st Edition) by Rajeev Motwani and Prabhakar Raghavan.
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 )
  • Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
Wed, Apr 30 Analyzing Parallel Algorithms ( continued )
  • Chapter 2 (Basic Techniques), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
  • Chapter 9 (Randomized Algorithms), Section 9.6.3 (A Parallel Randomized Quicksort Algorithm), An Introduction to Parallel Algorithms (1992) by Joseph JáJá
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.