# CS 1101 (A05) Homework 4: Lists of Structures

Due: September 20 (Tuesday) at 11:59pm via turnin

## Assignment Goals

To make sure you can
• write data definitions and templates for lists of structures,
• and write Scheme programs over lists of structures.

## The Assignment

### Tabulating Elections

Counting democratic elections poses a non-trivial problem. If we allow a voter to pick a sequence of choices, there are many strategies for tabulating votes. Here are three:

• the winner-takes-all strategy says that the person with the most first-place votes wins the overall election;

• the approval-rating strategy gives each person's first and second choices one point each and the candidate with the most points wins the overall election;

• the points-per-place strategy allocates 3, 2, and 1 point to each person's top three choices, respectively. Again, the candidate with the most points wins the overall election.

Not surprisingly, different strategies produce different winners. That is, given the same series of election results, the winner depends on the evaluation strategy. (Indeed, any of the above strategies may produce more than one winner, so we also need a tie-breaking mechanism in the end.)

### Exercises

1. A vote consists of the names of the three candidates that one person has voted for. Provide data definitions and examples of data for individual votes and a list of individual votes.

For all problems in this assignment, assume that the three names in one vote are all different (ie, no person lists the same candidate as more than one choice).

2. Write the template over a list of votes.

3. Write a function `top-votes-for` which consumes a name and a list of votes and produces the number of times that the given name was the first choice vote in the list of votes. (This tallies points under winner-takes-all voting.)

4. Write a function `top-two-votes-for` which consumes a name and a list of votes and produces the number of times that the given name was either the first or second choice in the list of votes. (This tallies points under approval-rating voting.)

5. Write a function `total-points-for` which consumes a name and a list of votes and produces the number of points that the given name has received using a points-per-place strategy.

6. A voting-tally consists of the name of a candidate and the number of points or votes that they received in an election. Write data definitions and examples for voting-tallies and a list of voting-tally (no template required).

7. Write a program `eliminate-no-votes` that consumes a list of voting-tally and produces a list of those tallies in which the candidate received at least one vote.

8. Write a program `tally-by-approval` that consumes a list of candidate names and a list of votes and produces a list of voting-tallies. The produced list should have one tally for each candidate. The number of votes in the tally for a candidate should be the number of votes that candidate received under the winner-takes-all strategy. [Hint 1: Use `top-votes-for` as a helper.]

The challenge in this problem is that you have two lists as inputs. One acts as the main list that determines the shape of the output -- use the template for that kind of list for this problem. The other list is only used as input to a helper function.

9. Write a program `tally-by-place-points` that consumes a list of candidate names and a list of individual votes and produces a list of voting tallies according to the points-per-place strategy.

10. The functions you have written so far provide a foundation for a social scientist who wants to study election strategies.

1. Write an example list of votes (over at least 5 candidates) that produces different winners under tally-by-approval and tally-by-place-points.

2. Provide the expressions that you would write to produce the voting-tallies under each election strategy.

3. Provide contracts and purposes for two more functions that it would be helpful to have (other than one that tallies by winner-takes-all) if you wanted to use your work so far to study the impact of voting strategy on election outcome. Your functions should perform different kinds if tasks, rather than just be two variations on the same theme. Don't write the functions, just provide the contracts and purposes.

## What to Turn In

Turn in a single file hwk4.ss or hwk4.scm containing all code and documentation for this assignment. Make sure that both students' names are in a comment at the top of the file.

Back to the Assignments page