Home Bookmarks Papers Blog

498 Intro to Randomized Algs

Fall 2019


Tue/Thursday 2pm-3:15pm, SC 1103 .
In course exploder: here.
Acaedemic calendar: pdf.
HWs: HW 1, HW 2, HW 3, HW 4.
Class notes in one big file - updated as the semester continues.
Piazza
Schedule:
  1. Tue, 8/27/19: scribbles
  2. Thu, 8/29/19: notes scribbles
  3. Tue, 9/3/19: notes, scribbles : Quick Sort with high probability, treaps, pairwise independence.
  4. Thu, 9/5/19: k wise independence, scribbles.
  5. Tue, 9/10/19: notes, scribbles: Min Cut.
  6. Thu, 9/12/19: notes, scribbles: Hashing.
  7. Tue, 9/17/19: notes, scribbles: Occupancy.
  8. Thu, 9/19/19: Sampling, scribbles: sampling, quick select, and better selection.
  9. Tue, 9/24/19: Chernoff inequality, [applciations], Cheat sheet, scribbles.
  10. Thu, 9/26/19: routing in parallel computer, scribbles.
  11. Tue, 10/1/19: Closest pair, r-nets, scribbles.
  12. Thu, 10/3/19: Discrepancy and derandomization, scribbles.
  13. Tue, 10/8/19: Dimesnion reduction, scribbles.
  14. Thu, 10/10/19: Streaming, scribbles: reservior sampling, two pass median selection using Chernoff inequality.
  15. Tue, 10/15/19: Independent set (Turan Thereom), Frequency estimation, scribbles.
  16. Thu, 10/17/19: Frequency estimation II: Number of distict elements., scribbles.
  17. Tue, 10/22/19: LSH, scribbles.
  18. Thu, 10/24/19: LSH II, scribbles.
  19. Tue, 10/29/19: Multiplicative weight update, scribbles.
  20. Thu, 10/31/19: VC Dimension, scribbles.
  21. Tue, 11/5/19: eps-net and VC Dimension, scribbles.
  22. Thu, 11/7/19: scribbles.
  23. Tue, 11/12/19: Martingales, Martingales 2: scribbles.
  24. Thu, 11/14/19: Power of two choices scribbles.
  25. Tue, 11/19/19: Partitions scribbles.

Topics still needed to be covered:
  1. Approxiamtion via rounding: Weighted set cover, etc.
  2. Max cut
  3. Power of two choices
  4. Partitions in metric spaces
  5. Learning and VC dimensions

Papers for projects

  1. Hashing:
    1. nju2: Cryptographic sponge functions
    2. dz3: High Speed Hashing for Integers and Strings
  2. poojark2: Net & Prune: pdf.
  3. shal2: Mincut in near linear time: arxiv.
  4. apillai4: Edge estimation: pdf.
  5. tbajpai2: Matchings in d-regular bipartite graphs: arxiv.
  6. yq7: A Small Approximately Min-Wise Independent Family of Hash Functions
  7. selenaj2: Approxiamte distance oracles
  8. davidb2: Improved Approximation Algorithms for Large Matrices via Random Projections
  9. howard28: A constructive proof of the general local lemma
  10. Approximating the permanent
  11. ts6@: Geometric applications of a randomized optimization technique
  12. k-means++: The Advantages of Careful Seeding


Last modified: Tue 2019-11-19 22:05:25 UTC 2019 by Sariel Har-Peled