CSE 548-01 (#89599), AMS 542-01 (#89683): Analysis of Algorithms, Fall 2023

CSE 548-01 (#89599), AMS 542-01 (#89683): Analysis of Algorithms, Fall 2023

Lecture Time and Location. Tue/Thu 7:00 pm - 8:20 pm, Frey Hall Room 102, West Campus (classes will be live-streamed with Echo360).

Instructor. Rezaul Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
office hours: Tue/Thu 12:00 pm - 1:30 pm, via Zoom (link available on Brightspace)

Teaching Assistants.

Kiera Gross (kiera.gross{at}stonybrook{dot}edu)
office hours: Mon/Wed 1:00 pm - 2:30 pm, via Zoom
Tianchi (Maverick) Mo (timo{at}cs{dot}stonybrook{dot}edu)
office hours: Tue 2:00 pm - 5:00 pm, NCS 358
Santa Shithil (sshithil{at}cs{dot}stonybrook{dot}edu)
office hours: Fri 4:00 pm - 7:00 pm, via Zoom

Course Description. We will explore techniques for designing and analyzing 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).

Recommended Textbooks.

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

Course Requirements. There will be 4 homework assignments (mainly theory problems) and two in-class exams (the first one on Oct 12 and the second one on Nov 30; 75 minutes each). Each student will be responsible for scribing one lecture. The course grade will be based on the following.

Homework Assignments: 40% (the highest score will be worth 15%, the lowest score will be worth 5%, and the remaining two will be worth 10% each)
Exams: 45% (the higher of the two scores will be worth 30%, and the lower one 15%)
Scribe notes: 10%
Class participation and attendance: 5%

Download the Latex template for scribe notes. You can use the online Latex compiler at www.overleaf.com to create your notes.

Brightspace. Some course documents (e.g., scribe notes, homework solutions, etc.) will be available through Brightspace.

Students with Disabilities. If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact the Student Accessibility Support Center, Stony Brook Union Suite 107, (631) 632-6748, or at sasc@stonybrook.edu. They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential.

Lecture Schedule.

Date	Topic	Notes / Reading Material
Tue, Aug 29	Introduction	VIII Appendix: Mathematical Background, Introduction to Algorithms (4th Edition) by Cormen et al. Chapter 3 (Characterizing Running Times), Introduction to Algorithms (4th Edition) by Cormen et al.
Thu, Aug 31	Introduction (continued)	-
Tue, Sep 5	Introduction (continued)	-
Thu, Sep 7	Introduction (continued) Integer Multiplication & Karatsuba'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.
Tue, Sep 12	Integer Multiplication & Karatsuba's Algorithm (continued) Matrix Multiplication & Strassen's Algorithm	Chapter 2 (Divide-and-Conquer Algorithms), Section 2.1 (Multiplication), Algorithms (1st Edition) by Dasgupta et al. Chapter 4 (Divide-and-Conquer), Section 4.2 (Strassen’s Algorithm for Matrix Multiplication), Introduction to Algorithms (4th Edition) by Cormen et al.
Thu, Sep 14	Matrix Multiplication & Strassen's Algorithm (continued) Polynomial Multiplication & the Fast Fourier Transform	[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. Chapter 30 (Polynomials and the FFT), Introduction to Algorithms (4th Edition) by Cormen et al.
Tue, Sep 19	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.
Thu, Sep 21	Polynomial Multiplication & the Fast Fourier Transform (continued)	[fun] Thomas S. Huang, “How the Fast Fourier Transform Got its Name”, Computer, 4(3), page 15, 1971.
Tue, Sep 26	Polynomial Multiplication & the Fast Fourier Transform (continued)	-
Thu, Sep 28	The Master Theorem	Chapter 4 (Divide-and-Conquer), Section 4.5 (The Master Method for Solving Recurrences), Introduction to Algorithms (4th Edition) by Cormen et al.
Tue, Oct 3	The Master Theorem (continued)	Chapter 4 (Divide-and-Conquer), Section 4.5 (The Master Method for Solving Recurrences), Introduction to Algorithms (3rd Edition) by Cormen et al.
Thu, Oct 5	Akra-Bazzi Recurrences	Chapter 9 (Medians and Order Statistics), Section 9.3 (Selection in Worst-case Linear Time), Introduction to Algorithms (4th Edition) by Cormen et al. Chapter 4 (Divide-and-Conquer), Section 4.7 (Akra-Bazzi Recurrences), Introduction to Algorithms (4th 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.
Tue, Oct 10	No Class (Fall Break)	-
Thu, Oct 12	Midterm Exam 1 (7:05pm - 8:20pm, Frey Hall Room 102)	-
Tue, Oct 17	Akra-Bazzi Recurrences (continued)	Tom Leighton, “Notes on Better Master Theorems for Divide-and-Conquer Recurrences”, 1996.
Thu, Oct 19	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.
Tue, Oct 24	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.
Thu, Oct 26	Generating Functions (continued) Amortized Analysis	Chapter 16 (Amortized Analysis), Introduction to Algorithms (4th Edition) by Cormen et al.
Tue, Oct 31	Binomial Heaps	Chapter 6 (Heapsort), Introduction to Algorithms (4th Edition) by Cormen et al. Jean Vuillemin, “A data structure for manipulating priority queues”, Communications of the ACM, 21(4):309-315, 1978.
Thu, Nov 2	Binomial Heaps (continued)	[optional] Chapter 8 (Binomial Heaps), The Design and Analysis of Algorithms (1992) by Dexter Kozen.
Tue, Nov 7	Binomial Heaps (continued) Dijkstra's SSSP & Fibonacci Heaps	[optional] Chapter 19 (Binomial Heaps), Introduction to Algorithms (2nd Edition) by Cormen et al. Chapter 19 (Fibonacci Heaps), Introduction to Algorithms (3rd Edition) by Cormen et al.
Thu, Nov 9	Dijkstra's SSSP & Fibonacci Heaps (continued)	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.
Tue, Nov 14	Dijkstra's SSSP & Fibonacci Heaps (continued) High Probability Bounds and Randomized Algorithms	Appendix C (Counting and Probability), Introduction to Algorithms (4th Edition) by Cormen et al. [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. [optional] Chapter 1 (Introduction), Section 1.1 (A Min-Cut Algorithm), Randomized Algorithms (1st Edition) by Rajeev Motwani and Prabhakar Raghavan.
Thu, Nov 16	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. [optional] Chapter 1 (Introduction), Section 1.1 (A Min-Cut Algorithm), Randomized Algorithms (1st Edition) by Rajeev Motwani and Prabhakar Raghavan.
Tue, Nov 21	High Probability Bounds and Randomized Algorithms	Torben Hagerup and Christine Rüb, “A Guided Tour of Chernoff Bounds”, Information Processing Letters, 33(6), pp. 305-308, 1990. Chapter 7 (Quicksort), Section 7.4 (Analysis of Quicksort), Introduction to Algorithms (3rd Edition) by Cormen et al. William Pugh, “Skip lists: a probabilistic alternative to balanced trees”, Communications of the ACM, 33(6):668-676, 1990.
Thu, Nov 23	No Class (Thanksgiving Break)	-
Tue, Nov 28	Analyzing Parallel Algorithms	Chapter 5 (Analytical Modeling of Parallel Programs), Introduction to Parallel Computing (2nd Edition) by Grama et al. Chapter 26 (Parallel Algorithms), Introduction to Algorithms (4th Edition) by Cormen et al. [optional] Gordon E. Moore, “Cramming more components onto integrated circuits”, Electronics, 38(8), pp. 114-117, April 19, 1965. 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.
Thu, Nov 30	Midterm Exam 2 (7:05pm - 8:20pm, Frey Hall Room 102)	-
Tue, Dec 5	Analyzing Parallel Algorithms (continued)	-
Thu, Dec 7	Analyzing I/O and Cache Performance	Alok Aggarwal and Jeffrey S. Vitter, “The input/output complexity of sorting and related problems”, Communications of the ACM, 31(9), pp. 1116-1127, 1988. Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran, “Cache-Oblivious Algorithms”, ACM Transactions on Algorithms, 8(1), article 4: 1-22, January 1, 2012. Jeffrey S. Vitter, “Algorithms and Data Structures for External Memory”, Series on Foundations and Trends in Theoretical Computer Science, Now Publishers, Hanover, MA, 2008.

Prerequisites Review Slides (from CSE373/MAT373).

Homework Assignments.

Old Homework Assignments.

Fall 2019: hw1, hw2, hw3, hw4.
Spring 2019: hw1, hw2, hw3, hw4.
Fall 2017: hw1, hw2, hw3, hw4.
Fall 2016: hw1, hw2, hw3, hw4.
Fall 2015: hw1, hw2, hw3, hw4.
Spring 2015: hw1, hw2, hw3, hw4.
Spring 2014: hw1, hw2, hw3, hw4.
Fall 2012: hw1, hw2, hw3, hw4.

Exams.

Old Exams.

Fall 2019: exam 1, exam 2.
Spring 2019: exam 1, exam 2.
Fall 2017: exam 1, exam 2.
Fall 2016: exam 1, exam 2.
Fall 2015: exam 1, exam 2.
Spring 2015: exam 1, exam 2.
Spring 2014: exam 1, exam 2.
Fall 2012: exam 1, exam 2.

Additional Resources in SBUCS.

Algorithms Reading Group Meetings (CSE642: Seminar in Algorithms): This reading group provides a meeting place for Stony Brook faculty, postdocs, and students interested in the analysis of algorithms. We meet every Friday from 11:00 am - 12:15 pm via Zoom, and pose and solve interesting open research problems.