- Clarifications of Problem Set 4.
- In problem 1 you should assume for both parts that d(v) is finite for all nodes v. However, you may NOT assume that G has no negative cycles (though if there are negative cycles, than some d's should have been negative infinity, so the finite values given must be wrong.
- Problem 4. You may assume a tree-decomposition is given. Or you may write: I use the algorithm in the book to find a tree decomposition.

- Clarifications of Problem Set 1.

- In problem 1 in the arborescence questions, all arborescences have the same root r, where node r is part of the input.
- In problem 2. There are two natural interpretations of the greedy algorithm for greedoids. The issue is this. Suppose at some point you consider an element v (the largest weight at the moment), and do not succeed in adding v to the independent set. Do we later try to add v? In matroids, once v cannot be added to an independent set X, it also cannot be added to any set Y containing X, but this is not true for greedoids. The more interesting version of the question allows the greedy algorithm to consider the same element for addition multiple times. To be precise, here is the algorithm:Start I = emtyset

While something can be added to I

find the element x notin I such that

I+x is independent

and x has as high weight as possible

add x to I

Endwhile

I would like you to solve problem 2 for this more interesting version, though we will assign fairly large credit for the easier, less interesting version.

- The third problem set is due Friday,
October 10th. Click here if you prefer to have it in pdf
format. The file has been updated to fix two
typos: a sentence in Problem 1b, and the figure that goes with Problem 3.
- Question 1b we start from a tree T. Let S be the subset
of elements that we issue search(x), delete(x), or insert(x) operations.
The assumption is that |S|=n, that is, out of the N elements in the tree
only a small subset S is relevant in the sense that it occurs in a query.
The claim is that if the number of operations, m is high enough, then
the total time for the sequence of m queries can be bounded by O(m log
n) even if the total number of elements in the tree is much higher than
n.
- It is a good start to think about the case with no insert or delete (that is all we do is splay(x)), and we issue a splay(x) for each x in S as the first n queries. More generally, inactive nodes may become active later (as long as the total number of active nodes does not exceed n), and we may also use insert and delete operations.

- in Question 4 one has to be more careful with the push operations. We want it to be the case that once a phase with a given Delta terminates, and we divide Delta by 2, we never have to go back to the Delta phase, that is we'll never again have a node with excess more than Delta. To guarantee this property one needs to further limit the amount pushed.
- in Question 2: any algorithm that implements 2-opt changes efficiently will work. What I had in mind is this:

Select an edge e=(u,v).

Evaluate if adding (u,v) to the tour would improve it, and make the change if it improves:

- get next(v), next(w).

- if c(u,v) + c(next(v),next(w)) - c(v,next(v)) - c(w,next(w)) < 0 then reverse(next(v),w)

The goal of the problem is to invent a data structure that can maintain a tour through the nodes and do this loop for a sequence of m edges in time O(m log n) time on the average.

- Question 1b we start from a tree T. Let S be the subset
of elements that we issue search(x), delete(x), or insert(x) operations.
The assumption is that |S|=n, that is, out of the N elements in the tree
only a small subset S is relevant in the sense that it occurs in a query.
The claim is that if the number of operations, m is high enough, then
the total time for the sequence of m queries can be bounded by O(m log
n) even if the total number of elements in the tree is much higher than
n.
- Comments, typos, clarifications about the midterm.
- Problem 2 in definition of end(x), it should have said: intervals that have end time at LEAST x (not at most).
- Problem 3: the input for the problem is the graph (with n nodes and m edges), the edge e', the number k, and the variable epsilon. None of these values should be assumed to be constant. The running time should be polynomial in the input size.
- Problem 1: you may assume that all nodes have different values.