CS570 Analysis of Algorithms Fall 2006 Final Exam Name Student ID Received Maximum 20 15 15 15 15 20 Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Note The exam is closed book closed notes 1 20 pts Mark the following statements as TRUE FALSE or UNKNOWN No need to provide any justification TRUE FALSE P is the class of problems that are solvable in polynomial time TRUE FALSE NP is the class of problems that are verifiable in polynomial time TRUE FALSE It is not known whether P NP TRUE FALSE If an NP complete problem can be solved in linear time then all the NP complete problems can be solved in linear time TRUE FALSE Maximum matching problem in a bipartite graph can be efficiently solved thru the solution of an equivalent max flow problem TRUE FALSE The following recurrence equation has the solution n T log n n 2 n T T2 n3 n 2 TRUE FALSE UNKNOWN If a problem is not in P it should be in NP complete TRUE FALSE UNKNOWN If a problem is in NP it must also be in P TRUE FALSE UNKNOWN If a problem is NP complete it must not be in P TRUE FALSE Integer programming is NP Complete 2 15 pts A cargo plane can carry a maximum of 100 tons and a maximum of 60 cubic meters of cargo There are three materials that need to be carried and the cargo company may choose to carry any amount of each up to the maximum amount available of each Material 1 has density 2 tons cubic meter maximum available amount 40 cubic meters and revenue 1000 per cubic meter Material 2 has density 1 tons cubic meter maximum available amount 30 cubic meters and revenue 1200 per cubic meter Material 3 has density 3 tons cubic meter maximum available amount 20 cubic meters and revenue 12000 per cubic meter Write a linear program which optimizes revenue within the given constraints 3 15 pts Given two sorted arrays a 1 n and b 1 n present an O log n algorithm to search the median of their combined 2n elements 4 15 pts Present an efficient algorithm for the following problem Input n positive integers a a a 3 2 1 a 1n a n and number t Task Determine if there exists a subset of the whose sum equals t s ai 5 15 pts There are M faculties and N courses Every faculty chooses 2 courses based on his her preference A faculty can teach zero one course or two courses and a course can be taught by one faculty only Find a feasible course allocation if one exists A feasible course allocation allows a faculty to teach only the courses he she prefers 2 20 pts In a weighted graph the length of path p v0 v1 vk is the sum of the weights of its constituent edges A path is simple if all vertices in the path are distinct Let D denote an algorithm for the decision version of the longest path problem The input consists of a weighted connected undirected graph G V E along with an integer k The output is yes if and only if G has a simple path of length k or more a Give an algorithm that uses D to compute the length of the longest path You don t have to output the actual path b True False The longest path problem is NP complete If True prove it If False disprove it Additional Space Additional Space Additional Space
View Full Document
Unlocking...