Piazza Algorithm Debate MaximumHappyWedding:

At the end of the course, it will be easy for you to find a fast algorithm for the MaximumHappyWedding problem. Can you do it now, maybe by using knowledge from your undergraduate algorithm course? Whatever algorithm you find, keep the algorithm your secret. Only apply it to specific inputs during the debate and return the output.

Software requirements come in different forms. Most are written informally in plain English, others use a logical formalism.

As successful software engineers you need to be familiar with both. If you get a plain English description, it is beneficial to translate it to a logical formalism before you attempt an implementation.

Plain English

Claim MaximumHappyWedding() in plain English: You organize a wedding with n families and you have m tables available. To increase the social interaction, you would like to seat the family members at tables so that no two members of the same family sit at the same table. Most importantly, you want to maximize the number of seated family members. It is possible that you cannot seat all. Assume that the wedding party has n families and the i-th family has ai members. Also assume that m tables are available and the j-th table has a seating capacity of bj.

Logical Formalism

Claim HappyWedding(Families,Tables,C) =
Families fi with ai members each, i in [1..n]
Tables tj with bj seats each, j in [1..m]
0 <= C <= sum [i in [1..n]] fi.ai
Let Members be all family members: union [i in [1..n]] fi.members
Let Seats be all seats: union [j in [1..n]] tj.seats 
Let Table be a function: Seats -> Tables, returning the table
at which the seat is located
Exists function Seating: Members -> Seats 
which assigns seats to family members such that:
(1) C family members are seated; 
(2) Socializing Property holds: ForAll pairs (p,q) of 
seated family members of the same family: 
Table(Seating(p)) != Table(Seating(q))
i.e., no two members of the same family sit at the same table.

Claim MaximumHappyWedding() =
ForAll
Families fi with ai members each, i in [1..n]
ForAll
Tables tj with bj seats each, j in [1..m]
Exists C in Nat: 
(HappyWedding(Families,Tables,C)
	and
	(ForAll C' in Nat, C'>C: 
		!HappyWedding(Families,Tables,C')
	)
)

When you make claim MaximumHappyWedding() you should be equipped with an algorithm that finds the maximum seating assignment: There is no other seating which seats more members.

Notation

To avoid confusion during the debates, we choose a notation to be used by all. It is based on the JSON standard. How to make a claim HappyWedding(Families,Tables,C):

Provide a specific set of families [a1,a2,a3, ... ,an] and tables [b1,b2,b3, ... ,bm] and provide your maximum C. For example: claim HappyWedding([3,4,5,6],[3,4,5,6],12).

During the debate, Seating-objects are exchanged. We use the following notation:

[
[f4.1,t4.1] ,// member 1 of family f4 is seated at seat 1 of table t4
...

Sample Debate

Alice makes the claim MaximumHappyWedding() which claims that she can find the best seating, no matter what the legal input. Bob will challenge Alice and be the Falsifier. The debate might go as follows: Bob, the Falsifier, provides families = [3,4,5,6], tables = [3,4,5,6]. Alice, the Verifier, provides C=12. Bob finds a weakness in Alice and he claims HappyWedding([3,4,5,6],[3,4,5,6],15) falsifying Alice' claim. Bob supports his claim HappyWedding([3,4,5,6],[3,4,5,6],15) with the following function Seating:

[
[f4.1,t4.1] ,// member 1 of family f4 is seated at seat 1 of table t4
[f4.2,t3.1],
[f4.3,t2.1],
[f4.4,t1.1] ,// two of f4 not seated
[f3.1,t4.2],
[f3.2,t3.2],
[f3.3,t2.2],
[f3.4,t1.2] ,// one of f3 not seated
[f2.1,t4.3],
[f2.2,t3.3],
[f2.3,t2.3],
[f2.4,t1.3] ,// f2 completely seated, t1 is full
[f1.1,t4.4],
[f1.2,t3.4],
[f1.3,t2.4]// f1 completely seated, t2 full
]

Bob has won as Falsifier. Alice needs to go back and improve here algorithm. Both Alice and Bob keep their algorithm secret.

What to turn in

What to turn in for question MaximumHappyWedding: The debate histories in your group of three by giving a link to your private group on Piazza. The claim is MaximumHappyWedding() and the position chosen by all is Verifier (because the claim is trivially true). You do one half of a full-round robin tournament of debates which is binomial(3,2)=3 debates. Each student participates only in 2 debates. In each debate one of the players is forced randomly, i.e., playing the devil's advocate role. The third player has the role of admin: she makes sure that the game rules are properly followed.

Turn in a link to your Piazza group and the following statistics: For each player: number of losses where player was not forced. Go to the groups tab on the Piazza course page and sign up for a group if you have not done so yet. It is recommended that one Piazza note is edited to record one entire debate. Suggested format:

Computational Problem: 
Player 1:       Chosen Side:
Player 2:       Chosen Side:
Admin: (can also be played by both players jointly)
Who is forced: (none or one of the players)
Move 1:
Move 2:
Move 3:
...
winner:

Preparation for next stage

Each team selects a member R with the minimum number of losses to represent the team in the next round. The side chosen by this member R is the side chosen by this team. Other team members can support R in R's moves in future debates. The triple (R, number of losses in non-forced side, time_stamp) has to be returned. The time stamp indicates when R lost last time in non-forced side. time_stamp = (month,day,year,hour). If R never lost in non-forced side, the time stamp is absent.

It is useful to know R because R might be a helpful resource to learn from and useful in future debates.