Graduate Algorithms

For this lecture, I’ll be telling you a story of rearranging the genome, and the influence of algorithms. The tale is told by Brian Hayes, in an article for American Scientist.

To play a Flash game on signed permutations, click here.

Extra material:

• The only paper Bill Gates ever published. (and it’s on pancake flipping)
• A pancake-flipping applet.
• Even more on pancake sorting.

We covered the section on global min cuts in the textbook. In addition, I talked about Chernoff bounds as a method for amplifying the probability of success of an algorithm. Here are some notes on this topic.

I also talked about the power of two choices: the idea that when placing balls in bins, merely choosing two locations at random and picking the better one can lead to an exponential improvement in the maximum load of a bin (from $latex \log{n}$ to $latex \log\log{n}$). A nice survey that reviews this idea (and gives three different proofs of the main theorem) can be found here.

For this lecture, we will be covering section 13.9 and 13.10 from the textbook. However, we will also consider simpler tail bounds. Some lecture notes on this topic can be found here.

Various books have decent coverage of Markov and Chebyshev bounds: the textbook does NOT cover these bounds.The notes I linked above cover the bounds, but not the specific examples relating to occupancy. I have to update my notes, and in the meantime, you can get more information from these notes.

Two useful textbooks for randomized algorithms in general are:

• Randomized Algorithms by Motwani and Raghavan
• Probability and Computing by Mitzenmacher and Upfal.

Max was 50, min was 30. Average is 43.25 and the median is 47 (!)

Due Wednesday Nov 21 (the day before Thanksgiving). LaTeX and PDF

The material in this lecture is drawn exclusively from KT Chapter 7.13

Perhaps the most important theorem in the study of flows is the max-flow min-cut theorem, which we will study in today’s lecture. In addition, we will also see an example application of flows to computing a maximum matching in a bipartite graph, and we will look at more efficient (and polynomial time) algorithms for computing max flows.

Additional reading: Some of the material covered today is best explained in these notes.

Aftermatter:

• Uri Zwick’s website: Presentation on Jenga, and the paper.
• An article by Brian Hayes that explains the result on stacking bricks.

Bondy and Murthy wrote a classic text on graph theory many years ago, and the book is now available online (scanned). If you are interested in a textbook on basic graph theory (that covers many of the basic graph structures we talk about in class), then this is a good reference to have.

The link is http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html