CSOR W4231Spring, 2022
homework | Network | 代做network | 代做Algorithm | assignment代做 – 该题目是一个常规的network的练习题目代写, 是有一定代表意义的Network/network/Algorithm等代写方向, 这是值得参考的assignment代写的题目
Eleni Drinea
homework 5 (125 points)
Homework Instructions.
- For all algorithms that you are asked to give or design, you should
- Describe your Algorithm clearly in English.
- Give pseudocode.
- Argue correctness; you may provide a formal proof or a convincing argument.
- Provide, with an explanation, the best (smallest) upper bound that you can for the running time. All bounds should beworst-casebounds, unless explicitly stated otherwise.
You are also encouraged to analyze the space required by your algorithm. We will not remove marks
if you dont, unless the problem explicitly asks you to analyze space complexity.
- If you give a dynamic programming algorithm, you should follow the instructions in HW2.
- If you give areduction, you should do so as we did in class, that is
(a) Give the inputs to the two problems.
(b) Describe in English the reduction transformation and argue that it requires polynomial time.
(You do not need to give pseudocode.)
(c) Prove carefully equivalence of the original and the reduced instances.
4.You should not use any external resources for this homework. You should work on these
problems entirely on your own and avoid collaborating with your classmates, unless you
have thought through the problems on your own for a long time and are unable to make any further
progress. Failure to follow this instruction might have a negative impact on your performance in the
second exam and interviews.
- You should submit this assignment as apdffile to Gradescope. Other file formats will not be graded, and will automatically receive a score of 0.
- I recommend you type your solutions using LaTeX. For every assignment, you will earn 5 extra credit points if you type your solutions using LaTeX or other software that prints equations and algorithms neatly. If you do not type your solutions, make sure that your handwriting is very clear and that your scan is high quality.
- You should write up the solutionsentirely on your own. Collaboration is limited to discussion of ideas only. You should adhere to the departments academic honesty policy (see the course syllabus). Similarity between your solutions and solutions of your classmates or solutions posted online will result in receiving a 0 in this assignment, and possibly further disciplinary actions. There will be no exception to this policy and it may be applied retro-actively if we have reasons to re-evaluate this homework.
Homework Problems
- (30 points) You are asked to assist in the following crisis event. Due to large scale flooding, there is a set ofninjured people distributed across a region that need to be rushed to hospitals. There arekhospitals in the region, and each of thenpeople needs to be brought to a hospital that is within a half-hours driving time of their current location (so different people will have different options for hospitals, depending on where they are right now). However you cannot overload any single hospital; instead, every hospital must receive at mostdn/kepeople.
Give an efficient algorithm for this problem.
- (25 points) In themin-cost flowproblem, the input is aflow network with supplieswhere each edge (i,j)Ealso has acostaij, that is, sending one unit of flow on edge (i,j) costsaij. Given a flow network with supplies and costs, the goal is to find a feasible flowf:ER+, that is, a flow satisfying edge capacity and node supply constraints, thatminimizesthe total cost of the flow. Show that the max flow problem can be formulated as a min-cost flow problem.
- (25 points) Suppose you had a polynomial-time algorithmAfor the decision versionVC(D)of the minimum vertex cover problem. That is, on input a graphG= (V,E) and an integerk,Aanswers yesif and only ifGhas a vertex cover of size at mostk, andAruns in worst-case polynomial time. Design a polynomial-time algorithm that takes as input a graphGand an integerk, and returns a vertex cover of size at mostk, if one exists inG, ornootherwise.
- (20 points) In theMAX SATproblem, the input is aSATformulawithmclauses overnvariables and the output is a truth assignment that maximizes the number of satisfied clauses, as well as that number. State the decision version ofMax SATand show that it isNP-complete.
- (25 points) Acliquein an undirected graphG= (V,E) is a subsetSof vertices such thatallpossible edges between the vertices inSappear inE. Max Cliqueis the following problem: On input a graphG= (V,E), find a clique of maximum size. Computing the maximum clique in a network (or the number of cliques of at least a certain size) is useful in analyzing social networks, where cliques corresponds to groups of people who all know each other. State the decision version ofMax Cliqueand show that it isNP-complete.
RECOMMENDED exercise: do NOT return, it will not be graded.
- Suppose you are givenncities and a set of non-negative distancesdijbetween pairs of cities.
(a) Give anO(n^22 n) dynamic programming algorithm to solve this instance ofTSP; that is, compute
the cost of the optimal tour and output the actual optimal tour.
(b) What are the space requirements of your algorithm?
Hint: LetV={ 1 ,...,n}be the set of cities. Consider progressively larger subsets of cities; for every
subsetSof cities including city 1 and at least one other city, compute the shortest path that starts at
city 1 , visits all cities inSand ends up in cityj, for everyjS.