CSOR W4231Final Exam Instructions
homework | express代写 | 代做Network | Data structure | network | Algorithm | 作业Objective | assignment – 这是利用Objective进行训练的代写, 对Objective的流程进行训练解析, 是比较典型的express/Network/Data structure/network/Algorithm/Objective等代写方向, 这个项目是assignment代写的代写题目
- Please write your name and UNI at the top of every page you scan.
- The exam is open textbook (CLRS), open lecture slides, lecture notes and homework solutions. No other resources may be consulted (e.g., Internet, other textbooks, etc.). You must adhere to your signed honor pledge and the CS department academic honesty policies. Failure to do so will result in receiving a 0 in the exam and further disciplinary actions.
- You should read all the problems as soon as possible as they might not appear in order of difficulty to you.
- Please keep your answers clear and concise. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them.
- You can use any Algorithm that we covered in class or the homework assignments by simply referring to it, specifying its input, and stating its running time.
- For all algorithms you design, you must describe them clearly in English, argue correctness even if you do so briefly, and analyze the running time. You should follow any other specific instructions in the problems (for example, analyze space if asked to do so). Pseudocode is optional unless explicitly stated otherwise.
- If you give a Dynamic Programming algorithm, you must
- Clearly define the subproblems.
- Give the recurrence and explain it briefly in English.
- State boundary conditions.
- State running time.
- State space requirements.
- Give the order to fill in subproblems if the DP table has at least 2 dimensions.
- If you give a reduction, you must
- State the inputs to the two problems.
- Describe the reduction transformation clearly in English and argue that it requires polynomial time.
- Prove carefully equivalence of the original and the reduced instances.
- Your hand-writing should be very clear and your scan should be high quality. We will not grade your answer if we have difficulty reading it.
- You must follow the instructions at EdStem post #548 to submit your exam. You must submit your exam to Gradescope to receive a non-zero grade. There will be no exceptions to this rule. You must submit a single pdf with your scanned handwritten solutions to Gradescope under assignment Final Exambefore5:40pm ET on 5/12 (CVN students, see EdStem post #548).
- No modifications to your submission will be permitted. You should double check that all your answers appear in the pdf you will upload to Gradescope.
- You should handwrite, date and sign your honor pledge as instructed at EdStem post #549 and submit it with your exam answers. We will not grade exam answers that do not include a signed honor pledge.
Duration:75 minutes to complete the exam + 15 additional minutes to scan and upload your answers.
TOTAL /
True or False? Write the correct answer asTrueorFalsein your sheet. No explanation required. (All log are log 2 .)
N.B.: If you just write T or F, you will not get any credit!
i. Consider any flow network such that the value of the maximum flow is greater than 0.
There always exists an edge so that increasing the capacity of only that edge increases
the value of the max flow.
ii. Weak duality states that, if the primal LP is a minimization LP, then the value of every
primal feasible solution is lower bounded by the value of any dual feasible solution.
iii. The efficient certifierB(x, t) for a decision problemXinNPmay run in super-polynomial
time if the input instancexis anoinstance.
iv.P=NP if and only if there is a polynomial-time algorithm for the decision version of
themax-cutproblem.
The following statements are True or False. State what they are, with a brief explanation. If you state True, you should give a proof showing why they are True. If you state False, you should give a counter-example.
i. (10 points) I can convert any LP into a minimization LP, where all variables are non-
negative and all constraints are equalities.
ii. (10 points) In class, we proved that there is no 2-approximation algorithm forSymmetric
TSPunlessP=N P. That proof also shows that there is no 2-approximation algorithm
forMetric TSPunlessP=N P.
Consider a Bloom filter consisting of an array ofn= 13 entries and thek= 3 hash functions below
- h 1 (x) = (x+ 3) mod 13,
- h 2 (x) = (2x+ 2) mod 13,
- h 3 (x) = (3x+ 1) mod 13.
(a) (10 points) Suppose you want to maintain the setS={ 6 , 9 , 15 }. Show the Bloom filter
after these elements have been inserted to the filter. (The Bloom filter is a 0-indexed
array.)
(b) (9 points) The Bloom filter now receives the following three queries:
i. Isx= 8S?,
ii. Isx= 16S?,
iii. Isx= 19S?.
State the answer (yes or no) provided by the Bloom filter for each query, and explain
why the Data structure provides each answer.
Recall the problemKnapsack: On input a large target integer weightW >0, andnitems each with an integer weightwi>0 and a (real) valuevi>0, we are looking for a subsetS of the items that maximizes the total value ofSsubject to the total weight of the items inS being at mostW.
(a) (25 points) State the decision version ofKnapsackand prove that it isNP-complete.
(Hint: What is the most similar problem we stated asNP-complete?)
(b) (8 points) Give a Linear Program or an Integer Program (whichever is most appropriate)
forKnapsack.
That is, introduce in English (a) the variables, and state the special constraints on them
(b) the Objective function (c) the main constraints. Then write the resulting LP or IP,
as we did for the examples in class. (If you give an IP, include the integrality constraints
on the variables among the main constraints, as we did in class).
There arencontainers andmtrucks. Each truckj can hold up tokcontainers. For each containeri, there is a specified subsetSiof trucks that may carry the container.
You are asked to determine whether it is possible to load allncontainers in themtrucks so that each truck is loaded with containers it may carry and no truck is overloaded.
Give a polynomial-time algorithm to solve this problem.