# 算法代写 | CSCI 570 Random Questions

Problem 1 (Questions 1-3) (Random Questions)[Any 3 from the below 8 Questions]
Rubric: 2 points each correct Answer. Max 6 points

1) A problem X that has a pseudo-polynomial time solution can be in P, even if P ≠ NP –
True

2) If a problem X has a weakly polynomial time solution and a problem Y has a strongly
polynomial time solution, then we can say that Y ≤p X – True

3) If a problem Y has a weakly polynomial time solution and a problem X has a strongly
polynomial time solution, then we can say that Y ≤p X – True

4) For any α > 1, we can find the α-approximation solution in polynomial time for the 0-1
Knapsack Problem – Unknown

5) The Subset Sum Problem can be solved in polynomial time if all items have positive
weights – Unknown

6) Shortest path problem in a weighted directed graph with no negative cycles is polynomial
time reducible to the minimum spanning tree problem. – True

7) Every decision problem in P has a polynomial time certifier. – True

8) Given a set of constraints on X and Y, the two objective functions (Maximize 3X+5Y ,
and Minimize -3X-5Y ) will produce the same solution to a linear programming problem
– True

Problem 1 (Questions 4-6) (Random Questions)[Any 3 from the below 7 Questions]
Rubric: 2 points each correct Answer. Max 6 points

1) Dynamic programming subproblems can overlap but divide and conquer subproblems do
not overlap, therefore these techniques cannot be combined in a single algorithm – False

2) Although the Bellman-Ford algorithm deals with O(n^2) subproblems it will require no
more than O(n) memory space to run (in addition to storage required for the input) – True

3) Consider an (A,B) min cut where the source node s is in A and the sink node t is in B.
Increasing the capacity of edges that go from B into A will never cause the value of max
flow to go up. – True

4) It is possible to have a max flow of zero in a flow network even if all edge capacities are
greater than zero. – True

5) The top down pass in dynamic programming produces the value of the optimal solution
and the bottom up pass produces the actual solution. – False

6) In a divide and conquer solution, the sub-problems are always disjoint and are not
required to be of the same size. – True

7) In a graph G with positive distinct edge weights the shortest path from vertex s to vertex t
is unique. – False