CS 1101 (A05) Homework 4: Lists of Structures

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

Assignment Goals

To make sure you can

The Assignment

Remember to follow the Expectations on Homework when preparing your solutions, including the academic honesty policy.

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:

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.)


  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