CS代考 DECEMBER 2019 - PowCoder代写

DECEMBER 2019
Final Exam
CSC 373H5F
Last Name: Student #:

First Name: Signature:
UNIVERSITY OF TORONTO MISSISSAUGA DECEMBER 2019 FINAL EXAMINATION CSC373H5F
Algorithm Design and Analysis
Vincent Maccio
Duration – 3 hours
Aids: None
The University of Toronto Mississauga and you, as a student, share a commitment to academic integrity. You are reminded that you may be charged with an academic offence for possessing any unauthorized aids during the writing of an exam. Clear, sealable, plastic bags have been provided for all electronic devices with storage, including but not limited to: cell phones, smart devices, tablets, laptops, calculators, and MP3 players. Please turn off all devices, seal them in the bag provided, and place the bag under your desk for the duration of the examination. You will not be able to touch the bag or its contents until the exam is over.
If, during an exam, any of these items are found on your person or in the area of your desk other than in the clear, sealable, plastic bag, you may be charged with an academic offence. A typical penalty for an academic offence may cause you to fail the course.
Please note, once this exam has begun, you CANNOT re-write it.
This final examination consists of 7 questions on 16 pages (including this one). When you receive the signal to start, please make sure that your copy of the examination is complete.
If you need more space for one of your solutions, use the last pages of the exam and indicate clearly the part of your work that should be marked.
Good Luck!
Marking Guide
#1: /7 #2: /6 #3: /10 #4: /5 #5: /4 #6: /10 #7: /8
TOTAL: /50
Page 1 of 16
cont’d. . .

CSC 373H5F Final Exam DECEMBER 2019 Question 1. [7 marks]
Answer 7 of the 10 true or false questions below. You do not need to justify your answer, simply write true or false. Make it very clear which question(s) you’re answering. If you answer more than 7 questions, only the first 7 answers will be marked.
1. Let G be a flow-network. If all edges of G have their capacities increased by k, then the max-flow of G is increased by a multiple of k.
2. “Shortest Job First” is a 2-approximation for minimizing the average response time.
3. If there are only two machines (m = 2), then the Load Balancing problem can be solved by a well known greedy algorithm in polynomial time.
4. There is a well known greedy algorithm to solve the Fractional Knapsack Problem in polynomial time.
5. There is a well known dynamic programming algorithm to solve the Knapsack Problem in polynomial time.
6. To prove a greedy algorithm correct it’s enough to show there does not exist a problem instance in which the greedy algorithm returns a sub-optimal solution.
7. V isavertexcoverofG=(V,E)
8. If an algorithm is a k-approximation, then it is also a k/2-approximation.
9. In general, dynamic programming has greater space complexity than other algorithmic methods.
10. Let (S,T) be a min-cut of a flow network G, and (u,v) be an edge in G where u ∈ S and v ∈ T. Increasing c(u, v) increases the max-flow of G.
Page 2 of 16 cont’d. . .

DECEMBER 2019 Final Exam CSC 373H5F Question 2. [6 marks]
Below are problems and proposed greedy algorithms to solve those problems. For each problem, prove the greedy algorithm is suboptimal. For full grades your counter examples should be concise, clear, and obvious.
1. Problem: Vertex Cover Algorithm:
1) Find a node with the highest degree (most edges attached)
2) Add that node to your solution
3) Remove all edges incident to that node, then repeat until no edges remain
2. Problem: Load Balancing
Algorithm: Schedule the next job on the lightest loaded machine.
3. Problem: Shortest path from s to t in an arbitrary graph Algorithm: Dijkstra’s Algorithm
Page 3 of 16
cont’d. . .

CSC 373H5F Final Exam DECEMBER 2019 Question 3. [10 marks]
Recall the knapsack problem discussed in lecture, where given a set of n items, each with a weight and value, we wish to know the maximal value of a set of items, such that the total weight is less than or equal to some capacity C. Describe the dynamic programming solution to this problem by answering the following questions.
Part (a) [3 marks]
In plain English, describe what the sub-problem denotes. What are its parameters? If all your sub-problems
are solved, how would you arrive at the final answer to the knapsack problem?
Part (b) [4 marks]
Formally define how the sub-problems recursively relate to each other, make sure to define all base cases.
Let wi and vi denote the weight and value of item i, respectively.
Part (c) [3 marks]
Consider the following knapsack problem instance with total capacity C = 7 and the set of items:
I1 = (1, 3) I2 = (2, 7) I3 = (4, 12) I4 = (5, 14)
where Ii = (wi,vi) denotes that the ith item has a weight of wi and a value vi. Create and fill-out the table of sub-problems based on the dynamic programming solution above. Write your answer on the next page.
Page 4 of 16 cont’d. . .

