Monthly Archives: January 2015

Lecture 7

A couple of comments about today’s lecture: 1) Here’s a nice example (from Michel Goemans’ notes) of an instance where the max-matching is of size 8. Can you find such a matching? Can you find some set such that the … Continue reading

Posted in Uncategorized | Leave a comment

Lecture #5

We didn’t get time to see Fredman’s “trick” after all. What Fredman shows in this paper is the following result: The min-sum product (MSP) of two matrices can be computed using only comparisons. (He uses instead of our .) Using … Continue reading

Posted in Uncategorized | Leave a comment

Homework #2

And it’s on the webpage. 3 problems. Due next Friday. Please ask questions/clarifications here, or in office hours. [Edit: I added in a problem at the end, that you don’t have to submit, but may find interesting to solve if … Continue reading

Posted in Uncategorized | Leave a comment

Lecture #4

Two things I wanted to re-emphasize about today’s lecture: Yu asked, “where does the algorithm use the undirectedness”? The undirectedness was used in the Claim 2 towards the end. In particular, for the first part of the claim, we used … Continue reading

Posted in Uncategorized | Leave a comment

Lecture #3 notes

Just to clarify, today in lecture we only showed that for every non-negative cost function, there is an optimal solution to the LP that is an r-arborescence. It is not true if we allow negative costs, because nothing in our … Continue reading

Posted in Uncategorized | Leave a comment

Office Hours

I’ve put down my office hours for Monday 3-4pm. However, since next Monday is MLK Day, this week I’ll have office hours Friday — the day after tomorrow at 3-4pm (right after class).

Posted in Uncategorized | Leave a comment

Lecture #2

Today we used the fact that we could preprocess a tree in linear time, so that we could answer least-common ancestor (LCA) queries on constant time. This was a theorem of Harel and Tarjan. However, suppose we are given the … Continue reading

Posted in Uncategorized | Leave a comment