Typically, the clearest way to explain an algorithm is in English, with the use of some notation. A clear explanation followed by annotated pseudo-code is also fine.

Remember that when a problem asks you to design an algorithm, you must also prove the algorithms correctness and analyze its running time, i.e., the running time must be bounded by a polynomial function of the input size.

(3) (10 points) In American politics, gerrymandering refers to the process of subdividing a region into electoral districts to maximize a particular political party's advantage. This problem explores a simplified model of gerrymandering in which the region is modeled as one-dimensional. Assume that there are n>0 precincts represented by the vertices v1,v2,,vn of an undirected path. A district is defined to be a contiguous interval of precincts; in other words a district is specified by its endpoints ij, and it consists of precincts vi,vi+1,vi+2,,vj. We will refer to such a district as [i,j]. Assume there are two parties A and B competing in the election, and for every 1ijn,P[i,j] denotes the probability that A wins in the district [i,j]. The probability matrix P is given as part of the input. Assume that the law requires the precincts to be partitioned into exactly k disjoint districts, each containing at least smin and at most smax nodes. You may also assume the parameters n,k,smin,smax are chosen such that there is at least one way to partition the precincts into k districts meeting the specified size constraints. Your task is to find an efficient algorithm to gerrymander the precincts into k districts satisfying the size constraints, so as to maximize the expected number of districts that A wins