LAST (Family) NAME: FIRST (Given) NAME:
STUDENTNUMBER:~~~~~~~~~~~~~~~~~~~ UNIVERSITY OF TORONTO
Exam Reminders:
• •
• • • • •
Fill out your name and student number on the top of this page.
Do not begin writing the actual exam until the announcements have ended and the Exam Facilitator has started the exam.
As a student, you help create a fair and inclusive writing environment. If you possess an unauthorized aid during an exam, you may be charged with an academic offence.
Turn off and place all cell phones, smart watches, electronic devices, and unauthorized study materials in your bag under your desk. If it is left in your pocket, it may be an academic offence. When you are done your exam, raise your hand for someone to come and collect your exam. Do not collect your bag and jacket before your exam is handed in.
If you are feeling ill and unable to finish your exam, please bring it to the attention of an Exam Facilitator so it can be recorded before leaving the exam hall.
In the event of a fire alarm, do not check your cell phone when escorted outside.
Faculty of Arts & Science DECEMBER 2018 EXAMINATIONS
CSC373H1F
Duration: 3 hours
Aids Allowed: 1 double-sided aid sheet
Soecial Instructions:
Please put your name on each page of this final. You should read through the whole final, and start with the problem you find easiest. You will get more credit for doing one problem well then for doing two poorly. Ifyou cannot answer a question, you will receive 20% ofthe marks for that question if you leave it blank. Good luck.
Exam Format and Gradina Scheme:
This exam consists of 5 problems (each with multiple sub-problems) worth together 110 points. See table to the right for specific grade breakdown. You must achieve a 40% grade on the final to pass the course. Please write all your answers on the exam handout.
Problem 1 /20 Problem 2 /16 Problem 3 /22 Problem 4 /37 Problem S /15 Total /110
Students must hand in all examination materials at the end
Name:
Problem 1 (20 points):
Consider a round-robin chess tournament with n players with each player playing every other player exactly once. A win scores 1 for the winner and 0 for the loser, while a draw scores 1/2 for each player. We are given a set offinal scores (s1…sn) for the players. We want to check whether these scores are feasible. For example, in a four-player tournament, with 6 games, a set of final scores of (3,3,0,0) is impossible.
(A; 12 points) Design an algorithm that can solve this problem. You may want to recall bipartite graphs and network flows.
2/11
Name:
(B; 3 points) Explain the running time of your algorithm. Carefully explain the input size of any problem you reduced to, relative to the original input.
(C; 5 points) Prove or provide a counter-example to the following statement: If the set of scores only contains integers, and it is feasible, then it is also feasible in a tournament where no draws took place.
3/11
Name:
Problem 2 (16 points): Woody the woodcutter will cut a given log ofwood, at any place you choose, for a price equal to the length of the given log. Suppose you have a log of length L, marked to be cut in n different locations labeled 1,2, … , n. For simplicity, let indices 0 and n + 1 denote the left and right endpoints of the original log of length L. Let di denote the distance of mark i from the left end of the log, and assume that 0 = dO < di < d2 < ... < dn < dn+1 = L. The wood-cutting problem is the problem of determining the sequence of cuts to the log that will cut the log at all the marked places and minimize your total payment.
(A; 12 points) Design an algorithm that can solve this problem. Ifyou are using a dynamic programming algorithm explain your semantic array. Ifyou are reducing this to another problem, carefully explain the reduction. For full credit your algorithm should be maximally efficient.
(B; 4 points) Explain the running time ofyour algorithm.
4/11
Name:
Problem 3 (22 points): LP
Consider the following problem: your company purchases copper for $1O/kilogram and tin for $2/kilogram. From purchased goods you can make bronze, which consists of 7/8 copper and 1/8 tin, and which you can sell for $15/kilogram (assume you do not need to pay for the manufacturing). You are required by local regulations to buy copper and tin at at most a 5: 1 ratio (i.e. if you buy lkg of tin, you cannot buy more than 5kg of copper). Every day you can purchase between 2 and 20kg of copper and between 1 and 5kg of tin, which do not have to be integral.
(A; 6 points) Formulate this problem as a Linear Program; that is write a set oflinear equations/inequalities and an optimization criteria that would yield the largest profit per day.
(B; 6 points) Draw the feasible space. Label the vertex corresponding to the optimal solution and compute the profit at that vertex.
tin
5/11
copper
Name:
(C; 3 points) Write the LP in standard (matrix) form for the problem in part (A)
(D; 7 points) Write the dual LP for the primal problem you design in part (A)
6/11
Name:
Problem 4 (37 points):
Show by appropriate polynomial time transformations that the following problems are NP- hard and therefore also NP complete.
A; 9 points) Consider the restricted case of 3SA T in which each literal appears in at most 2 clauses (u and its complement are considered distinct literals). Show that this problem is NP complete by reduction from standard 3-SAT. (Hint: how would you write A --+ B --+ C --+ D --+ A in Conjunctive Normal Form?)
B; 9 points) Show that the small degree independent set decision problem is NP complete:
Given a graph G = (V, E) ofmaximum degree 4, and an integer k, decide ifG has an
independent set ofsize at least k. You can assume the result in part A even ifyou could not prove it.
7/11
Name:
C; 9 points) Show that the following small size set packing problem is NP complete: Given a collectionCofsetsSic U,witheachISd~4,andanintegerk,decideifthereisasubcollectionCo consisting of at least k disjoints sets Si. You can assume the results in parts A and B of this problem even if you could not prove them.
D; IO points) The optimization problem related to the one in part (C) is the following: Given a collection
C ofsets Sic U, with each ISd ~4, output a subcollection Co that maximizes ICol; that is, that maximizes the number ofdisjoint sets. In the weighted version ofthe optimization problem, each set Si EC has a weight Wiand the objective is to output a subcollection Co so as to maximize the sum ofweights SiECo Wi. Describe an approximation algorithm for the weighted small size set packing optimization problem. What is the approximation ratio of your algorithm? Indicate how you would prove the stated approximation ratio. Full credit for a reasonable proofbut partial credit for indicating an approach.
8/11
Name:
Problem 5 (15 points):
You are given an algorithm P for computing the product C =A·B oftwo nxn matrices with integer entries. The designers ofthe algorithm claim that Puses only O(n2·2) integer arithmetic operations (i.e.+,-, *). You are a little dubious but decide to use a randomized algorithm to try to verify ifthe algorithm is working correctly before trusting the output of algorithm P. Describe a one-sided randomized algorithm V that is given n x n matrices A, B, C and uses only O(n2) arithmetic operations to verify that C = A · B in the following sense:
• If A =B · C, your algorithm V will say "YES"
•IfA;f.B ·C,youralgorithmwillsay''NO"withprobabilityatleast1- l/n
9/11
Name:
This page is left blank as scratch paper or for solutions that are longer than allocated space
10111
Name:
This page is left blank as scratch paper or for solutions that are longer than allocated space
11/11