CS70 Midterm Exam 2 Summer 2022 v2.doc
CS570 Summer 2022: Analysis of Algorithms Exam II
Copyright By PowCoder代写 加微信 powcoder
Points Points
Problem 1 20 Problem 5 12
Problem 2 9 Problem 6 16
Problem 3 12 Problem 7 16
Problem 4 15
Instructions:
1. This is a 2-hr exam. Open book and notes. No electronic devices or internet access.
2. If a description to an algorithm or a proof is required, please limit your description or proof to
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.
Mark the following statements as TRUE or FALSE by circling the correct answer. No need
to provide any justification.
[ TRUE/FALSE ]
If we can use a 2-approximation algorithm for vertex cover to find a 0.5-approximation
algorithm for independent set in polynomial time, then P = NP.
[ TRUE/FALSE ]
In class we showed that the weighted vertex cover problem is polynomial time reducible to
linear programming.
[ TRUE/FALSE ]
Breadth first search is an example of a divide-and-conquer algorithm.
[ TRUE/FALSE ]
Suppose f is a max flow in a flow network G. Increase the capacity of an edge in G by 1 unit.
Then, updating the flow f to reflect the new max flow in G can be done in linear time.
[ TRUE/FALSE ]
It is not known whether P ⊆ NP.
[ TRUE/FALSE ]
In the scaled version of the Ford Fulkerson algorithm, choice of augmenting paths cannot
affect the number of iterations.
[ TRUE/FALSE ]
Maximum value of an s-t flow could be less than the capacity of a given s-t cut in a flow
[ TRUE/FALSE ]
If the runtime of an algorithm is bounded by a polynomial in the number of bits in its input
then this algorithm is considered to be efficient.
[ TRUE/FALSE ]
Let G be an arbitrary flow network with a source S and a sink T, and every edge has a
positive capacity. Let (P, Q) be a minimum S-T cut, if we increase the capacity of every edge
by 1, (P, Q) will remain a minimum S-T cut in G.
[ TRUE/FALSE ]
The problem of finding out whether a given flow f in a flow network G is a maximum flow or
not is in the class NP.
2) 9 pts (for each question, full score is given if only all correct answers for that question
are selected, zero points otherwise)
I. Assume P ≠ NP. If X is polynomial time reducible to Y then select all true
statements. (3 pts)
a) If Y belongs to NP but not NPC then 3SAT is not polynomial time reducible to X
b) If X belongs to P then Y necessarily belongs to NP
c) If Y is the decision version of the vertex cover problem then X can be any
in NP-Hard
d) None of the above
II. If a problem Z is in NP, which of the following statements are true? Circle all
correct answer(s). (3 pts)
a) If Z can be solved in polynomial time, then P = NP
b) If the Independent Set problem is polynomial time reducible to Z, then Z is
NP-complete
c) If there is a polynomial time solution to 3 SAT, then there is a polynomial time
solution to Z
d) All of the above
III. Which of the following edge sets forms an MST? (3 pts)
a) {(d,b,), (c,b), (d,e), (a,c)}
b) {(a,b), (d,b,), (d,e), (c,b)}
c) {(d,b,), (d,e), (c,b)}
d) {(c,b), (d,e), (b,e), (a,b)}
Given an edge-weighted undirected graph and a list of edges in its Minimum
Spanning Tree (MST), describe an efficient algorithm (instead of running
Kruskal/Prim’s algorithm again) for updating the MST when the graph is modified in
the following ways. (You don’t need to describe how to re-implement common graph
operations such as BFS/DFS and finding a cycle)
A) Update the MST when the weight of an edge e = (u, v) that was not part of the
MST decreases. (3 pts)
B) Update the MST when the weight of an edge e = (u, v) that was part of the MST
decreases. (3 pts)
C) Update the MST when the weight of an edge e = (u, v) that was part of the MST
increases. (3 pts)
D) Update the MST when the weight of an edge e = (u, v) that was not part of the
MST increases. (3 pts)
Problem Statement: You are given an m x n matrix. Jack wants to traverse from the
northwest corner cell [0][0] to the southeast corner cell [m-1][n-1].
At any cell, he can only make either of the 3 moves and for each move, he loses some
energy before landing on the destination cell.
1. Go east by one cell – This decreases energy by 10 units. (e.g., If his energy
was x units when he moved from cell [1,2] to [1,3], his energy becomes x-10
units before he lands on [1,3])
2. Go south by one cell – this decreases energy by 10 units.
3. Go diagonally south-east by one cell – this decreases energy by 15 units.
You cannot make a move that takes you outside the matrix.
For all 0 ≤ i < m and 0 ≤ j < n, G[i][j] is an integer representing the factor by which Jack gains energy when he lands on that cell. E.g. if he had x amount of energy when he landed on cell [3][4] with G[3][4]=4, his energy becomes 4x. He always starts at cell [0][0] with energy = 20. Also, G[0][0] =1 and G[m-1][n-1] = 1 Note: if you are moving from cell A to B, the energy deduction of the move takes place before you land on B and the energy factor is applied after you land on cell B Objective: Find an optimal path from the starting cell to the target cell that maximizes your final energy at cell [m-1][n-1]. (a) Define the subproblem in your own words (3 pts) (b) Write an efficient algorithm/ pseudocode to find the optimal value of the solution, addressing the base conditions, recurrence relation, and edge cases. (6 pts) (c) Where will the optimal value of the solution lie and how will you obtain the optimal solution (path to traverse)? (3 pts) (d) What is the time complexity of your algorithm? Is this an efficient solution? (3 In class we showed that undirected Hamiltonian Cycle is polynomial time reducible to undirected Hamiltonian Path. Prove that directed Hamiltonian Cycle is also polynomial time reducible to directed Hamiltonian Path. The organizers of the 2022 US Open Tennis Championships are working on making the draws for the first round and scheduling the matches. They are faced with several constraints in doing so. There are 2N players, seeded (ranked) from 1 to 2N. The players are divided into two halves - The top half containing players seeded 1 to N, and the bottom half containing seeds N+1 to 2N. The first round consists of N matches among the 2N players, each being one where a top-half player plays a bottom-half player. Additionally, to keep them a bit more competitive, each match must be between players whose seeds differ by at most N’ (a given constant > N).
The sports facility has courts C1…Cm. The matches will be scheduled in timeslots T1…Tk.
Matches can run in parallel on different courts in a given timeslot. Assume all courts are available
in all timeslots, however a single court can have at most p matches to preserve surface quality.
For broadcasting reasons, in any given timeslot, there should be at least one match being played
and at most r of them.
The bottom-half players were given the option to make requests if they preferred to play in
certain timeslots, and each of them has specified k’ of the k timeslots that they are okay to play in.
Seeded players on the other hand were given the option to make requests to avoid playing on
certain courts, and each of them has specified m’ of the m courts that they do not want to play on.
Describe a Network Flow/Circulation based algorithm to determine if it is possible to come up
with a feasible schedule of matches based on the above constraints.
Suppose you are the same professor from exam 1 who is obsessed with giving algorithm books as
gifts to students because they got good grades. So again, there are n students sitting in a line. The
ith student in the line has grades g(i). There are m different book types (titles) in your possession,
with several copies of each type (title). A single copy of the j th type has a price of p(j) and you
own c(j) copies of that type.
You will give rewards to the students based on the following new set of criteria:
1. Each student receives at least one book.
2. For any two students i and i’ sitting next to each other (i.e. |i – i’| = 1):
1. If g(i) > g(i’) then number of books given to i must be greater than that given to
2. If g(i) = g(i’) then the same number of books should be given to i and i’
2. No student should get multiple copies of the same book type.
3. Any two students sitting next to each other, should not get copies of the same book type.
Write an integer linear program to find the minimum total price of books you must distribute.
a) Describe what your discrete variables represent (2 pts)
b) Write your linear constraints, and for each linear constraint mention which of the
problem constraints they enforce (12 pts)
c) Write your linear objective function (2 pt)
Additional Space
Additional Space
Additional Space
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com