Algorithm
代做Algorithm – 这个题目属于一个Algorithm的代写任务, 涉及了Algorithm等代写方面
Your Name:
UCLA id:
The rules: Open book, open notes, open internet. You MUST write your in your own handwriting the pledge on the second page. You MUST simplify completely and BOX all answers. Except for the last problem, you MUST write out your logical reasoning and/or calculation steps in full. You MUST work on this midterm for at most 180 minutes within the 24 hour window.
Please write in your own handwriting the pledge below:
This work was performed solely by the me [your name, UCLA id], in accordance with the
rules above. No part of this midterm was shared with anyone in or outside of the class.
1
Problem 1. (30 points)
In the Gale-Shapely Algorithm, here are the preferences of applicants (1-5) and employers (A-E):
1 : (A, B, C, E, D)
2 : (B, A, D, E, C)
3 : (C, B, E, A, D)
4 : (D, E, A, B, C)
5 : (E, A, B, C, D)
A: (2, 3 , 4 , 5 ,1)
B: (3, 4 , 5 , 1 ,2)
C: (5, 1 , 4 , 2 ,3)
D: (3, 1 , 2 , 4 ,5)
E: (1, 5 , 2 , 3 ,4)
a) Show the steps of the GS Algorithm when employers make proposals. Check that this is a stable matching. b) Show the steps of the GS Algorithm when applicants make proposals. Is this the same stable matching as ina)?
Problem 2. (30 points)
Show all steps of the FordFulkerson Algorithm on the graph below. Find the value of the maximalst flow. Find the minimalstcut.
s b T
c
a u
e
d
v
w
12
9
8
6
7
8
13
3
2
6
4
4
5
6
2
13
7
6
Problem 3. (30 points)
Find the minimum vertex cover of the following bipartite graph. Remember to show the steps.
Problem 4. (30 points) The following points have integer coordinates in the [2020] square. Find the smallest distance between these points in this graph using the divide and conquer algorithm (feel free to use decimal approximation). Draw in the graph all distances the algorithm needs to compute.
Problem 5. (20 points) Recall the SATp3SAT reduction. Starting with the following SAT formula, compute the corresponding 3SAT formula.
(x 1 x 2 )(x 4 )(x 1 x 3 )(x 1 x 4 x 6 )(x 2 x 3 x 4 x 5 x 6 )
Problem 6. (20 points) We know thatIndependent Setis NP-complete. Suppose ProfessorXfound an algorithm which resolves the problem inT(n) 10 n^3 logntime on graphs withnvertices. ProfessorYis unconvinced and is interested in theHamiltonian cycleproblem. Which of the following is correct? Present a full argument. Feel free to quote any results from the textbook. a) ProfessorX should be able todecide if a graph withnvertices contains a Hamiltonian cycle in O(n^3 logn) time. b) ProfessorXshould be able todecideif a graph withnvertices contains a Hamiltonian cycle inO(n^300 ) time. c) ProfessorXshould be able tofinda Hamiltonian cycle if a graph withnvertices has one, inO(n^3000 ) time. d) ProfessorX should be able to bothsolveandgive an efficient certificateto the solution (whether positive or negative) of theHamiltonian cycleproblem for graphs withnvertices, inO(n^3000000 ) time.
Problem 7. (40 points, 2 points each). True or False?
Fill in the circles with correct answers. No reasoning/calculations will be taken into account.
T F 1. QSAT is either known or conjectured to be PSPACE-complete
T F 2. NP is either known or conjectured to be in PSPACEcoNP
T F 3. Integer Factoringis either known or conjectured to be NP-complete
T F 4. 2 -coloringis either known or conjectured to be NP-complete
T F 5. Vertex Coveris polynomial time reducible to SAT.
T F 6. Stable matchings can be found in polynomial time.
T F 7. Perfect matchings can be found in polynomial time in bipartite graphs.
T F 8. Travelling salesman problem is hard to solve in practice even for 100 cities.
T F 9. Augmented pathsare directedstpaths in the residual graph.
T F 10. Halls Theoremimplies thatPerfect Matchingproblem in a bipartite graph is NPcoNP
T F 11. It follows from theMaster Theoremthat the recurrence T(2n) 3 T(n) +O
(
n(logn)^2
)
implies T(n) =O(n^1.^8 )
T F 12. TheImage Segmentation Algorithmpresented in class is an application of the FordFulkerson Algorithm
T F 13. The best known algorithm for integer multiplication ofn-digit numbers takesO(nlogn) time
T F 14. In the coupon collectors problem, the expected number of trials isnlogn+O(n).
T F 15. Bubble sortingis a polynomial time algorithm
T F 16. Kruskals algorithmcan be used to find both the minimal and maximal spanning trees.
T F 17. Dijkstras algorithmis a divide and conquer algorithm
T F 18. FordFulkerson Algorithmis a greedy algorithm
T F 19. CookLevin Theoremproves that NP 6 = NP-complete
T F 20. IfXis ageometric random variablewith probabilitypof success, then the expectationE[X] = 1/p.