Reading assignment: Kleinberg-Tardos, Chapters 6 and 7.
In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that you are required to write up the solutions by yourself. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.
The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.
Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.
A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.
Problems
Each problem is worth 15 points unless otherwise noted.
Kleinberg and Tardos, Chapter 6, Problem 27
Kleinberg and Tardos, Chapter 7, Problems 3, 4, and 5
Reading assignment: Kleinberg-Tardos, Chapters 6 and 7.
In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that you are required to write up the solutions by yourself. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.
The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.
Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.
A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.
Problems
Each problem is worth 15 points unless otherwise noted.
In class today, the exercise was to prove that the flow out of s equals to the flow into t in any valid flow network. Someone cleverly proposed the following solution.
First, let A be the set of all nodes except s and t. Then by the flow conversation constraint, we have
But notice that for every edge e which does not have s or t as an endpoint, appears on both sides (since it goes into one node and comes out of one node). Canceling off all these terms, on the left hand side we are left with the flow into t, and on the right hand side, the flow out of s, proving that the two are equal.
In the next class (on Friday), we’ll see a generalization of this lemma, which will be the basis of our algorithms for computing minimum s-t cuts.
Reading assignment: Kleinberg-Tardos, Chapters 5 and 6.
In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that you are required to write up the solutions by yourself. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.
The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.
Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.
A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.
Problems
Each problem is worth 10 points unless otherwise noted.
Solve each of the following recurrences to get the best asymptotic bounds you can on in each case using notation. You can assume that everything is rounded down to the nearest integer.
for and .
for and .
for and .
[Hint: You can't use the Master Theorem for Divide and Conquer recurrences directly since the proof assumed that a and b were constants. Howeover you can look at the way we proved the Master Theorem - figure out the number of subproblems per level and the cost per subproblem. If that starts to look too ugly, maybe you can relate the cost to a similar recurrence that you can analyze using ther Master Theorem. ]
Kleinberg and Tardos, Chapter 5, Problem 2
Kleinberg and Tardos, Chapter 5, Problem 5
Modify Karatsuba’s algorithm based on splitting the polynomials into 3 pieces instead of two. Base your algorithm on a method for multiplying two degree 2 polynomials that uses 6 multiplications. What is the running time of this algorithm? How does the running time of your new algorithm compare to that of Karatsuba’s algorithm?
Extra credit
Show how to multiply two degree 2 polynomials using only 5 multiplications. If you use this in a modified version of Karatsuba’s algorithmi what running time would you get?
I mentioned in class that there was a group-theoretic approach to matrix multiplication in -time developed by Cohn and Umans. This followup paper is able to obtain an -time algorithm using the Cohn-Umans framework.
Reading assignment: Kleinberg-Tardos, Chapters 4 and 5.
In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that you are required to write up the solutions by yourself. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.
The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.
Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.
A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.
Problems
Each problem is worth 10 points unless otherwise noted.
Kleinberg and Tardos, Chapter 4, Problem 2
Kleinberg and Tardos, Chapter 4, Problem 5
Kleinberg and Tardos, Chapter 4, Problem 10
Kleinberg and Tardos, Chapter 4, Problem 19
Extra credit
Kleinberg and Tardos, Chapter 4, Problem 26
Prove that the following variant of Prim’s algorithm works: At every step, choose any edge of minimal cost crossing the current cut S, and add it to the current tree. (The algorithm we analyzed in class required choosing an ordering on all edges of the same weight, and then picking an edge of minimum weight, where ties are broken according to the ordering.)
For those of you who thought about extra credit problem #2, you’ll see that a full proof is perhaps not so easy to come by. You can see the solution in this paper by Dubins and Freedman.
In general, it’s annoying when your cell phone goes off in class, but just to be safe, you should have a cool ring tone to cover yourself. Here’s my suggestion from earlier.
Reading assignment: Kleinberg-Tardos, Chapters 3 and 4.
In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that you are required to write up the solutions by yourself. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.
The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.
Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.
A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.
Problems
Each problem is worth 10 points unless otherwise noted.
Kleinberg and Tardos, Chapter 3, Problem 4
Kleinberg and Tardos, Chapter 3, Problem 6
Kleinberg and Tardos, Chapter 3, Problem 9 [HINT: Think about running BFS from s]
appears on both sides (since it goes into one node and comes out of one node). Canceling off all these terms, on the left hand side we are left with the flow into t, and on the right hand side, the flow out of s, proving that the two are equal.
in each case using 
notation. You can assume that everything is rounded down to the nearest integer.
for 
and 
.
for 
for 
-time developed by 
-time algorithm using the Cohn-Umans framework.