Last Words

Thanks all for a great quarter! Your exam grade will be posted on Catalyst shortly, and final grades will be up on your myUW account as soon as they get through the system (most likely a few days). If you would like to pick up the final exam, stop by on Thursday between 10am and 2pm, or email me for an appointment anytime next week. If you have any feedback or questions, please feel free to email me or submit comments through the anonymous feedback form.

Enjoy your break, and hope to see you around soon!

-Elisa

Final Details

General Info:

• Handed out at the end of class on Friday (March 12th)
• Due Wednesday, March 17th, at 6pm in CSE 210. Please slide under my door if I am not there. (NOTE: CS building closes at 6pm!! Don’t be late!!)
• Review Session on Friday (bring or email questions)
• Open book/notes/slides. Closed internet/friends/other texts.

EXACTLY what is on the final:

Solve 5 of the following 6 problems..

1. Solve 2 recurrence relations (upper and lower bound).
   –with and without the master theorem
2. NP completeness proof
3. Given pseudocode for an approximation algorithm, prove the corresponding approximation factor.
4. Write a simple dynamic program.
   –pseudocode only, no proofs
5. Write a simple divide and conquer algorithm.
   –pseudocode only, no proofs
6. True / False questions
   – 5 of them
   – mostly on NP hardness and approximation

Slides: Approximation Algorithms

The first set of slides contains an introduction to coping with NP-Hardness, including algorithms for small vertex covers, and independent sets on trees. Continues with an intro to approximation algorithms, including vertex cover, load balancing, and center selection.

The second set of slides gives reviews the formal definition of an approximation algorithm, and presents several examples related to the traveling salesman problem.

Extra Credit Homework: Dealing with NP-Hardness

Due: Friday, Mar 12th, 2:30pm.

Remember to take a look at the guidelines for writing up solutions.

NOTE: No late days on this assignment. Homework must be turned in on time to get any credit.

YES: this is an optional extra credit assignment! There is no way in which this assignment could hurt your grade — even if you do not do this assignment and everyone else does!

Reading assignment:

• Kleinberg & Tardos, Chapter 10.1-2, 11.1-2
• Approximation Algorithms by Vijay Vazirani, Chapters 1, 3

Problem Set:

1. (30 pts) Kleinberg & Tardos, Chapter 11, Exercise 3. Do not forget to prove correctness (which in this case, means proving that your algorithm is a 2-approximation).
2. (70 points) Consider the Hitting Set problem we saw last week.
   a) Kleinberg & Tardos, Chapter 10, Exercise 1
   b) Prove that the problem in Chapter 11, Exercise 4 is NP-Hard given what you know from question 8.5 (in last week’s homework).
   HINT: This should be super easy!
   c) Kleinberg & Tardos, Chapter 11, Exercise 4

Slides: P vs NP

The first set of slides for Chapter 8 covering polynomial-time reductions, and an introduction to NP and NP-Completeness.

The second set of slides, which includes NP-Completeness proofs for Hamiltonian Cycle, TSP, 3-Color, and Subset-Sum.

Homework 7: P vs NP

Due: Friday, March 5th, 2:30pm.

Remember to take a look at the guidelines for writing up solutions.

Reading assignment:

• Kleinberg & Tardos, Chapter 8
• Listen to this song, written by Dan Barrett during an Algorithms final exam.

Problem Set:

1. (25 pts) Kleinberg & Tardos, Chapter 8, Exercise 1
2. (50 pts) Kleinberg & Tardos, Chapter 8, Exercise 4.
   For this problem please prove NP-completeness when appropriate. However, if the problem is not NP-complete, you need only give pseudocode and runtime analysis for your poly-time algorithm (no proof of correctness is required).
   UPDATE: Please omit 4.c from this question (only turn in a, b, and d).
3. (25 pts) Kleinberg & Tardos, Chapter 8, Exercise 5

Extra Credit:

1. (5 pts) Challenge: Chapter 13 Problem 37
   HINT: Show that SUBSET-SUM STAR-WARS.
