CS 170 AlgorithmsSpring 2009 David Wagner HW 8Due March 20, 2:45pmInstructions: See “Instructions for writing up homework” on the course web page.1. (25 pts.) A greedy algorithm—so to speakThe founder of LinkedIn, the professional networking site, decides to crawl LinkedIn’s relationshipgraph to find all of the super-schmoozers. (He figures he can make more money from advertisersby charging a premium for ads displayed to super-schmoozers.) A super-schmoozer is a person onLinkedIn who has a link to at least 20 other super-schmoozers on LinkedIn.We can formalize this as a graph problem. Let the undirected graph G = (V,E) denote LinkedIn’srelationship graph, where each vertex represents a person who has an account on LinkedIn. Thereis an edge {u,v} ∈ E if u and v have listed a professional relationship with each other on LinkedIn(we will assume that relationships are symmetric). We are looking for a subset S ⊆ V of verticesso that every vertex s ∈ S has edges to at least 20 other vertices in S. And we want to make the setS as large as possible, subject to these constraints.Design an efficient algorithm to find the set of super-schmoozers (the largest set S that is consistentwith these constraints), given the graph G.Hint: I bet there are some vertices you can rule out immediately as not super-schmoozers.2. (25 pts.) A funky kind of coloringLet G = (V,E) be an undirected graph where every vertex has degree ≤ 51. Let’s find a way ofcoloring each vertex blue or gold, so that no vertex has more than 25 neighbors of its own color.Consider the following algorithm, where we call a vertex “bad” if it has more than 25 neighbors ofits own color:1. Color each vertex arbitrarily.2. Let B := {v ∈ V : v is bad}.3. While B 6= /0:4. Pick any bad vertex v ∈ B.5. Reverse the color of v.6. Update B to reflect this change, so that it again holds the set of bad vertices.Notice that if this algorithm terminates, it is guaranteed to find a coloring with the desired property.(a) Prove that this algorithm terminates in a finite number of steps. I suggest that you define apotential function that associates a non-negative integer (the potential) to each possible wayof coloring the graph, in such a way that each iteration of the while-loop is guaranteed tostrictly reduce the potential.CS 170, Spring 2009, HW 8 1(b) Prove that the algorithm terminates after at most |E| iterations of the loop.Hint: I suggest that you figure out what is the largest value the potential could take on.Comment: You might enjoy thinking about how to implement the algorithm so that its total runningtime is O(|V | + |E|)—but we will not grade it.3. (50 pts.) SchedulingThis problem will give you a tour through several scheduling algorithms with interesting practicalapplications.(a) You are writing a scheduler for an operating system running on a machine with a single CPU.You have n jobs to schedule, and the ith job will take tiseconds. Only one job can run at atime, so you must decide what order to run them in. There are no dependencies between thejobs, so there are no constraints on what order you can schedule them in. The goal is to findan ordering that minimizes the average time at which a job finishes, averaged over all jobs.For instance, suppose we have three jobs, and suppose you decide to execute the jobs in theorder 1, 2, 3. Then job 1 completes at time t1, job 2 completes at time t1+ t2, and job 3 attime t1+t2+t3. Therefore, in this example the average is [t1+ (t1+t2) + (t1+t2+t3)]/3.Design an efficient algorithm to find such an ordering, given t1,...,tn.(b) Now suppose that in addition to the times t1,...,tn, we are also given weights w1,..., wnthatrepresent how important each job is (the higher the weight, the more important the job is).Assume that w1+ ·· · + wn= 1 and 0 < wi≤ 1 for each i. The goal is to find an order thatminimizes the weighted average. For instance, if we execute n = 3 jobs in the order 1, 2, 3,the weighted average will be w1t1+ w2(t1+t2) + w3(t1+t2+t3).Design an efficient algorithm to find such an ordering, given t1,...,tnand w1,..., wn.(c) We buy another identical machine, so now we have two machines. Each job must be assignedto one of the two machines. Suppose what we care about is the final completion time whenthe last job is finished (the weights are irrelevant now). To put it another way: let S1denotethe set of jobs assigned to the first machine, and S2= {1,2,...,n} \ S1the set of jobs assignedto the second machine. The completion time for the first machine is C1=∑i∈S1ti, and thecompletion time for the second machine is C2=∑i∈S2ti. The overall completion time isC = max(C1,C2), and we’d like to find an assignment of jobs to machines that makes C assmall as we can.Consider this greedy algorithm. We process the jobs one by one, assigning job i to whichevermachine completes earlier given the assignment of the first i − 1 jobs. In pseudocode:1. Set c1:= 0 and c2:= 0.2. For i := 1, 2, .. ., n:3. If c1< c2, then assign job i to machine 1 and set c1:= c1+ti.4. Otherwise, assign job i to machine 2 and set c2:= c2+ti.Prove that the completion time of the solution output by this algorithm is at most 1.5 timeslarger than the completion time of the best possible ordering.Hint: Let a =12∑ni=1tiand b = maxiti. Let C∗denote the overall completion time of theoptimal ordering. Show that C∗≥ a, and C∗≥ b. Give an upper bound on |C1−C2|, as afunction of b; an upper bound on |C1− a|, again as a function of b; and similarly for |C2− a|.CS 170, Spring 2009, HW 8 2(d) We buy a whole bunch of identical machines, so that we have a total of m machines. Supposewe apply the greedy algorithm in part (c). In pseudocode:1. Set c[i] := 0 for each i := 1,2,.. .,m.2. For i := 1, 2, ..., n:3. Find j that minimizes c[ j] (i.e., choose j so that c[ j] ≤ c[k] for all k).4. Assign job i to machine j, and set c[ j] := c[ j] + ti.Give a good upper bound on the ratio between the completion time of the greedy algorithmabove and the completion time of the optimal ordering, as a function of m. In other words,you should come up with a small constant factor rm(which may depend upon m but shouldbe independent of n), so that the completion time of the greedy algorithm on any input is atmost rmC∗, where C∗is the completion time of the optimal ordering on this input. Make sureto prove your answer, and to provide a formula for rmas a function of m.(In part (c) we saw that r2= 1.5.