CS570 Analysis of Algorithms Fall 2006 Final Exam Name: _____________________ Student ID: _________________ Maximum Received Problem 1 20 Problem 2 15 Problem 3 15 Problem 4 15 Problem 5 15 Problem 6 20 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 )).nlog(n()n(T2⋅=Θn3)2n(T2)n(T ⋅+= [ 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 TrueUnknownUnknownFalseFalseFalseTrueTrue2) 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 and number t Task: Determine if there exists a subset of the whose sum equals t? n1n321a,a...,a,a,a−s'ai5) 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 SpaceAdditional SpaceAdditional
View Full Document
Unlocking...