Assignment 7

Contents

Assignment 7#

Dave Friedman
CMPSC 465 Data Structures and Algorithms

1#

You are placed in charge of the development of an algorithm for the newly created Penn State University Missile Defense System, which is responsible for defending the university from missile attacks launched from the University of Pennsylvania. Fortunately, your life has been made a bit easier by a defector, who has provided you with the full schedule of planned missile launches over the next \(n\) days. For each day \(i \lt n\), \(x_i\) missiles will arrive. Because of the defector, you know the exact values of \(x_i\).

Unfortunately due to budget cuts, your missile defense system has limited capacity. You need to stockpile anti-missile munitions which are supplied to you each day. Additionally, when the missile defense system is activated it will expend all available munitions regardless of the number of missiles destroyed that day. Munitions are supplied according to a function \(f(j)\) such that the value of this function indicates the number of missiles that can be intercepted by the system after \(j\) days of stockpiling. If the system is activated after \(j\) days of stockpiling, on day \(k\), then it will destroy \(\min\{ x_k, f(j) \}\) incoming missiles.

Your goal is to design a dynamic programming algorithm which will, based on the daily schedule of missile launches \((x_0, x_1, x_2, \dotsc, x_{n - 1})\) and a known resupply function \(f(j)\) determine the maximum number of incoming missiles that can be destroyed by the system. You must also analyze the runtime of this algorithm and state its time complexity in big-theta notation.

\(f(j) =\) the number of missiles that can be intercepted by the anti-missile system after \(j\) days of stockpiling.

for day i = 1 to n
    x[i] missiles

f(j) = anti-missile munitions

2#

Consider the following weighted directed graph (which includes negative edge weights):

A -> (D,   1), (H, 5), (I, -1), (J, 1)
B -> (A,   2), (G, 5)
C -> (D, -10)
D -> (F,   3)
E -> (F,   2)
F -> (G,   2)
G -> (E,   3)
H -> (C,   1)
I -> (B,   1)
J -> (I,   2)

A

Will Dijkstra’s algorithm work on this graph to calculate the single-source shortest paths starting at vertex A? If not, provide a specific example where it results in the wrong decision being made.

No, Dijkstra’s algorithm will not work on this graph to calculate the single-source shortest paths starting at vertex A. Due to the greedy choice property, Dijkstra’s algorithm selects A -> D with weight 1 when in fact the shortest path A -> D has weight -4.

(A,  0) <- (D, 1+0), (H, 5+0), pop(I, -1+0), (J, 1+0)
(I, -1) <- (D, 1), (H, 5), (J, 1), pop(B, 1-1)
(B,  0) <- pop(D, 1), (H, 5), (J, 1), (A, 2+0), (G, 5+0)
(D,  1) <- (H, 5), pop(J, 1), (A, 2), (G, 5), (F, 3+1)
(J,  1) <- (H, 5), skip(A, 2), (G, 5), pop(F, 4)
(F,  4) <- (H, 5), (G, 5), pop(G, 2)
(G,  2) <- (H, 5), (G, 5), pop(E, 3+2)
(E,  5) <- pop(H, 5), skip(G, 5), (F, 2+5)
(H,  5) <- (F, 7), pop(C, 1+5)
(C,  6) <- (F, 7), (D, -10+6)

B

Apply the Bellman-Ford algorithm to calculate the single-source shortest path from vertex C. Include a table showing the values of the paths to each vertex at each step of the algorithm.

     Iteration

A    infty    infty
B    infty    infty
C        0        0
D    infty      -10
E    infty       -2
F    infty       -7
G    infty       -5
H    infty    infty
I    infty    infty
J    infty    infty

3#

The Bellman-Ford algorithm will only function properly on graphs that do not contain negative cycles. Thus, it is important to be able to detect negative cycles. Propose an algorithm based on Bellman-Ford for determining whether a given graph contains a negative cycle and state its time complexity in big-theta notation.

The Bellman-Ford algorithm will converge after \(|V| - 1\) iterations under the assumption that the graph has no negative cycle. Therefore, run the algorithm one more time for a total of \(|V|\) iterations and check whether there is an update to a weight. If so, then there is a negative cycle. The time complexity \(\Theta(|V|\cdot |E|)\) does not change.

Contents