B403 Homework 3 Due date: 6, 2017 Lecturer: Qin Zhang Your Name: Your University ID: Instruction: Please submit your homework before class on the due...

B403 Homework 3 Due date: Mar. 6, 2017 Lecturer: Qin Zhang Your Name: Your University ID:

Instruction:

Please submit your homework before class on the due date, in hard copy . Please add references to ALL the resources you have used for completing the assignment. You are allowed to discuss the assignment with other students, and if you do so, please list their names in the submission.

Due: Mar. 6, 2017 Total points: 17 (+3 Bonus) Late Policy: No extensions or late homeworks will be granted, unless a request is made to the course instructor before due date and written documents are provided to support the reason for late submission.

Problem 1 (3 points). (Textbook Exercise 4.2(b)) Consider the following statement, decide whether it is true or false. If it is true, give a short explanation. If it is false, give a counterexample. Suppose we are given an instance of the Shortest s tPath Problem on a directed graph G . We assume that all edge costs are positive and distinct. Let Pbe a minimum-cost s t path for this instance. Now suppose we replace each edge cost c e by its square, c2 e , thereby creating a new instance of the problem with the same graph but di erent costs. True or false? Pmust still be a minimum-cost s tpath for this new instance.

Problem 2 (4 points). Consider the interval scheduling problem we discussed in class:

given a set S= f1;2 ; ; ngof activities, each activity ihas a starting time s i and nish time f i. Decide whether each of the following two greedy strategies will return an optimal solution which is a compatible set of maximum size. If the answer is yes, give a proof; if the answer is no, give a counterexample.

1.Select the job i2 Swith the biggest length (the length of job iis f i s i). If i is incompatible with some other job in S, then we do not schedule i; otherwise we schedule i.

2.Select the job i2 S with the smallest s i (i.e, earliest starting time). If there is a job j 2 Sn f ig such that [ s j; t j) [s i; t i), then we do not schedule i; otherwise we schedule i .

1 Problem 3 (4 points).

For the graphG= ( V ; E ) with weight w:E ! R >0 in Figure 1:

1.Use Dijkstra's algorithm to compute the shortest paths from ato all other vertices; 2.Use Prim's algorithm to nd the minimum spanning tree, with abeing the root vertex. Figure 1:

G= ( V ; E ) You can use the Table 1 and Table 2 to describe the execution of two algorithms respec- tively. iterations vertices b c d e f g considered d d d d d d 1 a 8 a 1 / 1 / 1 / 9 a 12 a 2 b 3 4 5 6 7 Table 1: Running Dijkstra's algorithm on the graph in Figure 1.

Problem 4 (3 points). Given a graphGand its MST T, we construct a new graph G 0 = G[ f eg by adding an edge e= ( u; v) (suppose there is no edge between u; vinG).

Design an algorithm to nd the MST of G0 with running time O(n ), where nis number of nodes in G.

Problem 5 (3 points). (Textbook Exercise 4.17) Consider the following variation on the Interval Scheduling Problem. You have a proces- sor that can operate 24 hours a day, every day. People submit requests to run daily jobson the processor. Each such job comes with a start timeand anend time ; if the job is accepted to run on the processor, it must run continuously, every day, for the period between its start 2 f b c a d e g 8 29 31 5 2 9 16 6 14 15 12 7 iterations edges vertices b c d e f g added considered d d d d d d 1 / a 8 a 1 / 1 / 1 / 9 a 12 a 2 ( a; b ) b 3 4 5 6 7 Table 2: Running Prim's algorithm on the graph in Figure 1.

and end times. (Note that certain jobs can begin before midnight and end after midnight; this makes for a type of situation di erent from what we saw in the Interval Scheduling Problem.) Given a list of nsuch jobs, your goal is to accept as many jobs as possible (regardless of their length), sub ject to the constraint that the processor can run at most one job at any given point in time. Provide an algorithm to do this with a running time that is polynomial in n. You may assume for simplicity that no two jobs have the same start or end times.

Example. Consider the following four jobs, speci ed by ( start time ,end time ) pairs.

(6 P:M:; 6A:M: ); (9 P:M:; 4A:M: ); (3 A:M:; 2P:M: ); (1 P:M:; 7P:M: ):

The optimal solution would be to pick the two jobs (9 P:M:;4A:M: ) and (1 P:M:;7P:M: ), which can be scheduled without overlapping.

Hint: Design an algorithm using the greedy interval scheduling algorithm we learned in class as a blackbox.

Problem 6 (3 bonus points). Consider the following algorithm for nding the minimum spanning tree of a connected graph G= ( V ; E ) with weight function w:E ! R.

(1) T E (2) while Tis not a tree (3)let Cbe an arbitrary cycle in T (4)let ebe the heaviest edge in C(ties are broken arbitrarily) (5) T Tn f eg (6) return T Does the algorithm always return a minimum spanning tree Tof G? If your answer is yes, prove it; if your answer is no, give an instance ( G; w) for which the algorithm does not return a minimum spanning tree.

3