Consider the following function G[j, k, d, d2] = true if it is possible to allocate...

Transcribed Image Text:

Consider the following function G[j, k, d, d2] = true if it is possible to allocate k of the first j precincts to district 1 and at the same time achieve at least d, votes for party A in district 1 and at least d, votes for party A in district 2. Otherwise G[j, k, d, d2]=false. 6.1 Explain how G[j, k, d;, dz] can be used to find the solution (assuming you have already computed the solution for all relevant parameters (j = 1,...,n, k = 1,...,?, etc.)). 6.2 Write a recursion for G[j, k, d,, dz]. 6.3 Write pseudo code implementing a dynamic programming algorithm that solves the problem based on your recursion. 6.4 Analyse the space and running time of your algorithm. Consider the following function G[j, k, d, d2] = true if it is possible to allocate k of the first j precincts to district 1 and at the same time achieve at least d, votes for party A in district 1 and at least d, votes for party A in district 2. Otherwise G[j, k, d, d2]=false. 6.1 Explain how G[j, k, d;, dz] can be used to find the solution (assuming you have already computed the solution for all relevant parameters (j = 1,...,n, k = 1,...,?, etc.)). 6.2 Write a recursion for G[j, k, d,, dz]. 6.3 Write pseudo code implementing a dynamic programming algorithm that solves the problem based on your recursion. 6.4 Analyse the space and running time of your algorithm.