CS570 Fall 2021: Analysis of Algorithms Exam III
Instructions:
1. This is a 2-hr exam. Open book and notes but no internet access allowed.
2. If a description to an algorithm or a proof is required, please limit your description or proof to
Copyright By PowCoder代写 加微信 powcoder
within 150 words, preferably not exceeding the space allotted for that question.
3. No space other than the pages in the exam booklet will be scanned for grading.
4. If you require an additional page for a question, you can use the extra page provided within
this booklet. However please indicate clearly that you are continuing the solution on the
additional page.
5. Do not detach any sheets from the booklet. Detached sheets will not be scanned.
6. If using a pencil to write the answers, make sure you apply enough pressure, so your answers
are readable in the scanned copy of your exam.
7. Do not write your answers in cursive scripts.
8. This exam is printed double sided. Check and use the back of each page.
1) Mark the following statements as TRUE or FALSE. No need to provide any justification. (18 pts total)
[ TRUE/FALSE ] (2 pts)
The NP-Hard class of problems does not contain any decision problems.
[ TRUE/FALSE ] (2 pts)
If every edge in a Flow Network is saturated due to flow F, then F must be a max flow.
[ TRUE/FALSE ] (2 pts)
If every edge in a Flow Network G is saturated due to flow F, then G has a unique max flow.
[ TRUE/FALSE ] (2 pts)
If there exists an algorithm that solves problem X with pseudo-polynomial runtime, then X must be NP-Hard.
[ TRUE/FALSE ] (2 pts)
Based on the definition of polynomial time reduction, we can say that linear programming is polynomial time reducible to max flow
[ TRUE/FALSE ] (2 pts)
Suppose there is a 7-approxmiation algorithm for the general Traveling Salesman Problem. Then there exists a polynomial time solution for the 3-SAT problem.
[ TRUE/FALSE ] (2 pts)
We can use the non-scaled version of the Ford-Fulkerson algorithm to find max-flow in weakly polynomial time, and use the scaled version of the algorithm to find max-flow in strongly polynomial time.
[ TRUE/FALSE ] (2 pts)
Suppose , then .
[ TRUE/FALSE ] (2 pts)
If X <=p Y, then an α-approximation algorithm for Y will give us an α-approximation algorithm for X
2) Multiple choice (6 pts total)
2.1 (3 pts)
Consider 3 problems A, B, and C where we know problem A is NP-complete, A ≤ p B, and C ≤p A. Based on this information select all correct answers below.
o B is NP-Complete o C is in NP
o B is NP-Hard
2.2 (3 pts)
Consider the following linear program:
maximize x1 + x2
subject to x1 + 2x2 ≤ 2
2x1 + x2 ≤ 2
x1, x2 ≥ 0
What is the (optimal) solution of this linear program?
(a) (x1, x2) = (1/3, 1/3)
(b) (x1, x2) = (2/3, 2/3)
(c) (x1, x2) = (1/3, 2/3) (d) None of the above
3) (10 pts)
Recall the Min-Flow problem from discussion set 9:
Provide a linear programming formulation to solve this problem. Describe your:
a) LP variables (2 pts)
Variables will be f(e)’s i.e., flow over the edge e for all edges e ∈ E
b) Objective function (2 pts)
Minimize ∑ f(e) for all e out of s (or into t)
-1 if it says max instead of min
-1 if doesn't sum over only the edges out of s (or only the edges into t)
c) Constraints (6 pts)
3 points each for lower bound and conservation of flow
Lower bound constraints:
f(e) >= le for all edges e ∈ E
conservation of flow
∑ f(e) for all e into v = ∑ f(e) for all e out of v, for all v ∈ V except for s and t
-1 point if conservation constraint doesn’t exclude s,t.
Given a directed graph G=(V,E) a source node s ε V, a sink node t ε V, and lower
bound le for flow on each edge e ε E, find a feasible s-t flow of minimum possible value.
Note: there are no capacity limits for flow on edges in G.
Alternate solution (more complicated): penalties apply same as for the solution before
f denotes feasible flow satisfying lower bounds, f’ denotes flow in the reverse direction (to decrease from feasible flow f)
d) LP variables (2 pts)
Variables will be f(e), f’(e) over edge e for all edges e ∈ E
e) Objective function (2 pts)
Minimize ∑ (f(e) – f’(e)) for all e out of s (or into t)
f) Constraints (6 pts)
1.5 points each for lower bound and conservation of flow
Lower bound feasibility of f:
f(e) >= le for all edges e ∈ E capacity for reverse flow f’:
f’(e) <= f(e) - le for all edges e ∈ E conservation of flow for f as well as f’:
∑ f(e) for all e into v = ∑ f(e) for all e out of v, for all v ∈ V except for s and t ∑ f(e) for all e into v = ∑ f(e) for all e out of v, for all v ∈ V except for s and t
4) (18 pts)
After a snowstorm, all the traffic lights went out on Main Street. Main Street is a linear street with n traffic lights. Because traffic lights are interconnected, fixing one traffic light will automatically fix its adjacent traffic lights (traffic lights adjacent to light i are lights i-1 and i+1 if they exist). However, fixing an already fixed light will do nothing. You are given a list of the times needed (in hours) to fix each light: T = t1, t2, t3, ..., tn. You are also given a list of pays for each light that you work on: P = p1, p2, p3, ..., pn. Note that you are only given pay for the lights that you have worked on, not the adjacent lights that are fixed automatically. You are given k hours to work on the traffic lights. Find the maximum pay possible.
An example to this question:
Total 9 lights: L1, L2, L3, L4, L5, L6, L7, L8, L9
Time needed to fix: T = 1, 4, 1, 4, 1, 1, 5, 2, 2
Pays: P = 250, 130, 100, 60, 50, 70, 270, 160, 140
You are given k = 6 hours
Solution: You should fix L1, L3, L6, L8 to earn a maximum pay of 580.
a) Define (in plain English) subproblems to be solved. (4 pts)
OPT[i][j] = Max pay value for lights 1..i given a total of j hours to work on traffic lights
- alternate solution can consider lights i to n (recurrence and pseudo-code changes accordingly)
-1 for saying “i lights” and not specifying which i
-2 for saying “light i” rather than the set of i lights above
b) Write a recurrence relation for the subproblems (5 pts)
Very similar to the 0-1 knapsack problem:
if we can fix light i within the j hours left, i.e. ti ≤ j OPT[i][j] = max(OPT[i - 1][j], OPT[i - 2][j - ti] + pi)
OPT[i][j] = OPT[i - 1][j] (Okay to exclude this case here IF correctly covered in
the pseudo-code via base cases or otherwise)
Scoring: up to -2 per mistake depending on how severe.
c) Using the recurrence formula in part b, write pseudocode using iteration to compute the maximum possible pay. (4 pts)
Make sure you specify
- base cases and their values (2 pts)
- where the final answer can be found (e.g. opt(n), or opt(0,n), etc.) (1 pt)
- OPT[0][j] = 0 for all j= 0 ... k (can skip this by adding base cases for OPT[2][j] instead)
- OPT[i][0]=0 foralli=0...n(thiscanbe excluded as it’s handled by the ti > j case in the loop)
– OPT[1][j] = 0 if t1 > j otherwise p1 for all j= 1 … k
For i from 2 to n:
For j from 1 to k:
if ti <= remaining time j:
OPT[i][j] = max(OPT[i - 1][j], OPT[i - 2][j - ti] + pi)
OPT[i][j] = OPT[i - 1][j]
Total_pay = OPT[n][k]
Scoring: up to -2 per mistake depending on how severe. No repeated penalties from the recurrence (but other errors arising from the inaccurate recurrence cannot be accepted.)
c) What is the complexity of your solution? (1 pt)
Runs in O(nk)
Is this an efficient solution? (1 pt)
No. This is not an efficient algorithm. This is a pseudo-polynomial time solution because the polynomial function nk contains a numerical value of an input term k
5) (14 pts)
Given an undirected, connected graph G with all edges having integer weights in the range 1 to 10, and starting vertex s, design an algorithm to find the smallest distance from s to all other nodes in the graph. The designed algorithm must run asymptotically faster than Dijkstra’s and state why.
Given graph G we will construct graph G’ as follows:
G’ will have the same initial set of nodes as G
For each edge e=(v,u) with cost c (1