UNIVERSITY OF TORONTO Faculty of Arts and Science
AUGUST 2019 EXAMINATIONS
CSC 373H1Y Instructor(s): Koushik Pal
Duration — 3 hours
Copyright By PowCoder代写 加微信 powcoder
Examination Aids: One 8.5” × 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 12 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 paper, 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 answers, 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 10% of the marks for that (part of the) question if you leave it blank, and 20% 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: /15 #4: /20 #5: /20
TOTAL: /85
Total Pages = 12 Page 1 of 12
cont’d. . .
PLEASE HAND IN
PLEASE HAND IN
August 2019 Final Examination CSC 373H1Y Question 1. (Dynamic Programming) [15 marks]
A subsequence is palindromic if it is the same whether read from left to right or right to left. For instance, the sequence (A,C,G,T,G,T,A,T,G,C) has many palindromic subsequences. Examples of palindromic subsequences of this sequence include (C,G,T,A,T,G,C), (A,T,G,T,A), (A) and (T,T), which have lengths 7, 5, 1, and 2, respectively.
Write a 5-step Dynamic Programming algorithm that takes an input sequence x = (x1, x2, . . . , xn), for some n ≥ 1, and returns both the length and an instance of a palindromic subsequence of the maximum length. Your algorithm should run in O(n2) time and require O(n2) space for full marks.
Student #: Page 2 of 12 cont’d. . .
August 2019
Final Examination CSC 373H1Y
Question 1.
(continued)
Student #:
Page 3 of 12 cont’d. . .
August 2019 Final Examination CSC 373H1Y Question 2. (Graph Problem) [15 marks]
Given a boolean 2D matrix A (with entries either 0 or 1), find the number of islands. An island is a group of connected 1s, where “connected” means adjacent horizontally, vertically, or diagonally. For example, the below matrix contains 5 islands:
Input: A= 1 0 0 1 1 Output: 5. 0 0 0 0 0 10101
Write down an algorithm to solve the above problem, and compute its complexity.
Student #: Page 4 of 12 cont’d. . .
August 2019 Final Examination CSC 373H1Y Question 3. (Network Flow) [15 marks]
You are given a set of profs P = {pn}Nn=1, a set of courses C = {ck}Kk=1, and the number of course sections S = {sk}Kk=1 being offered next term. Here sk is a positive integer equal to the number of different sections of course ck that need to be taught next term. In addition, for each prof pn, you are given the set of courses that he/she likes to teach, say Tn ⊂ C, along with her teaching load Ln, a nonnegative integer representing the number of courses that prof pn is assigned to teach next term. Finally, suppose the sum L = Nn=1 Ln of teaching loads is equal to the total number S = Kk=1 sk of course sections that need to be taught.
The prof-to-course assignment problem is then to assign each prof pn to exactly Ln course sections, with the courses chosen from Tn, and ensure that each section of each course gets assigned a prof.
(a) Give an efficient algorithm to solve this problem, based on network flow techniques.
(b) Explain when an assignment of profs to courses is possible.
(c) Justify that your algorithm is correct. In particular, explain how profs and courses/sections corre- spond to each other and to flows in the network.
(d) Analyze the worst-case running time of your algorithm.
Student #: Page 5 of 12 cont’d. . .
August 2019
Final Examination CSC 373H1Y
Question 3.
(continued)
Student #:
Page 6 of 12 cont’d. . .
August 2019 Final Examination CSC 373H1Y
Question 4. (Linear Programming and Approximation) [20 marks]
Part (a) [10 marks]
A calculator company produces a scientific calculator and a graphing calculator. Long-term projections indicate an expected demand of at least 100 scientific and 80 graphing calculators each day. Because of limitations on production capacity, no more than 200 scientific and 170 graphing calculators can be made daily. To satisfy a shipping contract, a total of at least 200 calculators much be shipped each day.
If each scientific calculator sold results in a $2 loss, but each graphing calculator produces a $5 profit, how many of each type should be made daily to maximize net profits? Explain your work.
Student #: Page 7 of 12 cont’d. . .
August 2019 Final Examination
CSC 373H1Y
Part (b) [10 marks]
A cut in an undirected graph G = (V, E) is any partition of the vertices into sides S ⊆ V and S = V −S. The size of a cut size(S, S) is measured as the number of edges across the cut, i.e., with one endpoint in S and the other in S. For any cut (S, S) and any vertex v ∈ V , “cut(v)” represents the set of edges adjacent to v that cross the cut, and “uncut(v)” represents the set of edges adjacent to v that do not cross the cut. For example, cut(c) = {(a, c), (c, e)} and uncut(c) = {(b, c), (c, d)} for the graph pictured on the right, where S = {a, e}.
Consider the following algorithm that attempts to find a large cut in an undirected graph G:
start with any non-empty subset S ⊂ V
while there is some vertex v ∈ V with |uncut(v)| > |cut(v)|:
dc es @ @c c@
move v from S to S (or from S to S)
Prove that for all undirected graphs G, this algorithm will produce a cut whose size is at least 1/2 of the
maximum cut size for G.
Student #: Page 8 of 12 cont’d. . .
August 2019 Final Examination CSC 373H1Y
Question 5. (NP-Completeness) [20 marks]
Part (a) [3 marks]
Let A and B be decision problems. Show that if A ≤p B, then A ≤p B (where A is the complement of A).
Part (b) [5 marks]
Show that if A is NP-complete and A is in coNP, then NP = coNP.
Student #: Page 9 of 12 cont’d. . .
August 2019 Final Examination CSC 373H1Y Part (c) [12 marks]
Consider the following SteinerTree decision problem.
Input: A connected undirected graph G = (V, E) with an integer length l(e) ∈ N for each edge e ∈ E, a
subset N ⊆ V of vertices called terminals, and a nonnegative integer k.
Question: Does G contain a subtree T such that each vertex of N is on T and the total length of T is at most k? (Warning: T does not have to be a *spanning* tree, i.e., it does not have to cover each vertex in V .)
Show that SteinerTree is NP-complete. Give a detailed reduction and argument of correctness. (Hint: You can use any of the problems you know to be NP-hard from lectures, tutorials, or the textbook — except for SteinerTree itself, of course!)
Student #: Page 10 of 12 cont’d. . .
August 2019 Final Examination CSC 373H1Y Extra Page
Student #: Page 11 of 12 Cont’d…
August 2019 Final Examination CSC 373H1Y Last Page
Total Marks = 85
Student #: Page 12 of 12 End of Examination