CS570 Analysis of Algorithms Fall 2007 Exam Name: _____________________ Student ID: _________________ DEN (circle YES/NO) Maximum Received Problem 1 20 Problem 2 15 Problem 3 20 Problem 4 10 Problem 5 20 Problem 6 15 Total 100 Note: The exam is closed book closed notes.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 nb- 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. SABCDEFGT6 1 10 20 2 2 4 4 5 5 6 2 1 10 12b- 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 SpaceAdditional
View Full Document
Unlocking...