CS570 Analysis of Algorithms Fall 2007 Exam Name Student ID DEN circle YES NO Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Total Note The exam is closed book closed notes Maximum 20 15 20 10 20 15 100 Received 1 20 pts Mark the following statements as TRUE FALSE No need to provide any justification TRUE FALSE The runtime of Ford Fulkerson is bounded by O E f where E is the number of edges in the graph and f is the maximum flow in the graph and capacities are real TRUE FALSE If all edge capacities in a graph are integer multiples of 5 then the maximum flow value is a multiple of 5 TRUE FALSE For any graph with edge capacities and vertices s and t there always exists an edge such that increasing the capacity on that edge will increase the maximum flow from s to t in G Assume that there is at least one path in the graph from s to t TRUE FALSE Let G be a flow diagram a directed graph with edge capacities and let k be a positive number Then there is a flow through G of size k if and only if the edges out of the start node have capacities adding to at least k and the edges into the finish node have capacities adding to at least k TRUE FALSE In O V E time a matching in a bipartite graph G V E can be tested to determine if it is maximum TRUE FALSE By definition all dynamic programming algorithms must have polynomial complexity TRUE FALSE The time complexity of Ford fulkerson algorithm is polynomial TRUE FALSE If a directed graph has n vertices and n n 1 2 edges then it has a directed cycle TRUE FALSE For any maximum flow allocation for all pairs u v either flow in edge u v or flow in v u must be 0 TRUE FALSE Dijkstra s algorithm asymptotically beats the Bellman Ford algorithm at solving the single source shortest paths problem 2 15 pts You have N dollars to spend on game software There are m games available with prices in dollars cj j 1 m assume all cj s are positive integers Each game has a rating rj which is also a positive integer Your goal is to buy games with total price at most N dollars so as to maximize the sum of the ratings of the games bought Give a dynamic programming algorithm to solve this problem 3 20 pts The roads in the region including Point A and Point B are represented by an undirected graph with n nodes including A and B and m edges where an edge means that a road may be traversed in either direction An accident prevents drivers from using the road in either direction Transportation planners want to know the smallest number of simultaneous accidents which in the worst case could prevent all travel from Point A to Point B a Describe an efficient algorithm that determines this number and determine its running time as a function of m and n b If the path exists how can we determine if it is unique 4 10 pts a Prove or disprove If the capacities of edges in a flow network G are increased and the total increase of all edge capacities is k then the value of a maximum flow of G increases no larger than k b Prove or disprove For a given flow network we know that edge e is on a minimum cut If over time the nodes in this network start leaking in other words flow out of the node 1 flow into the node then e may no longer be on a minimum cut 5 20 pts Let G V E be an undirected graph of n vertices and m edges such that every edge e of E has a weight w e 0 w e is a real number For any input integer k 0 and two vertices s and t of G a k edge shortest path in G is defined as follows It is an s to t path in G that consists of no more than k edges and that has the minimum total sum of edge weights among all possible s to t paths in G with no more than k edges Design an efficient algorithm to compute a k edge shortest path in G 6 15 pts a For the flow network given below calculate the maximum flow and draw the residual graph corresponding to this flow 6 1 10 S A 2 B 2 C 4 1 20 5 10 12 G T 5 4 D 2 E 6 F b Identify a minimum s t cut in this flow network c Is the minimum s t cut unique i e are there other s t cuts in this graph with same capacity Additional Space Additional Space
View Full Document
Unlocking...