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
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?
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.
Problem 4
for every pair of
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.
Problem 6
Let G = (V,E) be an undirected graph with edge weights w : E → R+. Consider the following three edge 2
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?
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.
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.
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.
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σ.
3