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

Homework 3 is now online (pdf, latex). Remember that it is due next Monday, Oct 29.

Some comments:

• In the second problem, you are asked to show that heuristics for a poly-time solvable problem yield 2-approximations. It is not only NP-Complete problems that need approximations. Often, a problem can be solved exactly in polynomial time, but an approximation can be found much faster, and depending on the application, this might be acceptable.
• The final problem is a canonical example of how to prove that the planar version of a problem is NP-Complete: You take the problem, lay it out on the plane, and find some gadget that removes crossings while preserving whatever measure you’re trying to compute. Solving this problem will give you a good idea of how to attack any problem of this kind. A warning though: this problem will take some time, so don’t expect to be able to solve it on Sunday night without spending some time before then !

Update:  I’ve extended the assignment deadline to Oct 31, Wednesday, at 5pm.

The midterm can be found here. Due date is Oct 19 (friday) @ 5pm. LaTeX src (minus the figures: you’ll have to comment those parts out) is here.

Additional notes:

• You may NOT consult your fellow classmates or others. The books are your only friends.
• You may post questions about the midterm as comments on this post. I will be monitoring it frequently.