# 代写Network | network | math | 代写Algorithm | 代写mining – Final Exam

### Final Exam

#### math 182, Winter 2022

Instructions.This exam has 9 questions, worth a total of 100 points and divided into 3 sections. Each section starts on a new page and contains instructions for how to answer questions in that section. Please make sure to carefully read the instructions for each section.

The following three questions are all True/False or short answer. No justification is required.

Question 1: True or False (18 points) Mark each statement as either True or False. (a) For any functionf:NN,f(n+ 1)O(f(n)). (b) For any natural numbersa, b 2 ,nloga(n)O(nlogb(n)). (c)SupposeGis a network where all edge weights are positive integers,fis a maximum flow onG, Cis anstcut inG,eis an edge that goes out ofCandGis the graph obtained fromGby reducing the weight ofeby 1. Iffis a valid flow onGthenCis not a minimum cut inG. (d) If a hash table hasnbuckets and currently holdsn^3 /^2 items then there is some item such that searching for that item takes(n)time. (e)A decision problem is in P if and only if it is reducible to the decision version of the Maximum Flow problem. (f)Suppose thatHypergraph Super Coloringis some decision problem which has been shown to be NP-complete. If Hypergraph Super Coloring is reducible to Reachability then Independent Set has a polynomial time algorithm. Question 2: Topological Sort (5 points) Draw a DAG with vertex set{A, B, C, D, E, F, G}whose only valid topological sorts are as follows:

• A, B, C, D, E, F, G
• A, C, B, D, E, F, G
##### A, C, B, D, F, G, E.

Question 3: Minimum Spanning Tree (5 points) Consider the following graph. A

##### E
``````Add weights to the edges of this graph so that the first two spanning trees drawn below are minimum
spanning trees of the graph, but the third one is not.
A
``````

#### 2 Correct or Not?

Both of the following two questions contain a description of a problem and an Algorithm that is supposed to solve that problem. For each question you should determine whether or not the algorithm is correct. If it is correct, prove it. If it is not correct, provide an example of an input on which it fails to find the correct answer. If you give a counterexample, you should briefly justify why the algorithm fails on your example, but you do not need to actually run the algorithm on the example.

Question 4: Shortest Paths with Negative Cycles (12 points) Problem.Given a weighted, directed graph,G= (V, E), and verticess, tV, find the shortest path fromstotin which every vertex is used at most twice. You should not assume that the edge weights are all positive nor should you assume that there are no negative cycles. Input.A weighted, directed graphG= (V, E)and verticess, tV. Output.The length of the shortest path fromstotsuch that no vertex inV appears more than twice on the path. Algorithm.Use dynamic programming, similar to the Floyd-Warshall algorithm. Assume the vertices are labelled with the numbers 1 through|V|. For all 1 i, j |V|and 0 k |V|, defineA(i, j, k) as the shortest path fromitojwhose intermediate vertices all come from the set{ 1 , 2 ,… , k}. The recursive formula is A(i, j, k) = min(A(i, j, k1), A(i, k, k1) +A(k, j, k1), A(i, k, k1) +A(k, k, k1) +A(k, j, k1)) with base cases A(i, j,0) =

0 ifi=j w(i, j) if(i, j)E otherwise. At the end, return the valueA(s, t,|V|). Question 5: Shortest Paths with Nonlinear Costs (12 points) Problem.Suppose you have a directed graphG= (V, E)and functionsw 1 :ER> 0 andw 2 :E R> 0. For any pathP= (v 1 , v 2 ,… , vk)inG, letw 1 (P)denote the length ofPaccording tow 1 and let w 2 (P)denote the length ofPaccording tow 2. In other words, w 1 (P) =

``````i<k
``````
``````w 1 (vi, vi+1) and w 2 (P) =
``````
``````i<k
``````
``````w 2 (vi, vi+1).
``````
``````Thecostof the pathP is defined asw 1 (P) +w 2 (P). Given verticessandtinV, you want to find
the minimum cost of any path fromstot.
Input.A directed graph,G= (V, E), verticess, tV and access to functionsw 1 , w 2 :ER> 0.
Output.The cost of the minimum cost path fromstotinG.
Algorithm.Use a modified version of Dijkstras algorithm. Keep three arrays,dist1,dist2, andcost,
where for allvV,dist1[v]is the current estimate of thew 1 -length of the minimum cost path froms
tovand, likewise,dist2[v]is the current estimate of thew 2 -length of the minimum cost path from
stovandcost[v] = dist1[v] + dist2[v]. Initially, setdist1[s] = dist2[s] = 0 anddist1[v]
= dist2[v] = for allv 6 =s. At each step, pick the unvisited vertexvwith minimumcost[v](i.e.
minimum among all unvisited vertices). Markvas visited. Then for each neighboruofv, check if
dist1[v]+w 1 (v, u) +dist2[v]+w 2 (v, u)<cost[u]. If so, setdist1[u]=dist1[v]+w 1 (v, u)and
dist2[u]=dist2[v]+w 2 (v, u)and updatecost[u]accordingly. Once all vertices have been either
visited or havecostequal to, outputcost[t].
``````