Computer Science 284/484

Advanced Algorithms

Spring 2019

Instructor: Daniel Stefankovic
Class: Tuesday, Thursday 12:30pm-13:45pm, Wilmot 116.
Instructor office hours (Wegmans 2315): Tuesday, Thursday 2pm - 3pm.


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

Other resources/recommended reading (most on a 2 hour reserve in the library):

• [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. Häggström, 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

Jan. 17 Th - Max Flow I

Jan. 22 Tu - Max Flow II
Jan. 24 Th - Max Flow III

homework 1 (max flow) - due Feb. 14

TOPIC 2: Linear Programming

Jan. 29 Tu - Linear Programming I
Jan. 31 Th - Linear Programming II
Feb. 1 Fri - EXTRA CLASS - Linear Programming III

homework 2 (linear programming) - due Feb. 26

Feb. 5 Tu - CLASS CANCELED


TOPIC 3: Computational Geometry

Feb. 7 Th - Computational Geometry I (sweep technique)
Feb. 8 Fri - EXTRA CLASS - Computational Geometry II (convex hulls)

Feb. 12 Tu - CLASS CANCELED
Feb. 14 Th - CLASS CANCELED

Feb. 19 Tu - Computational Geometry III (closest pair of points)
Feb. 21 Th - Computational Geometry IV (Voronoi diagrams)

homework 3 (computational geometry) - due Mar. 19



TOPIC 4: String Algorithms

Feb. 22 Fri - EXTRA CLASS - String Algorithms I (Suffix Trees)

Feb. 26 Tu - String Algorithms II (Suffix Trees)
Feb. 28 Th - String Algorithms III (Suffix Arrays)
Mar. 1 Fri - EXTRA CLASS - String Algorithms IV (Suffix Arrays)

homework 4 (string algorithms) - due Apr. 2

TOPIC 5: Streaming Algorithms

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


Mar. 5 Tu - Probability I
Mar. 7 Th - Probability II

Mar. 12 Tu - SPRING BREAK
Mar. 14 Th - SPRING BREAK

Mar. 19 Tu - Streaming Algorithms I (distinct elements)
Mar. 21 Th - Streaming Algorithms II (sketching)
Mar. 22 Fri - EXTRA CLASS - Streaming Algorithms III (frequency moments)

Mar. 26 Tu - Streaming Algorithms IV

homework 5 (streaming algorithms) - due Apr. 16

TOPIC 6: Markov chain Monte Carlo

reading:
MCMC course (Vigoda); lectures 6,7,8,9,11.


Mar. 28 Th - CLASS CANCELED

Apr. 2 Tu - MCMC I (basics: stationary distribution, detailed balance condition, ergodicity)
Apr. 4 Tu - MCMC II (mixing time)

Apr. 9 Tu - MCMC III (bounds on mixing time)
Apr. 11 Th - MCMC IV (coupling from the past)

homework 6 (MCMC) - due Apr. 30

TOPIC 7: Something Fun

Apr. 16 Tu - TBD
Apr. 18 Th - TBD

Apr. 23 Tu - TBD
Apr. 25 Th - TBD

Apr. 30 Th - CLASS CANCELED

Grading

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

Homework Rules

• Theoretical homework should be typeset (LaTeX preferred) and emailed to the instructor 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 .