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

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.

• Sara Zarandi (sbahaadinibe{at}cs{dot}stonybrook{dot}edu)
Office Hours: TuTh 10:30 am - 12:00 pm, 2110 Computer Science Building
• Laraib Malik (lmalik{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.

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 at the end; 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.

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 Chapter 3 (Growth of Functions), Introduction to Algorithms (3rd Edition) by Cormen et al. Tue, Feb 3 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. [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. Thu, Feb 5 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. Tue, Feb 10 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. Thu, Feb 12 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. Chapter 9 (Medians and Order Statistics), Section 9.3 (Selection in Worst-case Linear Time), Introduction to Algorithms (3rd Edition) by Cormen et al. Tue, Feb 17 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. Thu, Feb 19 Akra-Bazzi Recurrences (continued) Linear Recurrences with Constant Coefficients 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. Tue, Feb 24 Linear Recurrences with Constant Coefficients (continued) Generating Functions [optional] Chapter 7 (Generating Functions), Concrete Mathematics (2nd Edition) by Ronald Graham, Donald Knuth, and Oren Patashnik. Thu, Feb 26 Generating Functions (continued) Amortized Analysis [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. Chapter 17 (Amortized Analysis), Introduction to Algorithms (3rd Edition) by Cormen et al. Tue, Mar 3 Amortized Analysis 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. Thu, Mar 5 All SBU Classes Canceled (Winter Storm) - Tue, Mar 10 Binomial Heaps (continued) [optional] Chapter 8 (Binomial Heaps), The Design and Analysis of Algorithms (1992) by Dexter Kozen. Thu, Mar 12 In-class Exam 1 (Midterm) - Tue, Mar 17 Spring Break - Thu, Mar 19 Spring Break - Tue, Mar 24 Binomial Heaps (continued) [optional] Chapter 19 (Binomial Heaps), Introduction to Algorithms (2nd Edition) by Cormen et al. - Thu, Mar 26 Dijkstra's SSSP & Fibonacci Heaps Chapter 19 (Fibonacci Heaps), Introduction to Algorithms (3rd Edition) by Cormen et al. Tue, Mar 31 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. Thu, Apr 2 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. Tue, Apr 7 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. Torben Hagerup and Christine Rüb, “A Guided Tour of Chernoff Bounds”, Information Processing Letters, 33(6), pp. 305-308, 1990. Thu, Apr 9 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. Tue, Apr 14 Approximation Algorithms ( lecturer: Pramod Ganapathi ) 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. Thu, Apr 16 Approximation Algorithms ( lecturer: Pramod Ganapathi ) 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. Tue, Apr 21 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. Thu, Apr 23 Analyzing Parallel Algorithms [optional] Gordon E. Moore, “Cramming more components onto integrated circuits”, Electronics, 38(8), pp. 114-117, April 19, 1965. Tue, Apr 28 Analyzing Parallel Algorithms ( continued ) Chapter 5 (Analytical Modeling of Parallel Programs), Introduction to Parallel Computing (2nd Edition) by Grama et al. 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, Apr 30 Analyzing Parallel Algorithms ( continued ) Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al. Tue, May 5 Analyzing Parallel Algorithms ( continued ) Analyzing I/O and Cache Performance 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á 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”, Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 285-298, 1999. Jeffrey S. Vitter, “Algorithms and Data Structures for External Memory”, Series on Foundations and Trends in Theoretical Computer Science, Now Publishers, Hanover, MA, 2008. Thu, May 7 In-class 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 extra-credit 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.

• 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:30 pm in CS 2311 (Wireless Seminar Room), and pose and solve interesting research problems.
• Stony Brook Puzzle Society (SBPS): SBPS holds informal sessions on puzzles every week (Fridays, 1:00 – 2:30 pm, CSE 2129). Participants discuss, solve, and learn puzzles in mathematics, algorithms, data structures, programming, and logic. Discussions include puzzles asked in job interviews. Please consider attending.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8136308,"math_prob":0.7676861,"size":4890,"snap":"2019-13-2019-22","text_gpt3_token_len":1259,"char_repetition_ratio":0.14715514,"word_repetition_ratio":0.08791209,"special_character_ratio":0.25501022,"punctuation_ratio":0.14851485,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9633829,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-03-25T10:15:46Z\",\"WARC-Record-ID\":\"<urn:uuid:589ba918-75ea-422d-aa21-7783379a59a5>\",\"Content-Length\":\"25428\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:2cbfce68-16e5-4b6a-8451-6df2b432567e>\",\"WARC-Concurrent-To\":\"<urn:uuid:20fae0f2-f5b4-44bb-8dc5-49b99bba713f>\",\"WARC-IP-Address\":\"130.245.27.3\",\"WARC-Target-URI\":\"http://www3.cs.stonybrook.edu/~rezaul/CSE548-S15.html\",\"WARC-Payload-Digest\":\"sha1:NZSXFSJCYERTO2Y2CLSDYKWKV72DKSYH\",\"WARC-Block-Digest\":\"sha1:NDOWG5HSJNAEH2EGPZEUUWW2TEFGM7YX\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-13/CC-MAIN-2019-13_segments_1552912203865.15_warc_CC-MAIN-20190325092147-20190325114147-00195.warc.gz\"}"}