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...

Please see the attachment for more  clear and meaningful content of the this assignment.

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 − t Path Problem on a directed graph

G. We assume that all edge costs are positive and distinct. Let P be a minimum-cost s − t path for this instance. Now suppose we replace each edge cost ce by its square, c2e , thereby creating a new instance of the problem with the same graph but different costs.

True or false? P must still be a minimum-cost s − t path for this new instance.

Problem 2 (4 points). Consider the interval scheduling problem we discussed in class: given a set S = {1, 2, · · · , n} of activities, each activity i has a starting time si and finish time fi. 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 i ∈ S with the biggest length (the length of job i is fi − si). If i is incompatible with some other job in S, then we do not schedule i; otherwise we schedule i.

2. Select the job i ∈ S with the smallest si (i.e, earliest starting time). If there is a job j ∈ S {i} such that [sj , tj ) ⊆ [si, ti), then we do not schedule i; otherwise we schedule i.

Problem 3 (4 points). For the graph G = (V, E) with weight w : E → R>0 in Figure 1: 1. Use Dijkstra’s algorithm to compute the shortest paths from a to all other vertices;

2. Use Prim’s algorithm to find the minimum spanning tree, with a being the root vertex.

You can use the Table 1 and Table 2 to describe the execution of two algorithms respec-

tively.

Problem 4 (3 points). Given a graph G and its MST T, we construct a new graph G′ = G ∪ {e} by adding an edge e = (u,v) (suppose there is no edge between u,v in G). Design an algorithm to find the MST of G′ with running time O(n), where n is 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 jobs on the processor. Each such job comes with a start time and an end time; if the job is accepted to run on the processor, it must run continuously, every day, for the period between its start

and end times. (Note that certain jobs can begin before midnight and end after midnight; this makes for a type of situation different from what we saw in the Interval Scheduling Problem.)

Given a list of n such jobs, your goal is to accept as many jobs as possible (regardless of their length), subject 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, specified by (start − time, end − time) pairs. (6P.M., 6A.M.), (9P.M., 4A.M.), (3A.M., 2P.M.), (1P.M., 7P.M.).

The optimal solution would be to pick the two jobs (9P.M.,4A.M.) and (1P.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 finding the minimum spanning tree of a connected graph G = (V, E) with weight function w : E → R.

(1) (2) (3) (4) (5) (6)

T ← E while T is not a tree

let C be an arbitrary cycle in T let e be the heaviest edge in C (ties are broken arbitrarily) T ← T {e}

return T

Does the algorithm always return a minimum spanning tree T of 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.