Graduate Algorithms

The much awaited final is here. There are 6 problems, and all must be solved. Each problem is worth 20 points, and I’ll normalize to 100 later on.

The final is due Tuesday Dec 11 @ 5pm. You may submit the solution electronically or physically (if the latter, slide it under my door). As usual, this post will be the clearing house for question, and you can always email me directly.

The LaTeX for the final is here.

Good luck !

The stats for this homework are somewhat skewed because of the fewer number of submissions.

Average: 32.1
Max: 46
Min: 0
Median: 34

Stats for HW4:  Max = 50, Min = 26.5, Average = 39.29, Median = 39.5 (or some number in the interval between 36 and 43, for those of you who were giving me a hard time last week :))

These are questions really about the next incarnation of the class: you’ll of course be able to put in comments in the teaching evals, but I had my own questions:

• I want to introduce a programming element into the class, and came up with a couple of ideas
  • one programming question in each assignment
  • one full assignment with purely programming questions (probably towards the end of the semester)
  • a project (in lieu or in addition to a final) that would involve programming (some kind of web demo/algorithm comparison etc)

  Which of these do you think would be most useful ? Moreover, what languages are you comfortable programming in. A web demo is probably limited to Java/Flash, but other assignments could be in other forms.

• I know of suggestions you’ve made about topics to be covered. How about topics we *did* cover ? Was the distribution of time/progression of material to your liking, or are there things you’d change (”remove this”, “spend more time on that” etc).

Last lecture ! Here are some of the things we covered today:

• I talked about computational geometry and output sensitivity. In particular, I mentioned convex hull algorithms, and how to make them optimally output sensitive.
• Next, we looked at LP-duality, and how the max-flow min cut theorem can be viewed as a special case of general LP-duality
• Online algorithms are fun to think about, especially the rent-buy ski problem, and the parking lot problem.
• Finally, we looked at amortized analysis, and why it’s good to double every time you reallocate a growing array.

Lecture notes for today’s lecture.

I drew on many sources to cobble together material for this lecture.

• Quantum Computing (lecture notes) by Dave Bacon (the Quantum Pontiff)
• Quantum Computation (lecture notes) by Umesh Vazirani
• Quantum Computing and Quantum Information, by Nielsen and Chuang.

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.