CSE 548-01 (#89053), AMS 542-01 (#89139): Analysis of Algorithms, Fall 2019

CSE 548-01 (#89053), AMS 542-01 (#89139): Analysis of Algorithms, Fall 2019

Lecture Time and Location. MW 7:00 pm - 8:20 pm, Harriman Hall 137, West Campus (Prerequisites Review: F 7:00 pm - 8:20 pm, NCS 120, West Campus)

Instructor. Rezaul A. Chowdhury (rezaul{at}cs{dot}stonybrook{dot}edu)
Office Hours. Mon 4:00 pm - 5:00 pm, Fri 6:00 pm - 8:00 pm, NCS 239 (New Computer Science Building)

Teaching Assistants.

Heyi Li (heyi{dot}li{at}stonybrook{dot}edu), office hours: Tue/Thu 2:00 pm - 3:30 pm, NCS 134 (New Computer Science Building)
Zhi Li (zhi{dot}li{dot}5{at}stonybrook{dot}edu), office hours: Tue 3:30 pm - 5:00 pm, Wed 2:00 pm - 3:30 pm, room 2217 (Old Computer Science Building)

Graders.

Harsh Ranjan (hranjan{at}cs{dot}stonybrook{dot}edu)
Sunny Shah (sjshah{at}cs{dot}stonybrook{dot}edu)

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.

Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms (3rd Edition), MIT Press, 2009.
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, but may include some programming assignments, too) and two in-class exams (the first one on Oct 16 and the second one on Dec 2; 75 minutes each). Each student will be responsible for scribing one lecture. The course grade will be based on the following.

Homeworks: 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 paricipation 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.

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

Students with Disabilities. Please check the DSS website for assistance.

Lecture Schedule.

Date	Topic	Notes / Reading Material
Mon, Aug 26	Introduction	Chapter 3 (Growth of Functions), Introduction to Algorithms (3rd Edition) by Cormen et al.
Wed, Aug 28	Introduction (continued)	-
Mon, Sep 2	No Class (Labor Day)	-
Wed, Sep 4	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.
Fri, Sep 6	Prerequisites Review (Correctness of Algorithms) Merge Sort Insertion Sort and Selection Sort	Chapter 2 (Getting Started), Section 2.1 (Insertion Sort), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 2 (Getting Started), Section 2.2 (Analyzing Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 2 (Getting Started), Section 2.3 (Designing Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Sep 9	Integer Multiplication & Karatsuba's Algorithm Matrix 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. Chapter 4 (Divide-and-Conquer), Section 4.2 (Strassen’s Algorithm for Matrix Multiplication), Introduction to Algorithms (3rd Edition) by Cormen et al.
Wed, Sep 11	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 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.
Fri, Sep 13	Prerequisites Review Deterministic Quicksort and Average Case Analysis	Chapter 7 (Quicksort), Section 7.1 (Description of Quicksort), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 7 (Quicksort), Section 7.2 (Performance of Quicksort), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Sep 16	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.
Wed, Sep 18	Class Canceled	-
Fri, Sep 20	Prerequisites Review Heaps and Heapsort	Chapter 6 (Heapsort), Section 6.1 (Heaps), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 6 (Heapsort), Section 6.2 (Maintaining the Heap Property), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Sep 23	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.
Wed, Sep 25	Polynomial Multiplication & the Fast Fourier Transform (continued) The Master Theorem	Chapter 4 (Divide-and-Conquer), Section 4.5 (The Master Method for Solving Recurrences), Introduction to Algorithms (3rd Edition) by Cormen et al.
Fri, Sep 27	Prerequisites Review Heaps and Heapsort (continued)	Chapter 6 (Heapsort), Section 6.3 (Bulding a Heap), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 6 (Heapsort), Section 6.4 (The Heapsort Algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 6 (Heapsort), Section 6.5 (Priority Queues), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Sep 30	The Master Theorem (continued)	Chapter 4 (Divide-and-Conquer), Section 4.6 (Proof of the Master Method), Introduction to Algorithms (3rd Edition) by Cormen et al.
Wed, Oct 2	The Master Theorem (continued) 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.
Fri, Oct 4	Prerequisites Review Dynamic Programming	Chapter 15 (Dynamic Programming), Section 15.1 (Rod Cutting), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Oct 7	Akra-Bazzi Recurrences (continued)	Mohamad Akra and Louay Bazzi, “On the Solution of Linear Recurrence Equations”, Computational Optimization and Applications, 10(2):195–210, 1998. Tom Leighton, “Notes on Better Master Theorems for Divide-and-Conquer Recurrences”, 1996.
Wed, Oct 9	Akra-Bazzi Recurrences (continued) Linear Recurrences with Constant Coefficients (self-study) 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.
Fri, Oct 11	Prerequisites Review Dynamic Programming (continued)	Chapter 15 (Dynamic Programming), Section 15.2 (Matrix-chain Multiplication), Introduction to Algorithms (3rd Edition) by Cormen et al. Rezaul Chowdhury, Pramod Ganapathi, Steven Tschudi, Jesmin Jahan Tithi, Charles Bachmeier, Bradley C. Kuszmaul, Charles E. Leiserson, Armando Solar-Lezama, and Yuan Tang, “AutoGen: Automatic Discovery of Efficient Recursive Divide-&-Conquer Algorithms for Solving Dynamic Programming Problems”, ACM Transactions on Parallel Computing, 4(1):4, 2017.
Mon, Oct 14	No Class (Fall Break)	-
Wed, Oct 16	Exam 1	-
Mon, Oct 21	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 23	Amortized Analysis Binomial Heaps	Chapter 17 (Amortized Analysis), Introduction to Algorithms (3rd Edition) by Cormen et al. 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.
Fri, Oct 25	Prerequisites Review Dynamic Programming (continued)	Chapter 15 (Dynamic Programming), Section 15.3 (Elements of Dynamic Programming), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 15 (Dynamic Programming), Section 15.4 (Longest Common Subsequence), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 15 (Dynamic Programming), Section 15.5 (Optimal Binary Search Trees), Introduction to Algorithms (3rd Edition) by Cormen et al. Rezaul Chowdhury and Vijaya Ramachandran, “Cache-oblivious Dynamic Programming”, Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithm, pp. 591-600, 2006.
Mon, Oct 28	Binomial Heaps (continued)	[optional] Chapter 8 (Binomial Heaps), The Design and Analysis of Algorithms (1992) by Dexter Kozen.
Wed, Oct 30	Binomial Heaps (continued)	[optional] Chapter 19 (Binomial Heaps), Introduction to Algorithms (2nd Edition) by Cormen et al.
Fri, Nov 1	Prerequisites Review Greedy Algorithms	Chapter 16 (Greedy Algorithms), Section 16.1 (An Activity Selection Problem), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 16 (Greedy Algorithms), Section 16.2 (Elements of the Greedy Strategy), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Nov 4	Binomial Heaps (continued) Dijkstra's SSSP & Fibonacci Heaps	Chapter 19 (Fibonacci Heaps), Introduction to Algorithms (3rd Edition) by Cormen et al.
Wed, Nov 6	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.
Fri, Nov 8	Prerequisites Review Greedy Algorithms (continued)	Chapter 23 (Minimum Spanning Trees), Section 23.1 (Growing a Minimum Spanning Tree), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 23 (Minimum Spanning Trees), Section 23.2 (The Algorithms of Kruskal and Prim), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 24 (Single-Source Shortest Paths), Section 24.3 (Dijkstra's Algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al. Mo Chen, Rezaul Chowdhury, Vijaya Ramachandran, David Lan Roche, and Lingling Tong, “Priority Queues and Dijkstra's Algorithm”, UT Austin, Department of Computer Sciences, Technical Report TR-07-54, Oct. 2007.
Mon, Nov 11	Dijkstra's SSSP & Fibonacci Heaps (continued) High Probability Bounds and Randomized Algorithms	Appendix C (Counting and Probability), Introduction to Algorithms (3rd Edition) by Cormen et al.
Wed, Nov 13	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. [optional] Chapter 1 (Introduction), Section 1.1 (A Min-Cut Algorithm), Randomized Algorithms (1st Edition) by Rajeev Motwani and Prabhakar Raghavan.
Fri, Nov 15	Prerequisites Review Greedy Algorithms (continued)	Chapter 26 (Maximum Flow), Section 26.1 (Flow networks), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 26 (Maximum Flow), Section 26.2 (The Ford-Fulkerson method), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Nov 18	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.
Wed, Nov 20	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. William Pugh, “Skip lists: a probabilistic alternative to balanced trees”, Communications of the ACM, 33(6):668-676, 1990.
Fri, Nov 22	Prerequisites Review Greedy Algorithms (continued) More Graph Algorithms: Basic and Beyond	Chapter 26 (Maximum Flow), Section 26.3 (Maximum bipartite matching), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 22 (Elementary Graph Algorithms), Section 22.2 (Breadth-first search), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 22 (Elementary Graph Algorithms), Section 22.3 (Depth-first search), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 22 (Elementary Graph Algorithms), Section 22.4 (Topological sort), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Nov 25	Analyzing Parallel Algorithms	Chapter 5 (Analytical Modeling of Parallel Programs), Introduction to Parallel Computing (2nd Edition) by Grama et al. Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
Wed, Nov 27	No Class (Thanksgiving Break)	-
Mon, Dec 2	Exam 2	-
Wed, Dec 4	Analyzing Parallel Algorithms (continued)	[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.
Fri, Dec 6	Prerequisites Review More Graph Algorithms: Basic and Beyond (continued)	Chapter 22 (Elementary Graph Algorithms), Section 22.5 (Strongly connected components), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 24 (Single-Source Shortest Paths), Section 24.1 (The Bellman-Ford algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 24 (Single-Source Shortest Paths), Section 24.2 (Single-source shortest paths in directed acyclic graphs), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 25 (All-Pairs Shortest Paths), Section 25.1 (Shortest paths and matrix multiplication), Introduction to Algorithms (3rd Edition) by Cormen et al. Chapter 25 (All-Pairs Shortest Paths), Section 25.2 (The Floyd-Warshall algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al.
Mon, Dec 9	Approximation Algorithms (Guest Lecturers: Zhi Li, Harsh Ranjan, Sunny Shah)	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. Chapter 35 (Approximation Algorithms), Section 35.2.2 (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.

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.

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 Wednesday from 11:00 am - 12:30 pm in room 120 of the new CS building, and pose and solve interesting open research problems.