Computer Science 284/484
Instructor: Daniel Stefankovic
Class: Tuesday, Thursday 12:30pm-13:45pm, CSB 601.
Instructor office hours (CSB 620): Tuesday, Thursday, 9:00am-10:00am, or by appointment.
TA: Roya Feizi
TA office hours (CSB 603): Monday, Wednesday, 2:00pm-3:00pm, or by appointment.
Textbooks: there is no required textbook; see each section for the recommended reading.
Other resources/recommended reading (most on a 2 hour reserve in the library):
Introduction to Algorithms (3rd edition),
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2009.
Probability and Computing: Randomized Algorithms and
Probabilistic Analysis, M. Mitzenmacher, E. Upfal, 2005.
Randomized Algorithms, R. Motwani, P. Raghavan,
The Design of Approximation Algorithms, D.Williamson, D. Shmoys, 2011
Approximation Algorithms, V. Vazirani, 2004.
The Design and Analysis of Algorithms, D. Kozen,
Algorithm Design, J. Kleinberg and E. Tardos, 2005.
- [AHU74] The Design and Analysis of Computer
Algorithms, A. Aho, J. Hopcroft, J. Ulman, 1974.
- [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.
- [G97] Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology,
D. Gusfield, 1997.
TOPIC: Randomized algorithms
reading: chapters 1,2,3,5, and appendix in [CLRS09], chapters 1,2,3,4,7 in [MU05], chapters 1,3,4,6.1,6.2,6.3,6.4,6.5,7.2,7.3 in [MR95].
Jan. 15 Th - Basics of probability theory, randomized min-cut algorithm.
Jan. 20 Tu - Expectation, coupon collector, randomized quicksort, randomized median.
Jan. 22 Th - Polynomial identity testing (testing matrix product, matchings using Tutte matrix, Isolation Lemma).
Jan. 27 Tu - Monte Carlo, #DNF.
Jan. 29 Th - Concentration inequalities.
Feb. 3 Tu - Balls and Bins.
Feb. 5 Th - Random walks, cover time, hitting time.
Feb. 10 Tu - Markov chains I (basics: stationary distribution, detailed balance condition, ergodicity)
Feb. 12 Th - Markov chains II (mixing time)
Feb. 17 Tu - Markov chains III (bounds on mixing time)
Feb. 19 Th - Markov chains IV (coupling from the past)
TOPIC: Streaming algorithms
reading: Chapters 1,2,3,4 in [M05].
Feb. 24 Tu - Introduction.
Feb. 26 Th - Heavy hitters.
Mar. 1 Mon 8:15pm - 9:45pm - CSB 601 - Review session.
Mar. 3 Tu - Frequency moments.
Mar. 5 Th - MIDTERM
Mar. 10 Tu - SPRING BREAK
Mar. 12 Th - SPRING BREAK
TOPIC: Online Algorithms
reading: Chapters 1,2,3,4,10 in [BE98], chapter 13 in [MR95].
Mar. 17 Tu - Multiplicative weights algorithm.
Mar. 19 Th - Ski rental.
Mar. 24 Tu - Caching, paging, k-server.
reading: chapter 29 in [CLRS09], chapters 21 and 26 in [V04].
Mar. 26 Th - Linear Programming.
Mar. 31 Tu - Semidefinite programming (Max Cut).
Apr . 2 Th - Metric Embeddings.
Apr. 7 Tu - Class cancelled.
Apr. 9 Th - Class cancelled.
Apr. 14 Tu - Sparsest Cut.
TOPIC: Computational Geometry
reading: chapters 1 and 5 in [BCKO08].
Apr. 16 Th - Convex Hulls.
Apr. 21 Tu - k-d trees, range trees.
TOPIC: String Algorithms
reading: chapters 5 and 7 in [G97]
Apr. 23 Th - Suffix trees I.
May. 4 Mon, 8:00pm-9:30pm - Review session.
Apr. 28 Tu - Suffix trees II.
May. 6 Wed - comprehensive FINAL EXAM, 7:15pm, CSB 601.
for the course is the combination of the exam grade
and the homework grade
The midterm contributes 40% to the exam grade; the final exam contributes 60% to the exam grade.
- Theoretical homework is collected on the due date, before class.
- Applied (implementation) homework should be emailed to both TA and the instructor by the deadline (specific for each assignment).
- No late homework will be accepted without instructor's
permission (a permission must be requested at least 24 hours
before the due date).
- 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.
- 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).
- All tests are closed book. No text
or notes, no scratch paper allowed.
This course follows
The University Policy on Academic Honesty