Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Guidelines
– Please make sure that the file you submit is not corrupted and that its size is reasonable (e.g., roughly at most 10-11 MB).
If we cannot open your file, your homework will not be graded.
Problem 1
Consider a virtual directed acyclic grid graph with its set of vertices and set of edges defined as follows. Let m and n be two positive integers. Each vertex in the graph is of the form (i,j), with i = 1,2,…,m and j = 1,2,…,n, where vertex (i,j) is in row i and column j. The number of vertices in the graph is mn. For each i = 1, 2, …, m, row i consists of vertices (i, j) with j = 1, 2, …, n. For each j = 1, 2, …, n, column j consists of vertices (i, j) with i = 1, 2, …, m. The graph contains three types of directed edges:=
horizontal edges, vertical edges and diagonal edges. For each i = 1, 2, …, m and each j = 2, 3, …, n, there is a directed horizontal edge from vertex (i, j − 1) to vertex (i, j) with a weight of w(1,j). For each i = 2,3,…,m and each j = 1,2,…,n, there is a directed vertical edge from vertex (i − 1, j) to vertex (i, j) with a weight of w(i, 1). For each i = 2, 3, …, m and each j = 2, 3, …, n, there is a directed diagonal edge from vertex (i − 1, j − 1) to vertex (i, j) with a weight of w(i, j). Note that some weights in the weight matrix w are negative, while other weights are non-negative.
For each i = 1,2,…,m and j = 1,2,…,n, define S(i,j) to be the maximum weight of all paths from the source vertex (1,1) to a target vertex (i,j), where the weight of a path from (1,1) to (i,j) is the sum of weights of each edge in the path. Develop and justify a formula for computing the matrix S. Design and analyze an algorithm with a running time of O(mn) for computing a maximum-weight path from (1,1) to (m,n). The input to the algorithm is a weight matrix w of m rows and n columns. You need to express the algorithm in pseudocode and to determine its running time. Note that there is no need to build this grid graph. But it is helpful to carry out the computation in order of rows or in order of columns of this virtual grid graph. Below an example weight matrix w of 4 rows and 5 columns. A maximum-weight path is < (1,1),(1,2),(2,3),(3,3),(4,4),(4,5) > with a weight of (−2)+8+(−1)+9+(−3) = 11. Note that w(3,1) = −1 is the weight of the edge from vertex (2,3) to vertex (3,3) and that w(1,5) = −3 is the weight of the edge from vertex (4, 4) to vertex (4, 5).
Problem 2
0 −2 −4 −8 −3 −2 −5 8 −5 2 −1 1 2 2 3
−4 2 3 9 1
Prove that P is closed under the star operation by dynamic programming. Problem 3
A triangle in an undirected graph G is defined to be a 3-clique (i.e., three vertices in G that are pairwise connected by edges) and 3−AN GLE := {⟨G⟩ | G contains a triangle }. Prove that 3 − AN GLE ∈ P .
Problem 4
Prove that if P = NP, then we can factor integers in polynomial time.