Algorithms (F2009)

max: 50
min: 20
mean: 43.96
median: 47
variance: 58.52
std-dev: 7.65

Hi all,

I have to skip office hours tomorrow, so I’ll do a replacement office hours on Monday Nov 23 @ 4pm.

This lecture is drawn from multiple sources. The example on estimating the size of a population that has a certain feature is taken from Probability and Computing, Chapter 2, and here are some notes I made for it. I extended the analysis to see what happens if you use a chebyshev bound instead of the chernoff bound: the results are interesting.

The example of MAX SAT, and the ensuing discussion of the probabilistic method, are taken from chapter 13 of the textbook. The probabilistic method is a deep technique that goes well beyond what we saw in class: there’s an entire book on the topic !

The birthday paradox and coupon collector problem are taken from these notes. For an extended discussion of the power of two choices, see the survey by Mitzenmacher, Richa and Sitaraman.

Due Nov 24. PDF and LaTeX.

Hi all,
For those of you who may be trying to shake off the rust when dealing with probability, there are two sources that contain information that might be helpful. The TheoryCS cheat sheet linked in the sidebar has a section (on page 3) concerning basic facts about probabiity (and even has the markov and chebyshev bounds !). Also, the end of Chapter 13 in the book has a review and re-examination of the basics of probability, state spaces and random variables which is worth reading over again.

This comic seems fitting somehow:

The book doesn’t cover the material for today’s lecture in too much detail. These notes have a good summary of what I talked about.

This lecture is not taken from the textbook: notes can be found here - these are drawn from Chapter 7.1-7.2 of the book “Randomized Algorithms” by Motwani and Raghavan.

Due Nov 10. Here’s the PDF and LaTeX

Hi all,
alas, the horror of staring at 6 NP-Complete problems has made me vulnerable to the flu. I won’t be able to do office hours tomorrow, and will hold a makeup next Monday @ 4pm, assuming I’m better by then.