**Unformatted text preview:**

CS570 Analysis of Algorithms Summer 2006 Final Exam Name: _____________________ Student ID: _________________ Maximum Received Problem 1 20 Problem 2 20 Problem 3 20 Problem 4 20 Problem 5 201) 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 space3) 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. a b c d e f 3 1 2 4 5 6 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 space4) 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 space7) Additional

View Full Document