2. (3 pts) Application: Find a real world problem where solving it with a polynomial time algorithm would imply that P = NP. You may not use any real world examples from class or the book, but may use NP-complete problems we have discussed. (If you choose to use an NP-complete problem not described in the book or in class you must prove that it is in fact NP-complete).

Reading Ahead

The reading assignments are posted with the homeworks. However, a few of you mentioned you might want to read ahead for lecture. The rough schedule for lectures is as follows (this material, including all previous chapter we have seen, will be on the final):

• Polynomial Reductions (8.1-8.2)
• NP and NP-Completeness (8.3-8.4)
• NP-Complete Problems (8.5-8.8, 8.10)
• Co-NP (8.9)
• Greedy Approximation Algorithms (11.1-11.3)
• The Pricing Method (11.4-11.5)
• Knapsack PTAS (11.8)

Once we finish the above material, time permitting I may look at some topics from chapter 13 or show some algorithmic game theory  – the two major components I use in my research. These topics will just be for fun, and will not be covered on the final.

Disclaimer: The order may change a little, and the official reading assignments may include sections not listed here.

Slides – Divide & Conquer

Here are the slides for the divide and conquer section. This includes mergesort, analyzing recurrence relations, finding the closest pair of points, counting inversions, multiplying polynomials, stooge sort, and the master theorem.

The chapter from CLRS on the Master Theorem is here.

HW 6: Divide and Conquer

Due: Friday, Feb 26th.

Remember to take a look at the guidelines for writing up solutions.

Reading assignment:

• Kleinberg & Tardos, Chapter 5 (except 5.6)
• Uploaded chapter from CLRS on the Master Theorem.

Problem Set:

For the problems from Chapter 5, if the recurrence relation for the asymptotic runtime is one we have seen in class or in problem 1, you may simply reference that result when giving your algorithm’s complexity.

1. (40 pts) Consider the following recurrence relations (assume for all). For each one, state why the Master Theorem does not apply (i.e. which assumption(s) is violated) OR use the Master Theorem to bound the asymptotic runtime. Show your work.
   IMPORTANT: Use the version of the Master Theorem we talked about in class (in the slides).
   a)
   b)
   c)
   d)
   e)
   f)
   g)
   h)
   HINT: The Master Theorem works for three of the relations above.
2. (30 pts) Kleinberg & Tardos, Chapter 5, Exercise 2
3. (30 pts) Kleinberg & Tardos, Chapter 5, Exercise 6. In addition to following the usual grading guidelines, make sure to prove that no more than probes are used.
   HINT: The runtime will also be .

Extra Credit:

1. (5 pts) Challenge: Kleinberg & Tardos, Chapter 5, Exercise 7
   HINT: Show that if you find the minimum on a particular row, then you can query its neighborhood to decide that there must be a local minimum either above or below that row.
2. (3 pts) Application: For many problems, when n is large, the divide and conquer approach is fast, but when n is small, the extra overhead is not worth it. Although there are “software engineering” drawbacks to this, the fastest approach could be to do divide and conquer until n is “small”, and then switch over to a simpler method. Choose a divide and conquer algorithm we have discussed (or another you propose), and discuss where the right switch-over point is (if any).

HW5: What to Turn In

To get full credit, you need to turn in your code (e.g. name.java) under code 1 and code 2 for each part.

The TAs have asked you to turn in several other files, which will greatly speed up their grading process (and was not intended to make your turn in process so painful). I think times have changed since we learned to program and everything was done on the command line (at least this was the case for me), so we did not realize how overwhelming this was going to be. While you do not have to turn this in for full credit, it is always good advice to make your graders as happy as possible. So if you can, please turn in the following files.

– An executable (this will have a .class or .jar extension, and is the compiled version of your code).

– Instead of an executable (or in addition if you want to be extra nice), you can turn in a makefile. If you do not know what a makefile is, or have never written one, don’t worry about it.

– A runfile (titled “runfile”) which contains a the command which would run your compiled code. For example:
java -jar name.jar input.txt output.txt
or whatever you want us to type in to run your code. This should be the ONLY LINE OF TEXT in this file. It does not need to be wrapped with anything else (comments, java code, etc).