Algorithm Design COMP3027/3927 Tutorial questions The University of Sydney 2020 Semester 1 Tutorial 2 School of Computer Science
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
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σ.
Problem 2
Your friend is working as a camp counselor, and he is in charge of organizing activities for a set of junior- high-school-age campers. One of his plans is the following mini-triathlon exercise: each contestant must
1
swim 20 laps of a pool, then cycle 10 km, then run 3 km. The plan is to send the contestants out in a staggered fashion, via the following rule: the contestants must use the pool one at a time. In other words, first contestant swims the 20 laps, gets out, and starts biking. As soon as the first contestant is out of the pool, the second contestant begins swimming the 20 laps; as soon as he/she’s out and starts cycling, a third contestant begins swimming . . . and so on.)
Each contestant has a projected swimming time (the expected time it will take him or her to complete the 20 laps), a projected cycling time (the expected time it will take him or her to complete the 10 km of cycling), and a projected running time (the time it will take him or her to complete the 3 km of running. Your friend wants to decide on a schedule for the triathlon: an order in which to sequence the starts of the contestants. Let’s say that the completion time of a schedule is the earliest time at which all contestants will be finished with all three legs of the triathlon, assuming they each spend exactly their projected swimming, biking, and running times on the three parts.
What’s the best order for sending people out, if one wants the whole competition to be over as early as possible? More precisely, give an efficient algorithm that produces a schedule whose completion time is as small as possible. Prove the correctness of your algorithm.
Problem 3
Assume that you are given n white and n black dots, lying on a line. The dots appear in any order of black and white. Design a greedy algorithm which connects each black dot with a (different) white dot, so that the total length of wires used to form such connected pairs is minimal. The length of wire used to connect two dots is equal to their distance along the line.
Problem 4
Let G = (V,E) be an undirected graph with edge costs ce. Prove that if the edge costs are distinct, then there is a unique MST. That is, if ce ̸= ce′ for every pair of edges e ̸= e′, then there is exactly one spanning tree whose cost is minimum.
Problem 5
Let G = (V, E) be an undirected graph with edge costs ce. The cycle property says that when the edge costs are distinct, i.e. ce ̸= ce′ for every pair of edges e ̸= e′, then for any cycle C of G, the costliest edge e ∈ C cannot be in the unique MST. Prove the cycle property using an exchange argument.
2