Computer Science 284/484

Advanced Algorithms

Fall 2021

Instructor: Daniel Stefankovic
Class: Tuesday, Thursday 12:30pm-13:45pm, Hylan 203.
Instructor office hours: ONLINE (zoom link on blackboard) Monday 9:30pm-10:30pm and Wednesday 9:30pm-10:30pm.


Textbooks: there is no required textbook; see each section for the recommended reading (mostly online; I will also supply handouts).

Other resources/recommended reading:

• [CLRS09] Introduction to Algorithms (3rd edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2009.
• [K91] The Design and Analysis of Algorithms, D. Kozen, 1991.
• [KT05] Algorithm Design, J. Kleinberg and E. Tardos, 2005.
• [AHU74] The Design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ulman, 1974.


• [MU05] Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitzenmacher, E. Upfal, 2005.
• [MR95] Randomized Algorithms, R. Motwani, P. Raghavan, 1995.
• [H02] Finite Markov chains and algorithmic applications, O. Haggstrom, 2002.
• [G97] Counting, sampling and integrating: algorithms and complexity, M. Jerrum, 2003.


• [WS11] The Design of Approximation Algorithms, D.Williamson, D. Shmoys, 2011
• [V04] Approximation Algorithms, V. Vazirani, 2004.


• [BE98] Online Computation and Competitive Analysis, A. Borodin, R. El-Yaniv, 1998.
• [M05] Data Streams: Algorithms and Applications, S. Muthukrishnan, 2005.


• [BCKO08] Computational Geometry: Algorithms and Applications, M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, 2008.
• [PS85] Computational Geometry: An Introduction, F. Preparata, M. Shamos, 1985.
• [M93] Computational Geometry: An Introduction Through Randomized Algorithms, K. Mulmuley, 1993.
• [G97] Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, D. Gusfield, 1997.

Prerequisites: CSC282.

Schedule

TOPIC 1: Max-Flow

Aug. 26 Th - Max Flow I (basics, Ford-Fulkerson, min-cut max-flow)

Aug. 31 Tu - Max Flow II (Edmonds Karp)
Sep. 2 Th - Max Flow III (Push Relabel)



TOPIC 2: Linear Programming/Semidefinite programming

Sep. 7 Tu - Linear Programming I (Basics, duality)
Sep. 9 Th - Linear Programming II (Simplex algorithm I)

Sep. 14 Tu - Linear Programming III (Simplex algorithm II)
Sep. 16 Th - Linear Programming IV (applications)

Sep. 21 Tu - Semidefinite programming I (basics, semidefiniteness, Cholesky decomposition)
Sep. 23 Th - Semidefinite programming II (Max-Cut)

Sep. 28 Tu - Semidefinite programming III (metric embeddings)



TOPIC 3: Computational Geometry

Sep. 30 Th - Computational Geometry I (sweep technique)

Oct. 5 Tu - Computational Geometry II (convex hulls)
Oct. 7 Th - Computational Geometry III (closest pair of points)

Oct. 12 Tu - FALL BREAK (no class)
Oct. 14 Th - Computational Geometry IV (Voronoi diagrams)



TOPIC 4: String Algorithms

Oct. 19 Tu - String Algorithms I (Suffix Trees)
Oct. 21 Th - String Algorithms II (Suffix Trees)

Oct. 26 Tu - String Algorithms III (Suffix Arrays)
Oct. 28 Th - String Algorithms IV (Suffix Arrays)



TOPIC 5: Streaming Algorithms

reading:
Finite Probability Spaces (Babai).
Streaming Algorithms (Chakrabarti), chapters 1-5.


Nov. 2 Tu - Probability I
Nov. 4 Tu - Probability II

Nov. 9 Th - Streaming Algorithms I (distinct elements)
Nov. 11 Tu - Streaming Algorithms II (sketching)

Nov. 16 Tu - Streaming Algorithms III (frequency moments)
Nov. 18 Th - Streaming Algorithms IV



TOPIC 6: Something Fun

Nov. 23 Tu - TBD
Nov. 25 Th - THANKSGIVING (no class)

Nov. 30 Tu - TBD
Dec. 2 Th - TBD

Dec. 7 Tu - TBD

Grading

The grade for the course is based on the homework (theoretical and applied; there will be 6 problem sets); there are no exams.

Homework Rules

• Theoretical homework should be typeset (LaTeX preferred) and submitted on Gradescope by the deadline (specific for each assignment). You may work with other people on the theoretical homework, but you must each write up your solutions separately (without any written aid). If you work with other people, indicate who you worked with on your solution.
  
  
• No late homework will be accepted without instructor's permission (a permission must be requested at least 24 hours before the due date).

This course follows The University Policy on Academic Honesty .