Computer Science 284/484
Advanced Algorithms
Spring 2018
Instructor: Daniel Stefankovic
Class: Tuesday, Thursday 12:30pm-13:45pm, Wilmot 116.
Instructor office hours (Wegmans 2315): Tuesday, Thursday 2pm - 3pm.
TAs:
Jackson Abascal, Zachary Polansky
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
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 both TAs and 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.
- Applied (implementation) homework should be submitted to the automatic grading system before the deadline (specific for each assignment). You must work alone on the applied (implementation) homework. Do not discuss the problem with anybody (except me), do not search for a solution online, do not use any written material when writing any part of the code (for example, no copy-paste, no open textbook when writing code, no reediting of an old source file from an old project, etc).
- 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 .