Suppose we're currently in the middle of some unspecified sporting season and each of a set...

 

Transcribed Image Text:

Suppose we're currently in the middle of some unspecified sporting season and each of a set of n teams have some number of wins and losses (w; and li) accumulated in their played games so far. Suppose you also know a(i, j), the remaining number of games to be played between every pair of teams i, and j (note a(i, j) = a(j, i)). Each team plays the same number of games in total in each season; that is, let a(i) = , a(i, j), then for every team i, we have wi + li + a(i) = T. Our goal is to identify all teams who have a possibility of winning the championship by winning the most games in the season. If multiple teams are tied for the same (maximum) number of wins, they are all winners! Give a polynomial time algorithm to determine the set of all teams that can still potentially win the championship. 2. Pruning Branches (15 points). While on a walk, you observe a tree where some branches are dead while others look healthy. You begin to wonder how should one prune away the dead parts of the tree to maximally preserve the live parts? To think about this more formally, you come up with the following question: Given a tree T on the vertices [1, n] rooted at vertex 1, assign each vertex an integer weight w; (note that the weight can be negative). Let the total weight of a subtree rooted at a vertex u be the sum of its vertex weights. We can modify the tree using the prune(u) operation, which removes the entire subtree rooted at a vertex u. Give an algorithm to compute the maximum weight you can achieve for the tree t by performing at most k prune operations. You can assume that the numbering of vertices in the tree ensures that all ancestors a of a node u satisfy a < u. 1. First, give an efficient algorithm for the version of the problem where our goal is to maximize the weight of the tree using an unlimited number of prune operations. (8 points) 2. Next, extend your ideas from the previous part to give an efficient algorithm for computing the maxi- mum weight of the tree obtainable using at most k prune operations. Please assume that the tree is binary for this part of the problem. (7 points) 4. Game Show (20 points). You receive an invitation to participate in a game show, where you encounter a playing field scattered with n balls. Each ball is labeled with a unique identifier i and has an associated value vi (note that vi can be negative). Your objective is to collect a subset of these balls, place them in your bag, and maximize your earnings by the end of the game. The earnings are calculated as max(0, ies vi) dollars, where S is the set of balls you've chosen. To add a twist to the game, there are m additional rules, each falling into one of the following categories: If you pick up ball i but not ball j, you will incur a penalty of x dollars. If you pick up ball i, you are required to also pick up ball j. Your task is to devise a polynomial time algorithm that determines the optimal set of balls to collect in order to maximize your prize money. Hint: Try to model the problem as minimum cut. You should create a flow network such that a cut of the graph represents the money you lose from (1) not picking a ball with positive value (2) picking a ball with negative value and (3) violating a rule, which results in a penalty. 1 Warmup. (20 points) (a) Consider the following flow network. The notation f/c on an edge means that there is f flow already passing through the edge, and that the edge has total capacity c. Is the flow maximum? If it is, state a partition of the vertices defining a minimum s, t cut. If not, list the vertices of an augmenting path and state its capacity. (5 points) S 3/3 a C 4/5 2/2 1/3 1/5 0/5 2/2 b 3/3 4/5 d (b) Consider the following flow network. The notation f/c on an edge means that there is flow already passing through the edge, and that the edge has total capacity c. Is the flow maximum? If it is, state a partition of the vertices defining a minimum s, t cut. If not, list the vertices of an augmenting path and state its capacity. (5 points) 2/3 a C 5/5 2/2 3/3 0/5 0/5 1/2 4/5 b d 4/4 (c) Given two flow networks G, G' such that the max-flow values of both networks is identical, suppose we add 1 to the capacity of every edge in both networks. Do they both still have the same max-flow value? (say Yes or No and briefly explain, i.e., give an example if No) (5 points) (d) Given two flow networks G, G' such that the max-flow values of both networks is identical, suppose we double the capacity of every edge in both networks. Do they both still have the same max-flow value? (say Yes or No and briefly explain, i.e., give an example if No) (5 points) Suppose we're currently in the middle of some unspecified sporting season and each of a set of n teams have some number of wins and losses (w; and li) accumulated in their played games so far. Suppose you also know a(i, j), the remaining number of games to be played between every pair of teams i, and j (note a(i, j) = a(j, i)). Each team plays the same number of games in total in each season; that is, let a(i) = , a(i, j), then for every team i, we have wi + li + a(i) = T. Our goal is to identify all teams who have a possibility of winning the championship by winning the most games in the season. If multiple teams are tied for the same (maximum) number of wins, they are all winners! Give a polynomial time algorithm to determine the set of all teams that can still potentially win the championship. 2. Pruning Branches (15 points). While on a walk, you observe a tree where some branches are dead while others look healthy. You begin to wonder how should one prune away the dead parts of the tree to maximally preserve the live parts? To think about this more formally, you come up with the following question: Given a tree T on the vertices [1, n] rooted at vertex 1, assign each vertex an integer weight w; (note that the weight can be negative). Let the total weight of a subtree rooted at a vertex u be the sum of its vertex weights. We can modify the tree using the prune(u) operation, which removes the entire subtree rooted at a vertex u. Give an algorithm to compute the maximum weight you can achieve for the tree t by performing at most k prune operations. You can assume that the numbering of vertices in the tree ensures that all ancestors a of a node u satisfy a < u. 1. First, give an efficient algorithm for the version of the problem where our goal is to maximize the weight of the tree using an unlimited number of prune operations. (8 points) 2. Next, extend your ideas from the previous part to give an efficient algorithm for computing the maxi- mum weight of the tree obtainable using at most k prune operations. Please assume that the tree is binary for this part of the problem. (7 points) 4. Game Show (20 points). You receive an invitation to participate in a game show, where you encounter a playing field scattered with n balls. Each ball is labeled with a unique identifier i and has an associated value vi (note that vi can be negative). Your objective is to collect a subset of these balls, place them in your bag, and maximize your earnings by the end of the game. The earnings are calculated as max(0, ies vi) dollars, where S is the set of balls you've chosen. To add a twist to the game, there are m additional rules, each falling into one of the following categories: If you pick up ball i but not ball j, you will incur a penalty of x dollars. If you pick up ball i, you are required to also pick up ball j. Your task is to devise a polynomial time algorithm that determines the optimal set of balls to collect in order to maximize your prize money. Hint: Try to model the problem as minimum cut. You should create a flow network such that a cut of the graph represents the money you lose from (1) not picking a ball with positive value (2) picking a ball with negative value and (3) violating a rule, which results in a penalty. 1 Warmup. (20 points) (a) Consider the following flow network. The notation f/c on an edge means that there is f flow already passing through the edge, and that the edge has total capacity c. Is the flow maximum? If it is, state a partition of the vertices defining a minimum s, t cut. If not, list the vertices of an augmenting path and state its capacity. (5 points) S 3/3 a C 4/5 2/2 1/3 1/5 0/5 2/2 b 3/3 4/5 d (b) Consider the following flow network. The notation f/c on an edge means that there is flow already passing through the edge, and that the edge has total capacity c. Is the flow maximum? If it is, state a partition of the vertices defining a minimum s, t cut. If not, list the vertices of an augmenting path and state its capacity. (5 points) 2/3 a C 5/5 2/2 3/3 0/5 0/5 1/2 4/5 b d 4/4 (c) Given two flow networks G, G' such that the max-flow values of both networks is identical, suppose we add 1 to the capacity of every edge in both networks. Do they both still have the same max-flow value? (say Yes or No and briefly explain, i.e., give an example if No) (5 points) (d) Given two flow networks G, G' such that the max-flow values of both networks is identical, suppose we double the capacity of every edge in both networks. Do they both still have the same max-flow value? (say Yes or No and briefly explain, i.e., give an example if No) (5 points)