Bad news. The political consulting company you work for has collapsed following a highly-publicized financial scandal. Good news. Those employees who didn't go to jail or flee the country have reorganized the company, with you as chief programmer, for which you will be paid only in nearly worthless stock (but lots of it). If you can finish the redistricting job satisfactorily by the court-mandated deadline, you might rescue the company's stock price and make yourself a zillionaire (so that you can help the needy, of course, not for yourself).
| Back to the Warm Up
Instructions Warm Up Map files for testing Warm Up snapshots. Offsite info by Chris Ross (Unofficial! not part of 143 website): Snapshots, Compiled Project Info. Warm Up starter code directory |
Back to the Step Up
Instructions Step Up snapshots Step Up Map files for testing. Files of the old format are still valid (and should be tested!)
Sample solution for the Step Up. (includes a new Map Factory). Javadoc for the sample solution for the Step Up. Covers all solution source files, plus files like MGeomUtils for which source is not provided. |
Wrap Up
New! Egg Timer class. README file. Javadoc. .jar file with all required classes (and a copy of the Javadoc, slightly outdated). The classes in a directory structure. Check the typo correction in the next to last paragraph! New 12/10! A treasure trove of all 50 state maps, with counties, and high-precision coordinates. |
Deadlines (more details below). Part d: Tuesday, November 26. Part e: Wednesday, December 4. The description below is essentially for Part e. Part d is simpler, but you have to read the entire part e description to understand how Part d is different.
For the last part of this project, group the counties into congressional districts of approximately equal population. Such a grouping is called a "redistricting." For reference, the constitutional and statutory basis of congressional representation may be found at the link at the top of the page. Here we will stick to a simple model of redistricting.
A valid "district" is a set of contiguous counties.
"Contiguous" (or adjacent) counties share at least one segment or part of a segment. The shared portion must be of length greater than zero. Counties which have a common vertex (point) but no common boundary are not considered adjacent.
Each county must belong to exactly one district. A county cannot be split across more than one district.
The number of districts (N) is not something the program has to compute. It will be a user input (details below). A valid number of districts is an integer greater than 0. (However, for large enough integers, there may be no possible redistricting, which is a fact the program should detect and report). Districts are numbered from 1 to N. There is no requirement about which district gets which number.
Goodness. It is usually impossible to find an exactly perfect redistricting. For example, if the state has just three counties, of 100 people each, and two districts are required, then one district will have 200 people and the other will have 100; the perfect but impossible distribution would be 150 people in each district. For this reason, there needs to be a "goodness" value computable for any redistricting. For this project, use "average absolute mean difference" (see below).
Depending on the algorithm you use, it may take a long time for your program to find a "good" redistricting. Your program must not take too long to find and display a redistricting! This means you should display some sort of attempt as soon as you find it, rather than waiting until you have something perfect. If that first attempt is not very good, the program may continue (automatically) to look for better ones, as long as as increasingly better ones are being produced at a reasonable rate. This all sounds a bit complicated, and will take some further discussion (outside of this page) on questions about timing, grading, etc., and we might supply some helper code along these lines. For now, the message is: a solution which takes forever is as bad as no solution at all. Your program will be graded to some extent on how "good" a solution it finds in a given time span.
File format: no change. But be sure that your program properly handles all legal files (as defined in previous projects), and deals appropriately with illegal data. As before, appropriately means that the program shows awareness that something is wrong (by an exception, assertion, error message, graphical display, etc.). In the case of an invalid file, it is not necessary to attempt a solution; attempting to recover is purely optional. In any case, the program should not blow up without warning.
Display requirements. The basic screen display is as before, with a few changes described below. Be sure that your program now properly fulfills those older requirements (such as filling the counties with color, drawing the state boundary in a different color from the county boundaries, drawing the county seat names and locations, etc. etc.)
On the map panel, color-code the districts, That is, fill counties which are in the same district with the same color (or in closely related colors). Different districts should have distinctly different colors [Note: as an alternative to color-coding, you may indicate districts with a border around each district]. On each county, draw the name of the county (all caps). It might help legibility to make the county seat names smaller.
On the text panel, display the list of counties in alphabetical order. Display each line of county information in the same color as is used for than county on the map panel (doesn't apply f you drew district borders instead of using color coding on the map panel). Include the district number for each
districtcounty.Add a third panel for district information. On it, place the textbox mentioned earlier where the user inputs the number of districts. Give a district summary, which for each district tells how many counties are in it, and what the total population is. (This summary and other text information is best placed in a subpanel). Also, display the "goodness" of the redistricting.
For grading purposes, please also display the following information on the system console (essentially the same information as is on the screen): a list of all counties, in alphabetical order, showing which district they belong to, and a list of the districts, giving, for each one, its total population. Finally, display the "goodness" of the redistricting
Internal Requirements: If you have not already done so, structure your code in the direction of a MVC (model/view/controller) philosophy. See Step Up instructions; will also be discussed in class; and see textbook chapter 20. You may consider that the Step Up sample solution qualifies as sufficiently MVC. Caution: don't destroy a working program by rapidly and radically reorganizing it! And don't attempt any reorganization at the last minute... a word to the wise.
As usual, follow reasonable and accepted coding practices. It is not necessary to stick exactly to Sun's standard as long as what you do is equivalently clear, consistent, and complete.
Do write Javadoc comments as appropriate. Generate Javadoc for you solution files (any source files that you turn in), and print it off to turn in.
Groups of two people are allowed (and recommended!).
Part d specifics. Electronic turn-in Tuesday evening (9:00), November 26; paperwork in lecture on Wedesday.
For Part d, the program uses a fixed number of districts (2), which can be a constant in the program (no user input required). Instead of dividing according to population, the program finds a valid division of the N counties into 2 valid (contiguous) districts, each with N/2 or (N+1)/2 counties (this simplified problem is equivalent to the case where all counties have equal population.) No third display panel is required, nor is the district summary information. The map panel and text panel should implement the additional requirements on them as described earlier, except that sorting by name is not required. No information need be displayed on the system console. "Goodness" information need not be calculated or displayed. MVC structure and printed Javadoc are not required.
A final note: the testing we do for grading this part will use only valid files, and a relatively small number of counties (say, <=20). You should nevertheless run your program on larger maps and observe its behavior. In particular, before you turn in the project, run it on at least one map of 300 points and 50 counties, and make note of what happens.
Click here to submit part d electronically.
Part e specifics. Electronic turn-in Wednesday evening (9:00pm), December 4. In addition to the requirements listed, there will be written reports of some type (more information later). Also, the testing will be more extensive, and will be complicated by timing requirements.
Click here to submit part e electronically.
Goodness metrics (more may appear here later).
"Average absolute mean difference" is defined as follows: The ideal
mean number of people in each district would be the total state population
divided by N (the number of counties
districts). For each district, compute the
difference, as an absolute value, between the ideal district population and the
actual district population. Add all those absolute differences together,
and divide by N. This we will call the "Average absolute mean difference."
In some sense, this is the average number of people per district who are over-
or under- represented -- sort of.
Many other goodness metrics (or "objective functions") could be defined. The "root mean squared" metric is particularly common for this kind of problem. It's harder to give it a non-mathematical explanation, but in general, it's the one to use by default if you have no reason to choose another one.