Final Exam
代写Network | network | math | 代写Algorithm | 代写mining – 该题目是一个常规的math的练习题目代写, 涵盖了Network/network/math/Algorithm/mining等方面
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.
1 Short Answer
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, B, C, D, F, E, G
A, C, B, D, F, E, G
A, B, C, D, F, G, E
A, C, B, D, F, G, E.
Question 3: Minimum Spanning Tree (5 points) Consider the following graph. A
B C
D
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
B C
D
E
A
B C
D
E
A
B C
D
E
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].
3 Algorithm Design
Each of the next 5 questions asks you to design an efficient algorithm to solve some problem. For each problem, you should describe the main idea of your algorithm, give pseudocode for it and state its running time. You should give a brief justification of the running time (1-2 sentences should usually suffice).You do not need to provide a proof of correctness. Partial credit. For each problem, you will receive at least 5 points (and sometimes more) if you give a correct algorithm which runs in polynomial time. Incorrect algorithms may or may not receive partial credit, depending on the details of the algorithm. Incorrect algorithms are more likely to receive partial credit if you state that you know the algorithm is incorrect and give an example of an input on which it fails. Question 6: Winning a Game (12 points) You decide to play a game with your friend. Heres how the game works. You start with a board consisting of a line ofnsquares, each of which has two positive integers written on it, along with a token placed on the first square of the board. On each turn, the current player must move the token forward along the board and they can only move it forward by a number of steps which is written on the current square (e.g. if the current square has the numbers 3 and 7 then the current player can either move the token forward by 3 squares or 7 squares). Also the current player cannot move the token off the end of the board. If both available moves on the current square would cause the token to move off the end of the board then the current player loses (and the other player wins). You and your friend alternate turns and you have the first turn. You want to find out whether you have a winning strategy in this game. Design an efficient algorithm to solve this problem. Input.Ann 2 array of positive integers,A, representing the moves available on each square of the board (i.e.A[i, 1]andA[i, 2]denote the two moves available if the token is at squarei). Output.Trueif there is a winning strategy in the game described above where you start on square 1 andFalseotherwise. Hint.There is a dynamic programming solution with subproblemsW(i)defined as True if, when the token is on squarei, the current player has a winning strategy, and False otherwise. You are free to use a different solution, however. (a)Main idea. (b) Pseudocode. (c)Running time. Question 7: Rainbow Paths (12 points) Suppose you have a directed graphGwhere each vertex has been colored either red, green or blue. A path inGis called arainbow pathif for each of the three colors red, green and blue, there is at least one vertex in the path with that color. Given verticessandtinG, you want to check whether there is a rainbow path fromstot. Input.A directed graphG= (V, E), given in adjacency list format, whose vertex set is{ 1 , 2 ,… ,|V|}, verticess, tV and access to a functioncolorsuch that for any vertexiV,color(i)outputs the color of vertexiin constant time. Output.Trueif there is a rainbow path fromstotandFalseotherwise. (a)Main idea. (b) Pseudocode. (c)Running time (in terms ofn,mandk).
Question 8: Grid Search (12 points) Suppose you are given annmgrid with an integer written in each square in the grid. Additionally, except for the square in the upper left corner of the grid, the integer written in each square is larger than either the integer in the square above it or the square to the left of it (or both). Here are some examples of what the grid could look like: 1 2 3 6 5 4 7 9 8
1 4 6
2 4 7
3 11 10
3 8 9
4 5 6
You want to find thekthsmallest integer in the grid. Assume that if the grid contains repeated numbers then those are counted separately when deter mining thekthsmallest integer in the grid (so, for example, the 8 thsmallest integer in the second grid above is 10 , not 11 ). Design an efficient algorithm to solve this problem. Input.Natural numbersn, mandknmand annmarrayAof integers such that for all 1 in and 1 jm, at least one of the following holds: i=j= 1ori 1 1 andA[i – 1, j] < A[i, j] orj 1 1 andA[i, j – 1] < A[i, j]. Output.Thekthsmallest integer inA. (a)Main idea. (b) Pseudocode. (c)Running time (in terms ofn,mandk). Question 9: Arranging Books (12 points) You work at a bookstore and have a bookcase withkempty shelves that you need to fill up with books. You also have a list ofnbooks which you can use to fill up these shelves. However, there are a few rules you must obey. Namely, the books have been sorted in alphabetical order and you cannot change their ordering when placing them on the shelves. The shelves are also ordered and you should fill up the shelves in order: all the books on the first shelf should be in alphabetical order and should come (alphabetically) before all the books on the second shelf, all the books on the second shelf should come before all the books on the third shelf, and so on. However, you do not need to place all books on the shelvesyou may skip some and place them back in storage. Additionally, the bookcase has some fixed width and for each shelf, the sum of the widths of the books on that shelf should not exceed the width of the bookcase. Your goal is to put as many books as possible on the shelves. Design an efficient algorithm which finds the maximum number of books that you can place on thekshelves. Example.Suppose the width of the bookcase is 10 , the widths of the books are 3 , 7 , 4 , 15 , 4 , 3 , 5 , 1 , 2 , 3 and there are 2 shelves then the maximum number of books that can be placed on the shelves is 6 , which can be achieved by putting books with widths 3 , 4 , 3 on the first shelf and books with widths 1 , 2 , 3 on the second shelf. Input.Positive integerskandWthe number of shelves and the width of the bookcase, respectively along with a lengthnarrayAof positive integers such thatA[i]is the width of booki. Output.The maximum number of books that can be placed on the shelves if the rules explained above are followed. (a)Main idea. (b) Pseudocode. (c)Running time (in terms ofnandk).