Graduate Algorithms

In the early 80s, there was much excitement in the algorithms community about the idea of parallel machine models. The PRAM (parallel RAM), became the analysis model of choice, and in the lecture today, we’ll start to see the basic theory of parallel complexity as seen on the PRAM. The textbook has no material on parallel algorithms: I drew much material from these lecture notes.

Some additional links that might be useful:

• Flynn’s categorization of machine models.
• Amdahl’s Law.
• P-completeness

The average for this assignment was a shade under 34, much lower than normal.

Max was 50, min was 2, and median score was 38.

When you’ve shown a problem is NP-hard, and designed whatever approximation you can, and still aren’t close to solving a problem to the level needed, heuristics are often the next step.

From an algorithms perspective, what distinguishes a heuristic from an algorithm is the lack of formal guarantees. This deficiency can show up in a variety of ways:

• A heuristic may not have a clear stopping condition
• A heuristic will in general not guarantee any kind of quality of solution (except possibly local optimality)

If that’s the case, why use a heuristic ? Usually, it’s because the problem is too complex to analyse using formal approaches. Also, each problem often requires a completely different method of analysis if we’re looking at formal guarantees. Heuristics provide a generic approach that can “work” on a variety of problems.

Since you can’t usually evaluate a heuristic via formal methods, the questions you ask about a heuristic are usually different:

• What is a good stopping criterion ? This is especially tricky for iterative schemes: usually, you want to stop when the difference between the previous solution and the current one falls below some threshold: choosing that threshold is the hard part.
• Does the heuristic converge in a “reasonable amount of time” ? Many heuristics will make progress very quickly, and spend a lot of time towards the end, as they get closer and closer.
• How good do the solutions look ? You will often find silence on this point, mainly because to evaluate the “goodness” of a solution, you need some kind of lower bound on the optimal solution, which is also hard to find. Often, there are other ways of evaluating the quality of a solution, depending on the domain.

We’ll look at meta-heuristics in this lecture. You can think of meta-heuristics as general design principles that can be instantiated for any specific problem, giving an actual heuristic for that problem. Some examples:

• Local search (also hill climbing, gradient descent)
• The Metropolis algorithm
• Simulated annealing, and some cooling schedules
• Tabu search
• Evolutionary algorithms.

Due date for this homework is Monday Dec 3, at 5pm. Here’s the LaTeX and PDF.

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 (!)

In this lecture, we covered circulations and edges with lower bounds on demands. We also looked at two applications of flows, airline scheduling and image segmentation. All of this material is taken from KT Chapter 7.

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