Shortest paths with negative weights

Dijkstra's algorithm can return a wrong answer on a graph that has negative edge weights. What exactly goes wrong?

Shortest paths with negative weights

Assume we are running Floyd-Warshall on a graph that has no negative cycle. The algorithm keeps a matrix whose entry dist[u][v] is the current estimate of the distance from u to v, and its outer loop runs over the vertices in the order 1, 2, …, |V|. Once the iteration for vertex k has finished, what does dist[u][v] hold?

Counting shared starts in a set of traversal orderings

A graph has n vertices. A tool has run depth-first search on it many times, with each run visiting the neighbours of a vertex in a different order. We have recorded N of the orderings it produced. Each ordering is the sequence of all n vertices in the order that the run visited them. Every run started at the same vertex.

These 8 orderings of one graph on 8 vertices are an example:

1  ahbfdceg
2  aedfbhgc
3  aghbcdfe
4  aedcbhgf
5  ahbfdecg
6  ahgbedcf
7  aedfhbcg
8  ahfdebcg

You have to design a data structure that can answer how many of the recorded orderings begin with a given sequence of m vertices. For example, how many of the 8 orderings above start with the sequence ahb? (The answer would be 2.)

Give the following in your answer:

1. Describe the data structure, including what is stored at each of its nodes.
2. Explain how the data structure can be used to answer the query, and why it gives the correct answer.
3. State and justify the time required to build the data structure and the time to answer the query (in terms of N, n and m).

Write in plain text. You may write a running time as Theta(...) or O(...).

Let S be a string in which some substring occurs at least twice. You build the suffix tree of S, with the terminator $ appended to S first. A node of the tree spells the characters on the path from the root down to it.

Which node spells a longest substring that occurs at least twice in S?

A left-leaning red-black tree corresponds to a 2-3 tree.

What does each red node correspond to?

A left or right rotation is performed somewhere in a binary search tree.

Which of the following is guaranteed to stay the same?

The root of a 2-3 tree is the two-key node [40 70].

In the corresponding left-leaning red-black tree, what is at the root?

In an AVL tree, node x has balance factor −2 (its right subtree is two levels taller than its left), and its right child has balance factor +1. The balance factor is height(left) − height(right).

How is the balance restored?

Below is Kruskal's algorithm exactly as it appears in the course notes.

1  function KRUSKAL(G = (V, E))
2     sort(E, key((u, v)) = w(u, v))
3     forest = UnionFind.initialise(n)
4     T = (V, {})
5     for each edge (u, v) in E do
6        if forest.FIND(u) != forest.FIND(v) then
7           forest.UNION(u, v)
8           T.add_edge(u, v)
9     return T

It is run with slow union. Assume the following costs, and that every other line takes constant time:

The edge list is supplied to the algorithm already sorted by weight, so line 2 has nothing left to do; that is why it costs \Theta(1).

Assume the graph is connected and simple, which implies |V| - 1 \le |E| \le |V|^2.

Give the worst-case time complexity of the whole algorithm, and explain how you got it. A complete answer states the cost of each part, adds them up, and then says which term dominates and why. No space complexity is needed.

Since you cannot type \Theta(), please write theta() in your answer.

A research group has a grant of exactly B dollars of compute credit, which must be spent down to zero. There are n machine types. Renting a machine of type i for one hour costs c_i > 0 dollars and completes j_i > 0 jobs. Any type may be rented any number of times. Maximise the jobs completed.

We solve this by defining the subproblem

maxJobs[x] = the most jobs completable by spending exactly x dollars

For example, with c = [3, 4], j = [5, 7] and B = 10, the best is one of each type plus one more of type 1, for 17 jobs.

Write the recurrence relation for this subproblem. Your answer must give:

• the base case or cases;
• an infeasible case, because some budgets cannot be met exactly;
• the general case, including the condition under which it applies;
• one sentence saying, in words, what the subproblem means.

You do not need to give pseudocode, prove anything, or state a complexity. Write mathematics however is easiest to type; max, <= and -infinity are all fine.