Divide and Choose
Results and report are due
at the start of
class on
Wednesday, Jan 28
Overview
In lecture, we studied the
Divde and Choose algorithm. In this lab you will program the technique,
apply it to some data, and write a short report about your results.
You are encouraged to work in groups of up to 3 people on this project.
Your group submits just one report, coauthored by all group members.
Data
- Testing: each is 100x100 data points in a CSV file
- Homogeneous Use this same data set for each player's preferences.
- 1/2 chcolate, 1/2 vanilla: same cake but two different views
- Random
- Abstract Israel 1000x1000 CSV file
(map)
Procedure
The program you write should simulate a divide and choose situation. For each
of the above data sets, run your program under each of the following conditions:
- P1 cuts, P2 chooses
- P2 cuts, P1 chooses
Report (due Jan 28, start of class)
Write between 2-5 pages describing the results you have seen. In your
report, include the following:
- The names of the people in your group
- For each of the cakes:
- Homogeneous
- chocolate/vanilla
- Random
- Israel
describe the results of your divide-and-choose procedure:
- How did the cutter try to find 1/2 value in the cake?
- For example, by column?
- By row?
- Diagonally
- ???
- What value did the cutter receive?
- What value did the chooser receive?
- Gedankenexperiment (thought exercise)
Suppose the cutter wants to find a collection of cells in the cake (spreadsheet)
whose
sum is closest to 1/2. Those cells need not be compact or contiguous.
How hard is this problem in general?