# Design and Analysis of Algorithms

## A few practice final exams

Posted by James on December 6, 2009

Here are a few final exams from past offerings of the course.  They bear some resemblance (in terms of topics covered and difficulty) to the final exam that we’ll have on December 14th.

Practice final #1

Practice final #2

Practice final #3

## Homework #8: Reductions and NP-completeness

Posted by James on December 6, 2009

## 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

## Uhhh… alternate ring tone?

Posted by James on November 30, 2009

Dan Barrett wrote this song during an Algorithms final exam.

## Homework #7

Posted by James on November 28, 2009

## 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

## Reading + in-class flow exercise

Posted by James on November 25, 2009

A few people asked me about the solution to the flow exercise we did in class (with doctors, hospitals, etc.).  That problem was taken from a “Solved Exercise” in Kleinberg-Tardos, Chapter 7 (so you can look there to review the solution).

This week we will be discussing reduction and NP-completeness, so I suggest reading ahead in the slides and Chapter 8.

## Homework #6

Posted by James on November 18, 2009

## 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

## Tao’s blog

Posted by James on November 17, 2009

As mentioned in class today, Terry Tao’s blog.

## Homework #5

Posted by James on November 12, 2009

## 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

## Class exercise solution recap

Posted by James on November 9, 2009

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

$\displaystyle \sum_{v \in A} \sum_{e \textrm{ out of } v} f(e) = \sum_{v \in A} \sum_{e \textrm{ into } v} f(e).$

But notice that for every edge e which does not have s or t as an endpoint, $f(e)$ 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.

## Homework #4

Posted by James on October 29, 2009

## 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 $T(n)$ in each case using $O(\cdot)$ notation. You can assume that everything is rounded down to the nearest integer.
1. $T(n) = 2 T(n/2) + \log_2 n$ for $n > 1$ and $T(1)=1$.
2. $T(n) = \sqrt{n} T(\sqrt{n}) + n$ for $n > 1$ and $T(1)=1$.
3. $T(n) = 2T(n/2) + 4T(n/4) + \sqrt{n}$ for $n > 1$ and $T(1)=1$.

[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?