CIT 590/591 Assignment 4: Party time!
Fall 2012, David Matuszek

Purposes of this assignment

Backstory

Congratulations! You have just won $9.3M in the lottery! Now you want to throw a huge party to celebrate. You want as many people as possible to come to your party.

Unfortunately, not everyone that you know likes everyone else....

General idea of the assignment

For any two people X and Y:

The above is always true, and will constrain who you should invite to the party. Partly because you have a partner in this assignment, write this program with two different (but similar) sets of constraints. I recommend that you work together to figure out how best to solve the problem, then each take primary responsibility for one constraint set.

Constraint set #1: Absolute constraints

Constraint set #2: Relative constraint

Detailed specification

Requirements

Critical requirements

I will test your program with my data. To make this possible, your program must satisfy the following requirements:

Style requirements

Advice

I have specified the form of the input data, so that I can test your program with my own data.

I have not told you what kind of data structures to use to store and work with this data. Try to choose a representation that is easy to work with. You have lists, tuples, sets, and dictionaries, and combinations of these (lists of lists, sets of dictionaries, sets of lists of tuples, etc.). Your choice will have a major impact on how easy or difficult the program is to write, so think carefully about this.

This is an exponential problem. You can find a guaranteed optimal solution to small problems by trying every possible combination of people. For p people, that's 2p combinations. By using various tricks, you can reduce this number, but the problem will remain inherently exponential. That means that, given more than a couple dozen people, your program would run for a very, very long time, maybe years. We won't accept a program that takes years to run! Remember, the assignment is to find a reasonably good solution, in a reasonable amount of time.

How do you do this? Well, if you have (say) 100 friends, you cannot try all 2100 subsets of them. Instead, try to form various legal subsets of your friends--that is, subsets that satisfy whichever constraint you are using. You could try (depending on how you write the program) maybe as many as 10000 possible subsets. Think about ways you might create legal random subsets. Keep track of the largest legal subset you find, and that will be your answer.

Grading

It would be a good idea to read How Assignments Are Graded, but here's a summary: Do exactly what the assignment says to do, use good programming style, test your program carefully, zip up your program along with your unit tests, and turn it in via Blackboard. Late programs will lose points.

Due Date

Your program is due before