I have attached a pdf file and consists of 5 questions.
• The following functions take as input a specific source s ∈ V and output dist(s,v) for all vertices v ∈ V ; they work on both directed and undirected graphs. – BFS(G,s) – Dijkstra(G,s) – DAG-SP(G,s) – BellmanFord(G,s) ∗ Bellman Ford returns ”Negative Cycle Detected” if a negative cycle is detected • Johnson(G) returns dist(x,y) for all pairs of vertices x, y in V • TopSort(G). After running this algorithm, you can assume that the vertex set V = {v1, ..., vn} is in topological order. – TopSort(G) returns ”NOT a DAG” if the input graph G is not a DAG. Graph Problems For all problems that involve a graph, you can assume that the graph G has no isolated vertices. In particular, you can always assume that |E| ≥ |V |/2. Dynamic Programming Problems Problems 3 and 4 are dynamic pro- gramming problems. For both of these problems, your answer should follow the same basic template as from HW 4. In particular, your solution must contain ALL of the following, in the exact order below. To repeat, this only applies to problems 3 and 4. 1. What the values in your table correspond to. So e.g. for longest in- creasing subsequence (from class) I would write something like: T [i] is the length of the longest increasing sequence ending at A[i] 2. The DP-relation that computes one table entry in terms of other table entires. So for longest increasing subsequence I would write something like: T [i] = maxj T [j] + 1, where the maximum is taken over all j < i="" with="" a[j]="">< a[i]. 2 3. how do you initialize the table: so for longest increasing subsequence i would write t [0] = 1. 4. which entry of the table you return at the end of the algorithm. so for example for longest increasing subsequence i would write: return findmax(t) 5. pseudocode for the final algorithm. list of np-hard problems for this exam, you can assume that the fol- lowing problems are np-hard. you will want to use one of the problems on this list to solve problem 5. • hamcycle(g) • clique(g,k) • vertexcover(g,k) • 2-partition(s) • subsetsum(s,b) 3 figure 1: graph for problem 1 part 1. 1 problem 1 (20 points) part 1 (10 points) say that you run dijkstra(g,s) on the graph in figure 1. recall that dijkstra’s explores vertices one at a time. what is the order in which dijkstra(g,s) explores vertices when run the graph g and source s below? what is the distance label of each vertex when it is explored? no need to justify your work. your solution only needs to include the following table: • the table should have 2 rows and 7 columns (one column per vertex) • the first row should include the vertices of g in the order in which they are explored. • the second row should include the label of each vertex when that vertex is explored. so for example, if when b is explored it has label d(b) = 1000, then you put the number 1000 in the second row of the column of vertex b. (note: 1000 is not actually the correct answer for vertex b.) 4 part 2 (10 points) consider the dag g in figure 2. this graph has exactly two valid topological orderings. you should write down both of them. no need to justify work. your solution only needs to include the two orderings; no need for explanation or anything else. 5 figure 2: graph for problem 1 part 2. 6 2 problem 2 (15 points) both parts of this problem are about the reduced weights in johnson’s al- gorithm. recall that johnson’s algorithm takes as input a graph g with n vertices and (possibly negative) edge weights w(x, y) and outputs a graph g′ which has the same vertices/edges as g, but with different edge weights. let w′(x, y) be the edge-weights in g′, and recall that johnson’s algorithm guarantees that w′(x, y) ≥ 0 part 1 (5 points) say that in the original input graph g, all weights were non-negative; that is w(x, y) ≥ 0 for all edges (x, y). now say you ran johnson’s algorithm on this graph g and ended up with g′. what can you say about the relationship between w′(x, y) and w(x, y)? this relationship between w′(x, y) and w(x, y) will hold true for all edges (x, y). you must briefly justify your answer ; i’m not look for a complex proof. there is a very simple 1-3 sentence explanation. note: the problem sounds open ended, but it is not. there is an ex- tremely concrete thing you can say about the relationship between w(x, y) and w′(x, y). there is also an extremely concrete (and simple) explanation for why this relationship always holds. if you are saying something vague then you are not on the right track. note: the relationship between w(x, y) and w′(x, y) crucially depends on the fact that we are assuming in this part that w(x, y) ≥ 0 for all edges (x, y). part 2 (10 points) now consider a different graph g, which has exactly 10 vertices v1, v2, ..., v10 and also has the property that all edge weights w(x, y) are either −1, 0, or 1. now say that you ran johnson’s algorithm on this graph and ended up with the graph g′. what is the largest possible edge weight in g′? that is, what is the maximum possible w′(x, y)? you need to give an example of a graph g and a specific edge (x, y) such that running johnson’s on g to create g′ leads to this maximum possible w′(x, y). grading note: the correctness of your example will be a huge part of your grade. so don’t just give the final number without example. no justification needed for this problem. all of you need to include is the example graph, the specific edge (x, y) in the example graph, and the value of w′(x, y) achieved in your example graph. 7 3 problem 3 (25 points) in this problem we consider a variant of subset sum. consider the following problem: • input: – a set s = {s1, ..., sn} of positive integers.you can think of s as an array, so you can access any si = s[i] in o(1) time. – each element si ∈ s is colored either red or blue. you can think of each color as a field in the objects si. so you can access any si.color in o(1) time. – a target positive integer b • output: the algorithm should output true if there exists a subset s ′ ⊆ s such that ∑ x∈s′ = b and s ′ contains at most 100 red elements. the algorithm should output false otherwise. note that you don’t need to output the set s ′ itself; just true/false. show a dp algorithm that solves the above problem in o(nb) time. you should include all of the elements of a dynamic programming solution mentioned at the beginning of the exam. 8 4 problem 4 (22 points) consider the following problem: • input – a dag g = (v,e) – two specific vertices s, t ∈ v • output: the number of different paths in g from s to t that have ≤ 100 edges. you don’t have the output the actual paths; you just have to figure out how many of them there are. show a dynamic programming algorithm that solves the above problem in o(|e|) time. you should include all the elements of dynamic programming solution mentioned at the beginning of the exam. you should also include a brief (1-2 sentences) justification for why the running time is o(|e|). note: reminder that you can assume in this class that all arithmetic operations (multiplication, addition, etc.) take o(1) time. 9 5 problem 5 (18 points) recall the suitcase packing problem from hw 4, problem 5. consider the natural true/false version of this problem: suitcase(s,v,w) • input: – set s = {s1, ..., sn}, where each element si has an si.value and an si.weight – a target value v – a maximum weight w • output: return true if there exists a set s ′ ⊆ s such that the total value of s ′ is at least v and the total weight of s ′ is at most w . note the at least and at most: intuitively, we want to find a suitcase with large value and small weight, which is why we require value at least v and weight at most w . formally, the algorithm should output true if there exists a set s ′ ⊆ s such that both of the following hold: – ∑n i=1 si.value ≥ v – ∑n i=1 si.weight ≤ w the problem: show that the above problem suitcase(s,v,w) is np- complete. hint: note the list of np-hard problems at the beginning of this exam. you will want to use one of those in your proof that suitcase packing is np-complete. 10 a[i].="" 2="" 3.="" how="" do="" you="" initialize="" the="" table:="" so="" for="" longest="" increasing="" subsequence="" i="" would="" write="" t="" [0]="1." 4.="" which="" entry="" of="" the="" table="" you="" return="" at="" the="" end="" of="" the="" algorithm.="" so="" for="" example="" for="" longest="" increasing="" subsequence="" i="" would="" write:="" return="" findmax(t)="" 5.="" pseudocode="" for="" the="" final="" algorithm.="" list="" of="" np-hard="" problems="" for="" this="" exam,="" you="" can="" assume="" that="" the="" fol-="" lowing="" problems="" are="" np-hard.="" you="" will="" want="" to="" use="" one="" of="" the="" problems="" on="" this="" list="" to="" solve="" problem="" 5.="" •="" hamcycle(g)="" •="" clique(g,k)="" •="" vertexcover(g,k)="" •="" 2-partition(s)="" •="" subsetsum(s,b)="" 3="" figure="" 1:="" graph="" for="" problem="" 1="" part="" 1.="" 1="" problem="" 1="" (20="" points)="" part="" 1="" (10="" points)="" say="" that="" you="" run="" dijkstra(g,s)="" on="" the="" graph="" in="" figure="" 1.="" recall="" that="" dijkstra’s="" explores="" vertices="" one="" at="" a="" time.="" what="" is="" the="" order="" in="" which="" dijkstra(g,s)="" explores="" vertices="" when="" run="" the="" graph="" g="" and="" source="" s="" below?="" what="" is="" the="" distance="" label="" of="" each="" vertex="" when="" it="" is="" explored?="" no="" need="" to="" justify="" your="" work.="" your="" solution="" only="" needs="" to="" include="" the="" following="" table:="" •="" the="" table="" should="" have="" 2="" rows="" and="" 7="" columns="" (one="" column="" per="" vertex)="" •="" the="" first="" row="" should="" include="" the="" vertices="" of="" g="" in="" the="" order="" in="" which="" they="" are="" explored.="" •="" the="" second="" row="" should="" include="" the="" label="" of="" each="" vertex="" when="" that="" vertex="" is="" explored.="" so="" for="" example,="" if="" when="" b="" is="" explored="" it="" has="" label="" d(b)="1000," then="" you="" put="" the="" number="" 1000="" in="" the="" second="" row="" of="" the="" column="" of="" vertex="" b.="" (note:="" 1000="" is="" not="" actually="" the="" correct="" answer="" for="" vertex="" b.)="" 4="" part="" 2="" (10="" points)="" consider="" the="" dag="" g="" in="" figure="" 2.="" this="" graph="" has="" exactly="" two="" valid="" topological="" orderings.="" you="" should="" write="" down="" both="" of="" them.="" no="" need="" to="" justify="" work.="" your="" solution="" only="" needs="" to="" include="" the="" two="" orderings;="" no="" need="" for="" explanation="" or="" anything="" else.="" 5="" figure="" 2:="" graph="" for="" problem="" 1="" part="" 2.="" 6="" 2="" problem="" 2="" (15="" points)="" both="" parts="" of="" this="" problem="" are="" about="" the="" reduced="" weights="" in="" johnson’s="" al-="" gorithm.="" recall="" that="" johnson’s="" algorithm="" takes="" as="" input="" a="" graph="" g="" with="" n="" vertices="" and="" (possibly="" negative)="" edge="" weights="" w(x,="" y)="" and="" outputs="" a="" graph="" g′="" which="" has="" the="" same="" vertices/edges="" as="" g,="" but="" with="" different="" edge="" weights.="" let="" w′(x,="" y)="" be="" the="" edge-weights="" in="" g′,="" and="" recall="" that="" johnson’s="" algorithm="" guarantees="" that="" w′(x,="" y)="" ≥="" 0="" part="" 1="" (5="" points)="" say="" that="" in="" the="" original="" input="" graph="" g,="" all="" weights="" were="" non-negative;="" that="" is="" w(x,="" y)="" ≥="" 0="" for="" all="" edges="" (x,="" y).="" now="" say="" you="" ran="" johnson’s="" algorithm="" on="" this="" graph="" g="" and="" ended="" up="" with="" g′.="" what="" can="" you="" say="" about="" the="" relationship="" between="" w′(x,="" y)="" and="" w(x,="" y)?="" this="" relationship="" between="" w′(x,="" y)="" and="" w(x,="" y)="" will="" hold="" true="" for="" all="" edges="" (x,="" y).="" you="" must="" briefly="" justify="" your="" answer="" ;="" i’m="" not="" look="" for="" a="" complex="" proof.="" there="" is="" a="" very="" simple="" 1-3="" sentence="" explanation.="" note:="" the="" problem="" sounds="" open="" ended,="" but="" it="" is="" not.="" there="" is="" an="" ex-="" tremely="" concrete="" thing="" you="" can="" say="" about="" the="" relationship="" between="" w(x,="" y)="" and="" w′(x,="" y).="" there="" is="" also="" an="" extremely="" concrete="" (and="" simple)="" explanation="" for="" why="" this="" relationship="" always="" holds.="" if="" you="" are="" saying="" something="" vague="" then="" you="" are="" not="" on="" the="" right="" track.="" note:="" the="" relationship="" between="" w(x,="" y)="" and="" w′(x,="" y)="" crucially="" depends="" on="" the="" fact="" that="" we="" are="" assuming="" in="" this="" part="" that="" w(x,="" y)="" ≥="" 0="" for="" all="" edges="" (x,="" y).="" part="" 2="" (10="" points)="" now="" consider="" a="" different="" graph="" g,="" which="" has="" exactly="" 10="" vertices="" v1,="" v2,="" ...,="" v10="" and="" also="" has="" the="" property="" that="" all="" edge="" weights="" w(x,="" y)="" are="" either="" −1,="" 0,="" or="" 1.="" now="" say="" that="" you="" ran="" johnson’s="" algorithm="" on="" this="" graph="" and="" ended="" up="" with="" the="" graph="" g′.="" what="" is="" the="" largest="" possible="" edge="" weight="" in="" g′?="" that="" is,="" what="" is="" the="" maximum="" possible="" w′(x,="" y)?="" you="" need="" to="" give="" an="" example="" of="" a="" graph="" g="" and="" a="" specific="" edge="" (x,="" y)="" such="" that="" running="" johnson’s="" on="" g="" to="" create="" g′="" leads="" to="" this="" maximum="" possible="" w′(x,="" y).="" grading="" note:="" the="" correctness="" of="" your="" example="" will="" be="" a="" huge="" part="" of="" your="" grade.="" so="" don’t="" just="" give="" the="" final="" number="" without="" example.="" no="" justification="" needed="" for="" this="" problem.="" all="" of="" you="" need="" to="" include="" is="" the="" example="" graph,="" the="" specific="" edge="" (x,="" y)="" in="" the="" example="" graph,="" and="" the="" value="" of="" w′(x,="" y)="" achieved="" in="" your="" example="" graph.="" 7="" 3="" problem="" 3="" (25="" points)="" in="" this="" problem="" we="" consider="" a="" variant="" of="" subset="" sum.="" consider="" the="" following="" problem:="" •="" input:="" –="" a="" set="" s="{s1," ...,="" sn}="" of="" positive="" integers.you="" can="" think="" of="" s="" as="" an="" array,="" so="" you="" can="" access="" any="" si="S[i]" in="" o(1)="" time.="" –="" each="" element="" si="" ∈="" s="" is="" colored="" either="" red="" or="" blue.="" you="" can="" think="" of="" each="" color="" as="" a="" field="" in="" the="" objects="" si.="" so="" you="" can="" access="" any="" si.color="" in="" o(1)="" time.="" –="" a="" target="" positive="" integer="" b="" •="" output:="" the="" algorithm="" should="" output="" true="" if="" there="" exists="" a="" subset="" s="" ′="" ⊆="" s="" such="" that="" ∑="" x∈s′="B" and="" s="" ′="" contains="" at="" most="" 100="" red="" elements.="" the="" algorithm="" should="" output="" false="" otherwise.="" note="" that="" you="" don’t="" need="" to="" output="" the="" set="" s="" ′="" itself;="" just="" true/false.="" show="" a="" dp="" algorithm="" that="" solves="" the="" above="" problem="" in="" o(nb)="" time.="" you="" should="" include="" all="" of="" the="" elements="" of="" a="" dynamic="" programming="" solution="" mentioned="" at="" the="" beginning="" of="" the="" exam.="" 8="" 4="" problem="" 4="" (22="" points)="" consider="" the="" following="" problem:="" •="" input="" –="" a="" dag="" g="(V,E)" –="" two="" specific="" vertices="" s,="" t="" ∈="" v="" •="" output:="" the="" number="" of="" different="" paths="" in="" g="" from="" s="" to="" t="" that="" have="" ≤="" 100="" edges.="" you="" don’t="" have="" the="" output="" the="" actual="" paths;="" you="" just="" have="" to="" figure="" out="" how="" many="" of="" them="" there="" are.="" show="" a="" dynamic="" programming="" algorithm="" that="" solves="" the="" above="" problem="" in="" o(|e|)="" time.="" you="" should="" include="" all="" the="" elements="" of="" dynamic="" programming="" solution="" mentioned="" at="" the="" beginning="" of="" the="" exam.="" you="" should="" also="" include="" a="" brief="" (1-2="" sentences)="" justification="" for="" why="" the="" running="" time="" is="" o(|e|).="" note:="" reminder="" that="" you="" can="" assume="" in="" this="" class="" that="" all="" arithmetic="" operations="" (multiplication,="" addition,="" etc.)="" take="" o(1)="" time.="" 9="" 5="" problem="" 5="" (18="" points)="" recall="" the="" suitcase="" packing="" problem="" from="" hw="" 4,="" problem="" 5.="" consider="" the="" natural="" true/false="" version="" of="" this="" problem:="" suitcase(s,v,w)="" •="" input:="" –="" set="" s="{s1," ...,="" sn},="" where="" each="" element="" si="" has="" an="" si.value="" and="" an="" si.weight="" –="" a="" target="" value="" v="" –="" a="" maximum="" weight="" w="" •="" output:="" return="" true="" if="" there="" exists="" a="" set="" s="" ′="" ⊆="" s="" such="" that="" the="" total="" value="" of="" s="" ′="" is="" at="" least="" v="" and="" the="" total="" weight="" of="" s="" ′="" is="" at="" most="" w="" .="" note="" the="" at="" least="" and="" at="" most:="" intuitively,="" we="" want="" to="" find="" a="" suitcase="" with="" large="" value="" and="" small="" weight,="" which="" is="" why="" we="" require="" value="" at="" least="" v="" and="" weight="" at="" most="" w="" .="" formally,="" the="" algorithm="" should="" output="" true="" if="" there="" exists="" a="" set="" s="" ′="" ⊆="" s="" such="" that="" both="" of="" the="" following="" hold:="" –="" ∑n="" i="1" si.value="" ≥="" v="" –="" ∑n="" i="1" si.weight="" ≤="" w="" the="" problem:="" show="" that="" the="" above="" problem="" suitcase(s,v,w)="" is="" np-="" complete.="" hint:="" note="" the="" list="" of="" np-hard="" problems="" at="" the="" beginning="" of="" this="" exam.="" you="" will="" want="" to="" use="" one="" of="" those="" in="" your="" proof="" that="" suitcase="" packing="" is="" np-complete.="">