CSOR W4231.001 – Spring, 2022
Brief solutions to hw2
1. Solution to problem 1
Slightly modify the min-priority queue implementation of Dijkstra’s algorithm:
Copyright By PowCoder代写 加微信 powcoder
Algorithm 1
ModifiedDijkstra(G = (V, E, w), s)
while Q is not empty do u = ExtractMin(Q) for all (u, v) ∈ E do
if dist(v) > dist(u) + wuv then dist(v) = dist(u) + wuv unique[v] = unique[u] DecreaseKey(Q, v)
if dist(v) = dist(u) + wuv then
unique[v] = 0 end if
end for end while
Running time: O((n + m) log n).
A similar modification to the array implementation of Dijkstra’s algorithm yields an O(n2)
algorithm.
2. Solution to problem 2
Slightly modify Dijkstra’s algorithm to also maintain the number of edges minedges[u] on the current shortest s-u path, for every node u. Initialize minedges[s] = 0, minedges[v] = ∞ for v ̸= s.
Algorithm 2
Update(u, v)
2: 3: 4: 5:
if (dist[v] > dist[u] + wuv) ∨ ((dist[v] == dist[u] + wuv) ∧ (minedges[v] > minedges[u] + 1)) then
dist[v] = dist[u] + wuv
prev[v] = u
minedges[v] = minedges[u] + 1
Correctness and running time follow from the proof of correctness and the runtime analysis of Dijkstra’s algorithm.
3. Solution to problem 3
Let T1,T2,…,Tn be the completion times for the contestants scheduled 1st, 2nd, …, n-th, respectively. Our goal is to minimize the maximum completion time of any contestant. Note that the completion time for the contestant scheduled last is Tn = bn + rn + ni=1 si. This implies that the completion time for the last contestant might be very large—thus resulting in a bad completion time for the entire schedule—if the time he needs for biking and running
is too long. Note that the individual times for biking and running don’t matter, only their sum does.
This motivates us to use the following greedy schedule S. Let ti = bi + ri. Schedule the contestants in decreasing order of ti. For example, the contestant with the largest ti is scheduled first, and the contestant with the smallest ti last.
We will now show that S is an optimal schedule. Suppose that there is another optimal schedule S′. If S′ is not the same as S, then it must differ from S in scheduling some contestants. Specifically, there must be a pair of consecutive contestants i,j in S′ such that i is scheduled before j but ti < tj. Note that S would schedule j before i.
Let σ be the sum of the swimming times for any contestants scheduled before contestant i in S′ (σ could be 0). Then the completion time for contestant i under S′ is
TS′ =t +s +σ, iii
while the completion time for contestant j under schedule S′ is TS′ =t +s +s +σ.
i in S1 becomes
while the completion time for contestant j in S1 is
Suppose we swap i and j. Call the resulting schedule S1. The completion time for contestant
TS1 =t +s +s +σ