December 4, 2011

## Homework 6 bug fixes

Check out the comments in this post for fixes. In short, they involve question 1 (the $A$ should be $D$), and question 5b (the expression should be $3/2 OPT + 1/2 c(s,t)$).

December 3, 2011

## Course Evaluations

The course evaluations are now open off this page.

I realize they take a little time, but they are super-useful: given the course is a brand-new one, we could really use your feedback to see what we did right and what we didn’t, and to change things around as needed.

November 26, 2011

## Homework 6 posted

For those of you who weren’t in class on Tuesday: Homework #6 is on the webpage. The number of problems you must solve is based on the number of times you scribe for the course.

November 14, 2011

## Lecture 16: Multiplicative Weights

A draft of the Multiplicative Weights lecture notes has been posted.

November 9, 2011

## Homework 5 Due Date

is Tuesday Nov 15th. (Not Thursday Nov 15th, as listed earlier.)

November 9, 2011

## Lecture 14: The Canonical SDP for CSPs

Lecture notes on the Canonical SDP for CSPs are published.

November 6, 2011

## Lecture 13: The Canonical LP for Constraint Satisfaction Problems

Here is a draft of the lecture notes on The Canonical LP for Constraint Satisfaction Problems.

November 2, 2011

## Homework 5 posted

Homework 5 has been released. It’s due Nov 15th.

November 1, 2011

## Homework 3 graded

Homework 3 has been graded. The average was 16. Some comments (the detailed solutions are on the webpage, with the solution to problem 1 to be posted tomorrow).

1. Most of you got this one right. The reason why the binary search solution was not strongly poly-time was that the number of steps depends on the size of the numbers involved.

2. For this one, a few solutions tried proving it from first principles. All these statements can be proved in that way, but the easier way is to prove one version of the Farkas lemma (which you’ve already done in HW2) and then reduce these other versions to that one.

3. No surprises here, nothing to report.

4. Perhaps a majority of the solutions reduced it to standard matching and used Hall/Konig’s theorem to prove this statement. Perfectly kosher, even though I was hoping for the duality-based solution.

We give back the graded HWs 2 and 3 at the end of lecture tomorrow.

October 26, 2011

## Homework Sample Solutions

In case you hadn’t noticed, we’ve been trying to put up sample solutions for the HWs: complete solutions for HW2, and partial solutions for HW3 are now online (I still need to write the solutions for HW3 #1).