Design and Analysis of Computer Algorithm Assignment 2
Name: Boyu Zhang UTD-ID: 2021226566 Email:bxz140830@utdallas.edu

Contents
Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

Problem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Problem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Problem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Problem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

Problem 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

Problem 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11

Problem1 This problem can solution by Dial’s algorithm in the lesson six. We can set up W+2 buckets with the labels of 0, 1, …, W, . Then we carry out the following steps: (a). Initial the buckets with node S be in the bucket 0 and all other nodes be in the bucket . (b). then select the node with the minimum temporary distance label. For the first time, it should be the source node S in the bucket 0. (c). Update the buckets information. Then some node should be moved from the bucket  to the corresponding distance bucket. (d). Remove the selected node from the bucket. Then repeat step 2 and 3 until there is no non-empty bucket. Therefore we can compute the shortest paths from source vertexs in O(W|V|+|E|). Because the extract part’s step during the Dijkstra's algorithm takes O(W|V|) time while the decreasing operation still takes O(E) time.

Problem 2 Bottleneck Path Problem algorithm for directed graphs

2

1: INPUT: A directed graph G = (V, E) with m = |E| and edge weights de ∈D for all edge e∈E, source and target vertices s, t ∈V , a number s(m); 2: Initialize i ← 0, E’ ← E, L ← mine∈E de, U = maxe∈E de 3: while i < log s(m) do 4: Determine the median M of {de : e∈E’, de≤U}. 5: T := {e∈E’: de≤M}, F := {e∈E’: de > M} 6: if (V, F) is s–t–connected then 7: E’ ← F, L ← M 8: else 9: E’ ← T, U ← M 10: end if 11: i ← i + 1 12: end while 13: Number the t edges in {e∈E’: de ≤U} according to increasing weights: e1, . . . , et 14: Solve the instance: l(e) =1 if de≤L, or i + 1 if e∈E’, e = ei or t + 2 if ce > U The running time of this algorithm depends on some function s(w), where lines 12 altogether need O(mlog s(m)) steps. As the number of edges in E’

3

with weights at most U is halved in each iteration, we have t = O( m/s(m) ). Thus, if we sort D keys in O(D logD) time, the running time spent in line 13 is O( m/s(m)* log m/s(m) ). Line 14 thus needs O(m) steps. By setting s(m) = logm we obtain an O(mlog logm) algorithm for this problem in directed graphs.

Problem 3 Because in the Faster-All-Pairs-Shortest-Paths, according the lemma 25.2

the multiplication of matrices has already been redefined, then Lk denote the matrix with elements lkij which is the length of the shortest path with at most k edges from i to j. It is obvious that if there is negative-weight cycle in the graph, for example wkj is negative-weight ,so the lki+ wkj always is decrease, the matrix of Ln − 1 and all the matrices with the index greater than n − 1 should be the decrease. So according to this, we can use several ways to check whether there is a negative-weight cycle in the graph,

4

1. Compute Ln, Ln +1. If they are not equal, then there is a negative-weight cycle in the graph. 2. Compute Ln, L 2n. If they are not equal, then there is a negative-weight cycle in the graph.

Problem4

This problem has an optimal structure: The total cost of one labeled tree could always be calculated by the sum cost of the two sub-trees and an additional backup. Using m[i,j] to denote the lowest cost of a subtree with leaves vi, … , vj (i +1 ≤ j). It may seem strange that m[i,i]= 0, contradicts with the fact that one leave i still costs .However, here we only compute about a labeled tree, who has more than one leaf, this definition would keep all the m[i,j] correct (j >= i+1). m[i, j] 0 — —j =i m[i, j] = ai +aj — — j= i +1 m[ i,j ]= mini