CS570 Analysis of Algorithms Summer 2006 Final Exam Name Student ID Maximum 20 20 20 20 20 Received Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 1 20 pts Decide whether you think the following statement is true or false If it is true give a short explanation If it is false give a counterexample a Let G be an arbitrary flow network with a source s a sink t and a positive integer capacity ce on every edge e If f is a maximum s t flow in G then f saturates every edge out of s with flow i e for all edges e out of s we have f e ce b Let G be an arbitrary flow network with a source s a sink t and a positive integer capacity ce on every edge e and let A B be a minimum s t cut with respect to these capacities ce e E Now suppose we add 1 to every capacity then A B is still a minimum s t cut with respect to these new capacities 1 ce e E 2 20 pts There are n unit time tasks to be scheduled on a machine in the time interval 0 n The ith task has a deadline di a profit pi and a loss li The machine can process only one task at a time and each job must run uninterruptedly for one unit time If the ith task is complete by its deadline di you receive a profit pi but if it it completed after its deadline you suffer a loss li Give a polynomial time algorithm to find a schedule that obtains the maximum amount of net profit Analyze the time complexity of your algorithm Additional space 3 An instance of graph G E V given below represents a supply chain for a manufacturing company that produces products P1 and P2 Nodes V represent manufacturing sites with total capacity Cv and edges E represent transportation routes with capacity Ce Each product Pi takes away Wiv units of capacity when moving thru manufacturing site v Each product Pi also takes away Wie units of capacity when moving thru transportation route e Each product Pi brings a revenue of Vi and has manufacturing and transportation costs Liv and Lie at site v and route e respectively Manufacturing on both products is started at nodes 1 and 2 and completed at nodes 5 and 6 The objective is to maximize the profit associated with this supply chain b 2 5 d 3 4 1 6 a e c f Graph G Give a complete formulation of how this problem is solved and describe whether your solution is an exact solution or an approximate solution Additional space 4 Given an mxn array A of integers let f i denote for i 1 m the index of the column containing the leftmost minimum element of row i Suppose f m f m 1 f 1 a Describe in words instead of pseudo code a divide and conquer strategy that computes all the f i in O m n n logm time b Describe what your algorithm does when m 2 Write the recurrence describing the running time of your algorithm c Demonstrate that the minimum of the whole array can be computed in O m n n logm time 5 20 pts In a certain town there are many clubs and every adult belongs to at least one club The townspeople would like to simplify their social life by disbanding as many clubs as possible but they want to make sure that afterwards everyone will still belong to at least one club Prove that the Redundant Clubs problem is NP complete You may make use of the known NP completeness of the Independent Set Set Cover Vertex Cover Hamiltonian Cycle or Traveling Salesman Problems Formally the Redundant Clubs problem has the following input and output INPUT List of people list of clubs list of members of each club number K OUTPUT Yes if there exists a set of K clubs such that after disbanding all clubs in this set each person still belongs to at least one club No otherwise 6 Additional space 7 Additional space
View Full Document
Unlocking...