UNIVERSITY OF TORONTO Faculty of Arts and Science
AUGUST 2018 EXAMINA TIONS
CSC373H1Y Instructor(s): Koushik Pal
Duration – 3 hours
Examination Aids: One 8.5″ x 11″ sheet of paper, handwritten on both sides.
Student Number: Last (Family) Name(s): First (Given) Name(s):
Do not turn this page until you have received the signal to start.
(In the meantime, please fill out the identification section above, and read the instructions below carefully.)
This final examination consists of 5 questions on 10 pages (including this one), printed on one side of the paper. When you receive the signal to start, please make sure that your copy of the examination is complete and write your student number at the bottom of every page, where indicated.
Answer each question directly on the examination paper1 in the space provided, and use the reverse side of the pages for rough work. If you need more space for one of your solutions, use the reverse side of a page and indicate clearly the part of your work that should be marked.
In your ans\:vers, you may use without proof any result or theorem covered during the course in lectures, tutorials, assignments, or term tests. You must justify all other facts required for your solution.
If you are unable to answer a question (or part of a question), you will get 103 of the marks for that (part of the) question if you leave it blank, and 203 of the marks if you state clearly that you do not know how to answer. Note that you will not get those marks if your answer contains contradictory statements (such as “I don’t know” followed or preceded by parts of a solution that have not been crossed off).
AUTOFAIL: You must achieve at least 30 marks on this exam to pass the course.
Good Luck!
MARKING GUIDE
# 1: /15 # 2: /15 # 3: /25 # 4: /20 # 5: /15
TOTAL: /90
Total Pages = 10 Pagel of 10 CONT’D ..
August 2018 FINAL EXAMINATION CSC373HlY
Question 1. (Greedy Algorithm) [15 MARKs]
You are consulting for a trucking company that does a large amount of business shipping packages from Toronto to Montreal. The volume is high enough that they have to send a number of trucks each day between the two locations. Trucks have a fixed integer limit W > 0 on the maximum amount of weight they are allowed to carry. Boxes arrive at the Toronto loading platform one by one, and each package i has a positive integer weight Wi :::; W. The loading platform is quite small, so at most one truck can be at the platform at any time. Company policy (and the limited space available at the platform) requires that boxes are shipped in the order they arrive – there would be complaints if boxes made it to Montreal out of order!
Write an efficient greedy algorithm to solve this problem, and prove that your algorithm is correct. (Your proof will be marked on its structure as well as its content.)
Student#: Page 2 of 10
CONT’D…
August 2018 FINAL EXAMINA TION CSC373H1Y
Question 2. (Dynamic Programming) [15 MARKS]
Given a set S of non-negative integers, and an integer t, determine if there is a subset of S with sum equal to t. If yes, find out one such subset.
For example, if S = {3, 5, 7, 9} and t = 12, then one subset that satisfies the requirements is {5, 7} (another one is {3, 9}). For the same set S and t = 6, there is no subset of S with sum= 6.
Write a dynamic programming algorithm to solve this problem. Follow the 5-steps “dynamic program- ming paradigm” covered in class. In particular, describe carefully the recursive structure of the problem in order to justify the correctness of your recurrence. Analyze the running time of your algorithm.
Page 3 of 10
August 2018 FINAL EXAMINATION CSC373H1Y
Question 3. (Graph and Network Flow) [25 MARKS]
Part (a) [10 MARKS]
Given a flow network G = (V, E), a maximum bottleneck path between two vertices u and vis a path between u and v that allows the most flow to go through from u to v. As usual, the maximum amount of flow that can go through such a path is equal to the capacity of the bottleneck edge on that path.
Give an algorithm that finds a maximum bottleneck path between two given vertices. Prove the correctness and analyze the running time of your algorithm.
(HINT: Think of a modified version of Dijkstra!)
Page 4 of 10
August 2018 FINAL EXAMINATION CSC373HlY
Part (b) [15 MARKS]
Given a flow network G = (V, E) and a max flow F, we want to find out if we can increase the max flow
of the network by increasing the capacity of a single edge in the network. Further, if such an edge exists, we want to find one that has the maximum effect on the increase of the max flow.
Give an algorithm to solve this problem. Prove the correctness and analyze the running time of your algorithm. For full marks, your algorithm must be more efficient than brute-force.
Page 5 of 10
August 2018 FINAL EXAMINATION CSC373H1Y
Question 4. (Linear Programming and Approximation) [20 MARKS]
Show how to formulate problems (a) and (b) on this page as {O, 1} integer programming (IP) problems.
Part (a) [4 MARKS]
A film producer is seeking actors and investors for his new movie. There are n available actors, and actor i charges s, dollars. For funding, there are m available investors, and investor j will provide Pj dollars, but only on the condition that certain specific actors Lj <;;: {l, 2, ... ,n} are included in the cast (*all* of the actors in Lj must be included in order to receive funding from investor j). We want to find a set of actors and investors for the movie that maximizes the producer's profits (total funding from the investors minus total cost of actors).
Part (b) [4 MARKS]
Given a network N = (V, E) where each node v E V - {s, t} has a "loss coefficient"