DECEMBER 2019 Final Exam CSC 373H5F More room to work on Question 3. There are more questions on the following pages!
Page 5 of 16 cont’d. . .

CSC 373H5F Final Exam Question 4. [5 marks]
Consider the following flow network G = (V, E):
• V = {s,1,2,3,t}
• E = {(s,1),(s,2),(1,t),(2,1),(2,3),(1,3),(3,t)}
• c(s,1) = c(s,2) = 2
c(2,1) = c(2,3) = c(1,t) = 1 c(1,3) = c(3,t) = c(1,t) = 3
Part (a) [1 mark]
Draw the flow network, clearly label all vertices and edge capacities.
DECEMBER 2019
Part (b) [4 marks]
Run the Ford-Fulkerson method on the network (choose augmenting paths however you wish). For each augmenting flow sent through the network, clearly draw the corresponding residual network labelling all appropriate residual edges and capacities (you should have drawings of at least three different residual networks).
Page 6 of 16 cont’d. . .

DECEMBER 2019 Final Exam CSC 373H5F More room to work on Question 4 if needed. There are more questions on the following pages!
Page 7 of 16 cont’d. . .

CSC 373H5F Final Exam DECEMBER 2019 Question 5. [4 marks]
You’re trying to schedule shift workers at a power plant for the next 3 weeks. Each week i has si shifts which need to be covered. There are 5 workers total. Each worker j is only able to work di,j shifts in week i. As per union rules, over the entire 3 week schedule each worker can work no more than D shifts.
Draw a flow network that will determine if such a schedule is possible. State how you would use the flow network to determine if such a schedule was possible. Clearly label all edge capacities. Make things as neat as possible.
Page 8 of 16 cont’d. . .

DECEMBER 2019 Final Exam CSC 373H5F Question 6. [10 marks]
Recall the Travelling Salesman problem (TSP) from lecture, where given a graph G and a start node s we wish to find a minimum Tour of G. Let T∗ denote a minimum tour, and let MST denote a minimum spanning tree of G. We also assumed:
1. G is dense
2. ∀v1,v2,v3 ∈V,w(v1,v3)≤w(v1,v2)+w(v2,v3)
Part (a) [3 marks]
Propose an algorithm which is a 2-approximation to the TSP. You do not need to prove it’s a 2- approximation (yet). To achieve full grades you should discuss a “walk” of an MST using the pictures below.
There are more parts on the following page.
Page 9 of 16 cont’d. . .

CSC 373H5F Final Exam DECEMBER 2019 Part (b) [2 marks]
For all parts remaining use the following denotations:
• c(MST): The sum of all the edges in the MST • c(T ): The length of the tour T
• c(W ): The length of the walk W
Give a meaningful inequality or equality between c(MST) and c(T∗). Justify it.
Part (c) [2 marks]
Give a meaningful inequality or equality between c(MST) and c(W). Justify it.
Part (d) [3 marks]
Using your previous answers, prove your algorithm from Part (a) is a 2-approximation.
Page 10 of 16
cont’d. . .

DECEMBER 2019 Final Exam CSC 373H5F More room to work on question 6 if needed. There is one more question on the following page!
Page 11 of 16 cont’d. . .

CSC 373H5F Final Exam DECEMBER 2019 Question 7. [8 marks]
To find the max flow of a given flow-network we saw that we needed to keep track of potential “back-flow” edges in the residual network. That is, if we just selected paths from s to t in the original network, then sent flow through it, and repeated until no paths remain, we could find ourselves in a situation where no more flow can be sent from s to t, but |f| was not a max-flow. In other words, ignoring back-flows is suboptimal. But how bad is it?
Part (a) [3 marks]
Via a counter example show that ignoring back-flows is not a 2-approximation. To achieve full grades your
counter example should have capacity of 1 for all its edges.
Part (b) [5 marks]
Now show that for all k ≥ 1, ignoring back-flows is not a k-approximation. Hint: show that you can always construct a flow-network where the max-flow is (k + 1) but you could pick a path such that you terminate with a flow f, where |f| = 1.
Page 12 of 16 cont’d. . .

DECEMBER 2019 Final Exam CSC 373H5F
[Use the space below for rough work. This page will not be marked, unless you clearly indicate the part of your work that you want us to mark.]
Page 13 of 16 cont’d. . .

CSC 373H5F Final Exam DECEMBER 2019
[Use the space below for rough work. This page will not be marked, unless you clearly indicate the part of your work that you want us to mark.]
Page 14 of 16 cont’d. . .

Related Posts