Homework #8: Reductions and NP-completeness

Due: Friday, December 11th, in class.

Remember to take a look at the grading guidelines.

Reading assignment: Kleinberg-Tardos, Chapter 8.

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.

1. Kleinberg and Tardos, Chapter 8, Problem 5
2. Kleinberg and Tardos, Chapter 8, Problem 19
3. Kleinberg and Tardos, Chapter 8, Problem 20

Extra credit

1. Kleinberg and Tardos, Chapter 8, Problem 31

Homework #7

Due: Friday, December 4th, in class.

Remember to take a look at the grading guidelines.

Reading assignment: Kleinberg-Tardos, Chapters 7 and 8.

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.

1. Kleinberg and Tardos, Chapter 7, Problem 20
2. Kleinberg and Tardos, Chapter 7, Problem 23
3. Kleinberg and Tardos, Chapter 7, Problem 24 [Hint: Use the solution to Problem 23!]

Extra credit

1. Kleinberg and Tardos, Chapter 8, Problem 22

Homework #6

Due: Wednesday, November 25th, in class.

Remember to take a look at the grading guidelines.

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.

1. Kleinberg and Tardos, Chapter 6, Problem 27
2. Kleinberg and Tardos, Chapter 7, Problems 3, 4, and 5
3. Kleinberg and Tardos, Chapter 7, Problem 8

Extra credit

1. Kleinberg and Tardos, Chapter 7, Problem 19

Homework #5

Due: Wednesday, November 18th, in class.

Remember to take a look at the grading guidelines.

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.

1. Kleinberg and Tardos, Chapter 6, Problem 1
2. Kleinberg and Tardos, Chapter 6, Problem 6
3. Kleinberg and Tardos, Chapter 6, Problem 8

Homework #4

Due: Wednesday, November 4th, in class.

Remember to take a look at the grading guidelines.

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.

1. 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.
   1. for and .
   2. for and .
   3. 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. ]

2. Kleinberg and Tardos, Chapter 5, Problem 2
3. Kleinberg and Tardos, Chapter 5, Problem 5
4. 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

1. 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?

Homework #3: Greedy Algorithms

Due: Wednesday, October 28th in class.

Remember to take a look at the grading guidelines.

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.

1. Kleinberg and Tardos, Chapter 4, Problem 2
2. Kleinberg and Tardos, Chapter 4, Problem 5
3. Kleinberg and Tardos, Chapter 4, Problem 10
4. Kleinberg and Tardos, Chapter 4, Problem 19

Extra credit

1. Kleinberg and Tardos, Chapter 4, Problem 26
2. 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.)

Machiavelli and the Gale-Shapley algorithm

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.

Homework #2

Due: Wednesday, October 21st in class.

Remember to take a look at the grading guidelines.

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.

1. Kleinberg and Tardos, Chapter 3, Problem 4
2. Kleinberg and Tardos, Chapter 3, Problem 6
3. Kleinberg and Tardos, Chapter 3, Problem 9 [HINT: Think about running BFS from s]
4. Kleinberg and Tardos, Chapter 4, Problem 4

Extra credit

1. Kleinberg and Tardos, Chapter 2, Problem 8

Homework #1

Due: Wednesday, October 14th in class.

Remember to take a look at the grading guidelines.

Reading assignment: Kleinberg-Tardos, Chapters 1-2.

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

1. Kleinberg and Tardos, Chapter 1, Problem 3, page 22-23
2. Kleinberg and Tardos, Chapter 1, Problem 5, pages 24-25
3. Kleinberg and Tardos, Chapter 1, Problem 7, pages 26-27  [HINT: Try to set up a stable matching problem that will solve this problem]
4. Kleinberg and Tardos, Chapter 2, Problem 4, pages 67-68
5. Kleinberg and Tardos, Chapter 2, Problem 6, page 68

Extra credit

1. Kleinberg and Tardos, Chapter 1, Problem 8, pages 27-28
2. In class, we saw that it’s possible for a woman to cheat the Gale-Shapley stable marriage algorithm by lying.  Prove that, even if a man knows all the other preferences, he cannot do any better for himself by lying about his true preferences.