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 :))

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.

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

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

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.

Homework 2 consists of problems that are entirely from the textbook. Since many of the problems are rather long and wordy, I thought it better to merely mention the problem numbers, rather than reproducing them in their entirety. However, I know that many of you don’t own the textbook, and use library versions. If you foresee *any* problems in accessing the textbook in order to work on the problems, please let me know as soon as possible, and I can make copies of the problems for you.

Note that the due date is earlier than normal: Oct 5 rather than Oct 8. This is because fall break starts on Oct 6.

The problems are:

1. 4.3 (The UPS problem)
2. 4.9 (Bottleneck spanning trees)
3. 6.1 (Independent sets)
4. 6.6 (Typesetting): This problem dates back to Knuth, who mentions this as one of the problems he faced when designing TeX, (LaTeX is a high-level wrapper for TeX)
5. 6.8 (The Matrix, Reloading…)

Here’s the PDF and LaTeX source for the homework.