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.

## A few practice final exams

Posted by James on December 6, 2009

Posted in Announcement, Reading | Leave a Comment »

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

- Kleinberg and Tardos, Chapter 8, Problem 5
- Kleinberg and Tardos, Chapter 8, Problem 19
- Kleinberg and Tardos, Chapter 8, Problem 20

**Extra credit**

- Kleinberg and Tardos, Chapter 8, Problem 31

Posted in Homework, Reading | Leave a Comment »

## Uhhh… alternate ring tone?

Posted by James on November 30, 2009

Dan Barrett wrote this song during an Algorithms final exam.

Posted in Extraneous | Leave a Comment »

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

- Kleinberg and Tardos, Chapter 7, Problem 20
- Kleinberg and Tardos, Chapter 7, Problem 23
- Kleinberg and Tardos, Chapter 7, Problem 24 [Hint: Use the solution to Problem 23!]

**Extra credit**

- Kleinberg and Tardos, Chapter 8, Problem 22

Posted in Homework, Reading | Leave a Comment »

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

Posted in Reading | Leave a Comment »

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

- Kleinberg and Tardos, Chapter 6, Problem 27
- Kleinberg and Tardos, Chapter 7, Problems 3, 4, and 5
- Kleinberg and Tardos, Chapter 7, Problem 8

**Extra credit**

- Kleinberg and Tardos, Chapter 7, Problem 19

Posted in Homework, Reading | Leave a Comment »

## Tao’s blog

Posted by James on November 17, 2009

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

Posted in Extraneous | Leave a Comment »

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

**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.

**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.

**Problems**

**Each problem is worth 15 points unless otherwise noted.
**

- Kleinberg and Tardos, Chapter 6, Problem 1
- Kleinberg and Tardos, Chapter 6, Problem 6
- Kleinberg and Tardos, Chapter 6, Problem 8

Posted in Homework, Reading | Leave a Comment »

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

**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.

**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.

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

Posted in Homework | Leave a Comment »