Due: Wednesday, January 29th in class.

Remember to take a look at the grading guidelines.

Reading assignment: Kleinberg-Tardos, Chapter 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

  1. In class, we saw how to compute a topological sort of a DAG with a simple algorithm. In this problem, you should modify the recursive DFS algorithm to compute a topological ordering in O(m+n) time. Your algorithm should simply print out a list of nodes in topological order.

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

Extra credit

  1. Suppose you are given a list of n numbers D[1], D[2], ..., D[n]. Design an algorithm that decides whether there exists an undirected graph G=(V,E) whose vertex degrees are precisely D[1], D[2], ..., D[n]. In other words, the graph will have n vertices and the degree of vertex i is D[i]. G should be a simple graph (no multiple edges between the same pair of vertices, and no self-loops). Your algorithm should run in polynomial time, i.e. O(n^c) for some constant c.

  2. Kleinberg Tardos, Chapter 4, Problem 27