CSE 548-01 (#84542), AMS 542-01 (#84639): Analysis of Algorithms, Fall 2017 (original) (raw)
Lecture Time and Location. MW 7:00 pm - 8:20 pm, Javits Lecture Hall 102, West Campus
Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. MW 5:00 pm - 6: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.
Lecture Schedule.
| Date | Topic | Notes / Reading Material |
|---|---|---|
| Mon, Aug 28 | Introduction | Chapter 3 (Growth of Functions), Introduction to Algorithms (3rd Edition) by Cormen et al. |
| Wed, Aug 30 | Introduction (continued) | - |
| Mon, Sep 4 | No Class(Labor Day) | - |
| Wed, Sep 6 | Introduction (continued) Integer Multiplication & Karatsuba's AlgorithmMatrix Multiplication & Strassen's Algorithm | 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. |
| Mon, Sep 11 | Matrix Multiplication & Strassen's Algorithm (continued) Polynomial Multiplication & the Fast Fourier Transform | 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. |
| Wed, Sep 13 | Polynomial Multiplication & the Fast Fourier Transform (continued) Additional Slides | 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. |
| Mon, Sep 18 | Polynomial Multiplication & the Fast Fourier Transform (continued) | James W. Cooley and John W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series”, Mathematics of Computation, 19(90):297–301, 1965. [fun] Thomas S. Huang, “How the Fast Fourier Transform Got its Name”, Computer, 4(3), page 15, 1971. |
| Wed, Sep 20 | The Master Theorem Akra-Bazzi Recurrences | 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. |
| Mon, Sep 25 | 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. |
| Wed, Sep 27 | Akra-Bazzi Recurrences (continued) | Tom Leighton, “Notes on Better Master Theorems for Divide-and-Conquer Recurrences”, 1996. |
| Mon, Oct 2 | Akra-Bazzi Recurrences (continued) Linear Recurrences with Constant Coefficients (self-study) Generating Functions | Tom Leighton, “Notes on Better Master Theorems for Divide-and-Conquer Recurrences”, 1996. [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. |
| Wed, Oct 4 | Class Canceled | - |
| Mon, Oct 9 | 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, Oct 11 | Exam 1 | - |
| Mon, Oct 16 | Generating Functions (continued) Amortized Analysis | Chapter 17 (Amortized Analysis), Introduction to Algorithms (3rd Edition) by Cormen et al. |
| Wed, Oct 18 | Amortized Analysis (continued) Binomial Heaps | Chapter 6 (Heapsort), Introduction to Algorithms (3rd Edition) by Cormen et al. Jean Vuillemin, “A data structure for manipulating priority queues”, Communications of the ACM, 21(4):309-315, 1978. |
| Mon, Oct 23 | Binomial Heaps (continued) | [optional] Chapter 8 (Binomial Heaps), The Design and Analysis of Algorithms (1992) by Dexter Kozen. |
| Wed, Oct 25 | Binomial Heaps (continued) | [optional] Chapter 19 (Binomial Heaps), Introduction to Algorithms (2nd Edition) by Cormen et al. |
| Mon, Oct 30 | Dijkstra's SSSP & Fibonacci Heaps | Chapter 19 (Fibonacci Heaps), Introduction to Algorithms (3rd Edition) by Cormen et al. |
| Wed, Nov 1 | Dijkstra's SSSP & Fibonacci Heaps (continued) High Probability Bounds and Randomized Algorithms | Michael L. Fredman and Robert E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms”, Journal of the ACM, 34(3):596-615, 1987. |
| Fri, Nov 3 | High Probability Bounds and Randomized Algorithms (continued) | [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. |
| Mon, Nov 6 | 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. |
| Fri, Nov 10 | High Probability Bounds and Randomized Algorithms (continued) | Torben Hagerup and Christine Rüb, “A Guided Tour of Chernoff Bounds”, Information Processing Letters, 33(6), pp. 305-308, 1990. |
| Mon, Nov 13 | High Probability Bounds and Randomized Algorithms (continued) | Chapter 7 (Quicksort), Section 7.4 (Analysis of Quicksort), Introduction to Algorithms (3rd Edition) by Cormen et al. |
| Wed, Nov 15 | High Probability Bounds and Randomized Algorithms (continued) | William Pugh, “Skip lists: a probabilistic alternative to balanced trees”, Communications of the ACM, 33(6):668-676, 1990. |
| Mon, Nov 20 | Analyzing Parallel Algorithms | [optional] Gordon E. Moore, “Cramming more components onto integrated circuits”, Electronics, 38(8), pp. 114-117, April 19, 1965. Chapter 5 (Analytical Modeling of Parallel Programs), Introduction to Parallel Computing (2nd Edition) by Grama et al. |
| Wed, Nov 22 | No Class(Thanksgiving Break) | - |
| Mon, Nov 27 | Analyzing Parallel Algorithms (continued) | Gene Amdahl, “Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities”, Reprinted from the proceedings of the Spring Joint Computer Conference, AIFPS vol 30, pp. 483-485, 1967. Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al. |
| Wed, Nov 29 | Exam 2 | - |
| Fri, Dec 1 | Analyzing Parallel Algorithms (continued) Approximation Algorithms | Chapter 35 (Approximation Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 35 (Approximation Algorithms), Section 35.1 (The Vertex-Cover Problem), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 35 (Approximation Algorithms), Section 35.2 (The Traveling-Salesman Problem), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 35 (Approximation Algorithms), Section 35.2.1 (The Traveling-Salesman Problem with the Triangle Inequality), Introduction to Algorithms (3rd Edition) by Cormen et al. |
| Fri, Dec 1 | Approximation Algorithms (continued) | Chapter 35 (Approximation Algorithms), Section 35.2.1 (The General Traveling-Salesman Problem), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 35 (Approximation Algorithms), Section 35.3 (The Set-Covering Problem), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 35 (Approximation Algorithms), Section 35.5 (The Subset-Sum Problem), Introduction to Algorithms (3rd Edition) by Cormen et al. |
Homeworks.
Old Homeworks.
Exams.
Old Exams.
Additional Resources in SBUCS.