data留学生程序代做、代写c/c++，Java编程语言、system代写

日期：2020-11-10 11:25

26 (100 pts.) DynCraft

You’re in charge of setting up some gold mining infrastructure within an underground cave system.

The cave system can be modeled as a directed tree. It consists of N chambers. The root is the

entrance to the cave system, the chamber s. Each chamber is connected to at most 3 subtrees (a

ternary rooted tree!).

The quantity of gold in each chamber u is denoted by a function g(u).

To mine for gold and bring it up to the entrance, you need to place conveyor belts in the corridors

connecting the cave chambers. You have a limited number of L conveyor belts, L = O(N). If you

place a conveyor belt in a corridor connecting u to v, then it can carry gold from v to u towards

the entrance. You can mine all the gold from all of the chambers that can reach the entrance

through a path of conveyor belts.

The following is an example with three belts, and two dierent

solutions. Here, the root has value

0 associated with it. Here, the first solution has a better value than the second solution.

Give a dynamic programming algorithm that determines the optimal way to place the L conveyor

belts in order to mine the largest amount of gold.

Solution:

This is a standard dynamic programming problem on trees.

We can define each subproblem as F(u, `), which denotes the amount of gold that can be

brought up to chamber u by placing exactly ` conveyor belts, one of them has to connect u with

its parent.

At each tree, we have to choose how to allocate conveyor belts to the subtrees, that is we

have to choose among `1, `2, `3 such that `1 + `2 + `3  `. There are O(`2) such choices. We get

the recurrence:

Assume the vertices of the tree are numbered 1 to N, and s = 1. Let NULL = 0. Let

child(v, i) be a function that returns the ith child of the node v. If no such node exists, it

returns NULL.

otherwise.

Here is a pseudo-code for solving this using explicit-memoization:

return

The total number of subproblems is LN = O(N2). The time to compute each subproblem

will be O(N2) due to searching over `1 + `2 + `3 = `. As such, the overall running time is

O

⇣

(# subproblems) · (time per subproblem)

⌘

= O(N2 · N2

) = O(N4

).

The desired optimal solution value is ↵ = F(s, L + 1).

After computing all the optimal values, V [·, ·], recovering the optimal solution is easy.

continue

if V [v, `] = g(v) + V [child(v, 1), `1] + V [child(v, 2), `2)] + V [child(v, 3), `3] then

recoverOpt(v, child(v, 1), `1)

recoverOpt(v, child(v, 2), `2)

recoverOpt(v, child(v, 3), `3)

return

5

We call recoverOpt(NULL, v, `) to recover the optimal solution.

A faster solution is possible by rewriting the tree as a binary tree, with new fake edges being

“free”. The running time then improves to O(N3). An even faster algorithm should follow by

using separator node in the tree, but this is outside the scope for this class (and the analysis

looks messy in this case, but it probably leads to a near quadratic time algorithm in this case).

27 (100 pts.) Max Norm Suppose you have a directed graph with n vertices and m edges, where

each edge e has weight w(e), and no two edges have the same weight. Here, you can assume that

the graph is sparse, say, m = O(n log n). For a cycle C with edges e1e2 ··· e`, define the max-norm

of C to be

f(C) = max{w(e1), w(e2), ..., w(e`)}/`.

27.A. (20 pts.) Let f ⇤ be the maximum max-norm of any closed walk W in the graph. Show that

there is a simple cycle C such that f(C) = f ⇤. A simple cycle can visit a vertex at most

once.

Solution:

Let C be a cycle with the maximum f(C). If there is more than one such optimal

cycle, pick the one with the smallest number of edges. Let e1, e2,...,e`, e1 be its edge

sequence, where without loss of generality e1 is the edge with the most weight (the cycle

is the same if we simply rotate the indexes around). Suppose that a vertex is repeated.

Then the end vertex of ei is equal to the start vertex of ej for some j>i + 1. The cycle

e1,...,ei, ej , ej+1,...,e`, e1 has the same maximum edge weight, but fewer nodes, hence it

is has a greater max-norm, a contradiction.

27.B. (80 pts.) Give an algorithm that finds the cycle with largest max-norm as quickly as possible.

6

Solution: We compute for every pair of vertices u, v 2 V(G) their hop distance h(u, v)

– that is, the minimal number of edges in a path from u to v. This can be computed in

O(n(n + m)) time, by doing BFS from each vertex of the graph. Here h(u, v) = NULL, if

there is not path from u to v, where NULL is a special value indicator.

Now, for each edge u ! v in the graph, we compute the candidate value

(u,

v) = w(u ! v)

h(v, u)+1.

Here if h(u, v) = NULL, then we set (u,

v) = NULL.

The algorithm returns the maximum value h(u, v) computed that is not NULL, overall

vertices u, v 2 V(G). If all the computed values of h(·, ·) are NULL, the algorithm prints

“Oh no”, apologizes, throw a tantrum, and then do a core dump.

The running time of the algorithm is O(n2 + nm).

Lemma 9.2. The above algorithm returns the correct value.

Proof: If there is no cycle in the graph, then the algorithm detects it, and apologizes.

Otherwise, observe that any (u,

v) that is not NULLis a valid value of some cycle. Consider

the optimal cycle C, with e = u ! v be its heaviest edge. Clearly, h(v, u) = |C|

1,

which readily implies that the algorithm computes the right value.

7