Algorithm Design COMP3027/3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 3 School of Computer Science
Please review the lecture slides on MST and Djikstra’s algorithm prior to the tutorial. Most of you have already seen Dijkstra’s algorithm. Notice the similarity between it and Prim’s algorithm, even though they solve different problems.
Pre-tutorial questions
Do you know the basic concepts of this week’s lecture content? These questions are only to test yourself. They will not be explicitly discussed in the tutorial, and no solutions will be given to them.
1. Greedy algorithms
(a) What is typical with a greedy approach?
(b) What is the Interval Scheduling problem?
(c) What is the Interval Partitioning problem?
(d) To prove correctness of a greedy algorithm we often use an “exchange argument”. What is the idea of an exchange argument?
2. Minimum Spanning Trees
(a) What is a minimum spanning tree (MST)?
(b) A MST fulfills the cut property and the cycle property. Explain the two properties.
(c) Explain the general idea of Prim’s algorithm. 3. Dijkstra’s algorithm
(a) Convince yourself that Dijkstra’s on unweighted graphs is the same as BFS. In particular, if we run Dijkstra’s and BFS starting from the same vertex s and assuming that lexicographic tiebreaking is used in both algorithms, then the order in which vertices are explored are the same in both algorithms. Moreover, for every integer d > 0, the set of vertices that Dijkstra’s says has distance d to the source is the same as the d-th layer of the BFS tree.
(b) What does Dijkstra’s algorithm actually compute?
(c) State the general idea of Dijkstra’s algorithm.
Tutorial
Problem 1
Given set S of n real numbers and an integer I the 3-Sum problem is to decide (true/false) if S contains three elements that sum to I. It is well known that one can solve the problem in O(n2) time. The best known lower bound for the problem is Ω(n log n), that is, there is no algorithm that can solve the problem in less time. Given the below algorithm, can you give any upper and lower bounds on the running time of the algorithm? Assume that you have an algorithm Decide-3-Sum(S,I) that solves 3-Sum problem for a set S and an integer I.
1
Algorithm 1 Print-3-Sum values
1:
2: 3: 4: 5: 6: 7:
procedure Print-3-Sum values(S,m)
◃ S is a list of real values and m is an integer
for I = 1,…,m do
if Decide-3-Sum(S,I) then
Print(I)
end if end for
end procedure
b4e 43
Solution: We don’t know the implementation of Decide-3-Sum(S,I) we only know for sure that it requires Ω(n log n) time, hence the algorithm has a lower bound of Ω(mn log n) and we can’t give an upper bound. However, we do know that there exists some algorithm that can solve the problem in O(mn2).
3 7
a6d2g
535 c8f
Figure 1: Input graph to Questions 2 and 4.
9
Problem 2
Trace Prim’s algorithm on the graph in Fig. 1 starting at node a. What’s the output?
Solution: Recall Prim’s algorithm.
Step0: Setaastheroot,S={a}andthetreeT=nil.
Step 1: Find a lightest edge such that one endpoint is in S and the other is in V \ S. Add this edge to T and its (other) endpoint to S.
Step 2: If V \ S is empty then stop and output the minimum spanning tree T . Otherwise go to Step 1.
The output is shown in Fig. 2.
Problem 3
Prove that if the edge costs are distinct, then there is a unique MST. That is, if ce ̸= ce′ edges e ̸= e′, then there is exactly one spanning tree whose cost is minimum.
for every pair of
2
Solution: Suppose, towards a contradiction, that there exists two distinct MSTs T and T′. Let e be an edge that belongs to T and not T′. Removing e from T results in two connected components S and V \ S (see Figure 3 for an illustration). Let D denote the cutset of S. The cut property implies that the cheapest edge of D is every MST. Since e is the only edge of T in D, it must be that e is the cheapest edge of D. Applying the cut property again, we have that e must be in T′ as well. However, this contradicts the assumption that e does not belong to T′.
Problem 4
Trace Dijkstra’s algorithm on the graph in Fig. 1 starting at node a and ending at g. What’s the shortest path?
Problem 5
Similar to how BFS produces a rooted tree, observe that Dijkstra’s algorithm starting at s produces a shortest path tree T rooted at s. In particular, for every vertex v ̸= s, the s − v path in T is a shortest path between s and v. Similar to BFS, these edges are the ones that the algorithm uses to visit unexplored nodes.
Given the similarity between Dijkstra’s and Prim’s, one may be tempted to think that the algorithms are the same and produce the same trees. To overcome this temptation, give an example of a graph G with edge costs and a source vertex s, such that for every shortest path tree T rooted at s and every minimum spanning tree T′, we have that T′ ̸= T. In other words, no shortest path tree is a minimum spanning tree and vice versa.
Solution: The algorithm always choose to go to the node that is closest to the source. The output is shown in Fig. 4.
Solution: Consider the following graph G with edge weights cab = 5 and cac = 4 and cbc = 2, and source vertex a. The unique shortest path tree rooted at a consists of edges (a, b), (a, c) while the unique MST consists of edges (a, c) and (b, c).
a
c b
Problem 6
Let G = (V,E) be an undirected graph with edge weights w : E → R+. Consider the following three edge weightsw1,w2,w3 :E→R+,wherew1(e)=α·w(e)forsomeα>0,w2(e)=w(e)+βforsomeβ>0,and w3(e) = w(e)2.
1. Suppose p is a shortest s-t path for the weights w. Is p still optimal under w1? What about under w2? What about under w3?
2. Suppose T is minimum weight spanning tree for the weights w. Is T still optimal under w1? What about under w2? What about under w3?
3
Solution:
1. For w1 we note that for any two paths p and p′ if w(p) ≤ w(p′) then w1(p) = αw(p) ≤ αw(p′) = w1(p′).
so if a path is shortest under w it remains shortest under w1.
This is now longer the case with w2 and w3. Consider a graph with three vertices and three edges, basically a cycle. Suppose one edge has weight 1 and the other edges have weight 1/2. Consider the shortest path between the endpoints of the edge with weight one. The two possible paths have total weight 1, so both of them are shortest. Now imagine adding 1 to all edge weights; that is, consider w2 with β = 1. The shortest path in w2 is unique—the edge with weight 1 in w. Now imagine squaring the edge weights; that is, consider w3. The shortest path in w3 is unique—the path with two edges of weight 1/2, which under w3 have weight 1/4 each.
2. We claim that the optimal spanning tree does not change. This is because the relative order of the edge weights is the same under w, w1, w2, and w3. Therefore, if we run Prim’s or Kruskal’s algorithm the edges will be processed in the same order and the output will be the same in all cases.
Problem 7
Consider the following generalization of the shortest path problem where in addition to edge lengths, each vertex has a cost. The objective is to find an s-t path that minimizes the total length of the edges in the path plus the cost of the vertices in the path. Design an efficient algorithm for this problem.
Solution: We reduce the problem of finding a path with minimum edges plus vertex weight to a standard shortest path problem with weights on the edges only. Given a directed graph G = (V, E) and weights w we construct a new graph G′ = (V ′, E′) and weights w′. For each vertex u ∈ V we create two copies uin and uout , which we connect with an edge (uin , uout ) with weight w(u). For each edge (u, v) ∈ E we create an edge (uout , vin ) with weight w(e).
u uin uout u v uout vin
=⇒ =⇒ w(u) w(e)
w(e)
It is trivial to check that for each path p = ⟨u1,u2,…,uk⟩ in the input graph G we have a
path p′ = ⟨uout , uin , uout , . . . , uin ⟩. Furthermore, the edge weight of p′ equal the edges plus 122k
vertex weight of p.
It is easy to see that the graph G′ can be constructed in O(m + n) time. Furthermore, |V ′| = 2|V | and |E′| = |V | + |E|. Therefore Dijkstra’s algorithm run in O(m + n log n), where m = |E| and n = |V |.
Problem 8
It is not uncommon that a given optimization problem has multiple optimal solutions. For example, in an instance of the shortest s-t path problem, there could be multiple shortest paths connecting s and t. In such situations, it may be desirable to break ties in favor of a path that uses the fewest edges.
Show how to reduce this problem to a standard shortest path problem. You can assume that the edge lengths l are positive integers.
1. Let M be a positive integer and let us define a new edge function l′(e) = Ml(e) for each edge e. Show that if P and Q are two s-t paths such that l(P) < l(Q) then l′(Q) − l′(P) ≥ M.
4
2. Let us define a new edge function l′′(e) = Ml(e)+1 for each edge e. Show that if P and Q are two s-t paths such that l(P) = l(Q) but P uses fewer edges than Q then l′′(P) < l′′(Q).
3. Show how to set M in the second function l′′ so that the shortest s-t path under l′′ is also shortest under l and uses the fewest edges among all such shortest paths.
Solution:
1. Since the edge lengths are integer valued, if l(P ) < l(Q) then l(Q) − l(P ) ≥ 1. It follows then that l′(Q) − l′(P) = Ml(Q) − Ml(P) = M(l(Q) − l(P)) ≥ M.
2. Let |P| be the number of edges used in the path P. Then l′′(P) = Ml(P) + |P|. It follows that l′′(P) = Ml(P) + |P| < Ml(Q) + |Q| = l′′(Q).
3. Set M to be the number of vertices in the graph. From task (b) we know that if P is optimal under l′′ then it will have the fewest edges among paths that have length l(P ). Now suppose that there is another path Q such that l(Q) < l(P); then l(P)−l(Q) ≥ 1 and therefore M l(P ) ≥ M + M l(Q). Notice that since |Q| < n, we have
and also
M + Ml(Q) > |Q| + Ml(Q) = l′′(Q) Ml(P) ≤ |P| + Ml(P) ≤ l′′(P).
Putting all these inequalities together we get
l′′(P) ≥ Ml(P) ≥ M + Ml(Q) > l′′(Q)
which contradicts the optimality of P in l′′.
Problem 9
Suppose we are to schedule print jobs on a printer. Each job j has associated a weight wj > 0 (representing how important the job is) and a processing time tj (representing how long the job takes). A schedule σ is an ordering of the jobs that tell the printer how to process the jobs. Let Cjσ be the completion time of job j under the schedule σ.
Design a greedy algorithm that computes a schedule σ minimizing the sum of weighted completion times, that is, minimizing j wjCjσ.
5
Solution: An optimal schedule can be obtained by sorting the jobs in increasing tj order; wj
assume for simplicity that no two jobs have the same ratio. To show that the schedule is
optimal, we use an exchange argument. Suppose the optimal solution is σ and there are two
adjacent indices, say i and k such that ti > tk . We build another schedule τ where we wi wk
swap the positions of i and k, and leave other jobs in their places. We need to argue that this change decreases the cost of the schedule. Notice that the completion time of jobs other thaniandkisthesameinσandτ. Thus,
wjCjσ −wjCjτ = wiCiσ +wkCkσ −wiCiτ −wkCkτ. (1) jj
Let X = Ciσ − ti, the time when job i starts in σ, which equals the time when job k starts in τ. Then Ciσ = X + ti, Ckσ = X + ti + tk, Ckτ = X + tk, and Ciσ = X + ti + tk. If we plug these values into the above equation and simplify, we get
wjCjσ −wjCjτ =−witk +wkti. (2) jj
The proof is finished by noting that ti > tk implies −witk + wkti > 0 and therefore wi wk
wjCjσ >wjCjτ. jj
Hence, the schedule σ is not optimal.
6
b24e5 433
77 a6d32g
535 c48f
Figure 2: The red numbers show the order in which the nodes are added to the tree.
S
Figure 3: Illustration for proof that MST is unique if edge costs are distinct.
448 b4e
1
9
6
e
41337793 a6d82g
5235
5
11
9 c8f
Figure 4: The red numbers show the length of the shortest path from a, and the blue numbers show the order in which the nodes are reached.
7
10