UC Berkeley—CS 170 Problem Set 10Lecturer: David Wagner Due on April 24 at 3:30 p.m.Problem Set 10 for CS 170FormattingPlease use the following format for the top of the solution you turn in, with one line peritem below (in the order shown below):<your username on cory.eecs><your full name>CS170, Spring 2003Homework #10Section <your section number>Partners: <your list of partners>(Remember to write your section number, not the name of your TA or the time of yoursection.) This will make it easier for us to sort and process your homeworks. Thank you!NoteWhen asked for an algorithm you must give (1) a brief informal description of the algorithm,(2) a precise description using pseudo-code, (3) an informal argument for termination andcorrectness of the algorithm, and (4) an analysis of the running time of the algorithm.Exception! (added 4/21) For Problems 1 and 2, regarding the running time: it sufficesto state that your algorithm is polynomial time (it had better be!), and briefly say why.New! In addition, when specifying a linear programming problem, please first list a tableof variables and their intended meaning, before the system of linear inequalities itself.Problem 0. [Any questions?] (5 points)What’s the one thing you’d most like to see explained better in lecture or discussion sections?A one-line answer would be appreciated.(Sometimes we botch the description of some concept, leaving people confused. Some-times we omit things people would like to hear about. Sometimes the book is very confusingon some point. Here’s your chance to tell us what those things were.)Problem 1. [Henron] (30 points)You’ve been hired by Henron, a new startup with this great idea to make a killing bycreating a market for chicken futures. Henron has relationships with a set of n suppliersand a set of m purchasers. The i-th supplier can supply up to s[i] chickens this year, andthe j-th purchaser would like to buy up to b[j] chickens this year. Henron is the middlemanProblem set 10 due on April 24 at 3:30 p.m. 2and makes $1 off each chicken that is sold. Thus, the more chickens that are sold, the moremoney you make!However, there’s a complication. Due to federal restrictions on interstate trafficking inavian life forms, supplier i can only sell chickens to a purchaser j if they are situated atmost 100 miles apart. Assume that you’re given a list L of all the pairs (i, j) such thatsupplier i is within 100 miles of purchaser j. You will be given n, m, s[1..n], b[1..m], L asinput. Your job will be to compute the maximum number of chickens that can be sold thisyear.(a) Formulate this as a network flow problem.(In other words, show how to solve this problem, using a network flow algorithm as asubroutine.)(If you can show your graph, that might help the readers.)(b) Formulate this as a linear programming problem.(In other words, show how to solve this problem, using a linear programming algorithmas a subroutine.)(c) Let’s assume you don’t care about the running time of your algorithm. Which formu-lation would be better, network flow or linear programming?Hint: You can’t sell fractional chickens. (Can you imagine the mess?)Problem 2. [Optimal Gerrymandering] (25 points)It will soon be election time in Upper Moldavia, and things don’t look good for the Repub-licrat party: the majority of Upper Moldavians plan to vote Democan next year. However,the Republicrat party has a secret weapon up their sleeve: they control the committee thatwill be drawing up the map of voting districts1. The election will be winner-take-all: ineach district, whichever party gets the most votes receives one representative elected to theMoldavian Senate. Your job will be to find an algorithm the Republicrats could use tomaximize the number of representatives elected for their party next election.There are n counties in Upper Moldavia. Exactly riof the residents in county i areRepublicrat, and the other diresidents are Democan. No one votes for a third party. Inyour power as mapmaker, you must build m voting districts by amalgamating pieces fromthe various counties. A district can be made up of many portions of many counties, andeach portion can be obtained by drawing off any fraction fi,jof the i-th county towards thej-th district (thereby adding fi,j·riRepublicrats and fi,j·diDemocans to the j-th district).For instance, district 1 might be composed of12of county A and13of county B; district 2might include13of county A and all of county C; and district 3 might include16of countyA and23of county B.You are subject only to the restrictions that each of the m districts you draw up mustcontain at least 106voters, and that every voter is in exactly one district. Your algorithmwill receive as input the values n, m, ri, di. You must find the districting assignment (given1Hey, if it was good enough for Governor Gerry, maybe it’s good enough for Upper Moldavia...Problem set 10 due on April 24 at 3:30 p.m. 3by the fi,j’s) that maximizes E, the number of Republicrat representatives that will beelected under your assignment.Clarification! (added 4/22) Any algorithm that is polynomial in n and m will suffice.Your algorithm does not need to be polynomial in lgm.Hint: binary search, linear programming.Problem 3. [A Faster Network Flow Algorithm] (40 points)Let G be a connected, weighted graph, with source s and sink t. Let f denote the capacityof the maximum flow in G. The capacity of an augmenting path is the smallest of theweights on the edges along the path. By “show”, I mean “give an informal argument.”(a) Show that the maximum flow in G can always be found by some sequence of at most|E| augmenting paths.(In other words, show that if Ford-Fulkerson gets really lucky at every stage, it is alwayspossible for Ford-Fulkerson to terminate after at most |E| iterations.)Hint: Choose the paths after finding the maximum flow.(b) Show that, if we consider this set of ≤ |E| augmenting paths, the average path-capacityis at least f/|E|.(c) Show that there is some augmenting path in G with capacity at least f/|E|.(d) Show that, if we take the best augmenting path at each iteration, then O(|E| lg f )iterations of the Ford-Fulkerson algorithm suffice. (By “best”, I mean the augmentingpath with largest capacity.)Hint: After picking the first augmenting path, how much (as measured in capacitynot yet found) of the maximum flow remains to be found? How about after the secondaugmenting path? And so on.Hint: (1 − 1/|E|)|E|<