## 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?