CS 3110 Fall 2020 Prelim October 3–5, 2020
Instructions. Read the separate instructions document provided in CMS be- fore you begin. Note carefully the instructions regarding a required work-in- progress submission about two hours after you begin.
1 Everyone’s a Critic [20 pts]
At this URL you will find a video of a programmer developing some code for a hypothetical CS 3110 assignment:
https://cornell.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id= 28cc0f5b-2168-4ecd-b29c-ac4201642890
Watch the video. Please forgive the programmer; he’s new at OCaml and hav- ing trouble adjusting.
Imagine you wanted to help the programmer to improve. Criticizing his newbie knowledge of the language itself won’t be helpful. Instead, write a document that analyzes his development methodology, his final code, and his final test suite. Structure your document as a set of five independent critiques. (With all respect to the programmer—it should not be difficult for you to find that many.) Your critiques should be based on the programming principles that have been taught in this course, especially in the assignments, the textbook, and The Pragmatic Programmer.
Organization. A Word template has been provided in CMS; please use it if you can. Regardless, use appropriate formatting to make it easy for the grader to read your critique. Limit yourself to at most four pages, selecting only the most important critiques if necessary. I’m not going to specify any font sizes, margins, etc. Organize each of your critiques as follows:
• A heading of the form “Critique Number N.”
• A one line summary of the critique.
• A paragraph describing what the programmer is doing wrong. Include citations to particular timecodes (e.g., 3:09) in the video, so that it’s clear exactly what you are critiquing.
© 2020 Cornell University 1
• Aparagraphexplainingwhyyourcritiqueisimportant.Identifyadeeper reason about programming, not just (e.g.) “the textbook says so.”
• Aparagraphadvisingtheprogrammeronhowtoimprove.Makespecific suggestions about what to change in the methodology, code, or test suite.
Submission. Submit your critique as a Word or PDF file in CMS. Double check before the deadline that you have submitted the intended version of your file.
2 Get Out the Vote [40 pts]
Write an OCaml program that computes the results of elections. The kind of elections you should have in mind are small organizational elections, which tend to have few candidates, not too many voters, and might often result in ties. Your program must support two tallying algorithms: plurality and Borda count.
Plurality. Plurality voting is the voting system with which most people are likely to be familiar. Each voter selects exactly one candidate as their prefer- ence and puts that candidate’s name on the ballot. The tally of the election is a map from the candidates to the number of votes each candidate received. The winner is the candidate who received the highest number of votes, regard- less of whether that number is above any particular threshold. For example, a candidate could receive only 25% of the votes and still win, if all the other candidates received less than 25% of the votes. If there is a tie for the highest number of votes, then there is no winner.
Borda. The Borda count voting system, named after Jean-Charles de Borda (1733–1799), is useful for organizational decision making when building con- sensus is deemed important. Each voter ranks all of the candidates in a total order from most preferred to least preferred. For example, if Alice, Bob, and Charlie are the candidates, and if a voter prefers Alice the most, then Bob in the middle, and least prefers Charlie, then the voter submits this ballot:
1. Alice 2. Bob
3. Charlie
Ballots cast with the Borda count system thus contain more information about voters’ preferences than ballots cast with the plurality voting system. (That can be useful to avoid third-party spoiler effects.)
Based on the ballot, a number of points are awarded to each candidate. If there are n candidates in the election, then the candidate ranked first on the
© 2020 Cornell University 2
ballot receives n points, the candidate ranked second receives n − 1 points, etc., and the candidate ranked last receives 1 point. So the example ballot above would cause 3 points to be awarded to Alice, 2 points to Bob, and 1 point to Charlie.
The tally is the total number of points each candidate receives. The winner is the candidate who receives the highest number of points. If there is a tie for the highest number of points, then there is no winner.
Requirements. Create a program that computes:
• The tally of an election using the plurality voting system.
• The winner of an election using the plurality voting system.
• The tally of an election using the Borda count voting system.
• The winner of an election using the Borda count voting system.
You should therefore provide at least four functions, one for each of the above requirements. Each function should take a collection of ballots as input and produce the required output. Note that you are not being asked to create a sys- tem that runs entire elections (which would include voter rolls, authentication, handling spoiled ballots, etc.).
This problem is deliberately open-ended. I am asking you to demonstrate your skills as a programmer. The omission of required function names and types is deliberate. Use what you have learned to design those yourself. Of course, no make check system is provided, because I cannot predict in advance what you will design.
These requirements are all that will be stated. Given that people will be completing the exam at different times, I cannot fairly make announcements that refine the requirements as the exam is ongoing. So, I expect you to re- solve any remaining ambiguities in a reasonable and pragmatic way, keeping in mind the goal of delighting your client (me). Since I cannot consult with each of the 350 or so of you individually, I ask that you instead document and defend any decisions you make in comments in your source code, rather than post questions on Campuswire or email me.
Your task. Program the necessary types and functions to satisfy the above requirements, and a unit test suite. Use the release code provided in CMS as a skeleton for your solution. Provide specification comments for all your functions. Write code at the same quality as that required by the rubric in assignment A1.
For your test suite, provide unit tests that demonstrate the correct operation of your implementation. The graders will use your tests as a basis for adding new tests of their own to see whether your algorithms compute the correct results. Determining the winner logically requires the tally to be correct. So, if your program produces an incorrect tally for a collection of ballots, there will
© 2020 Cornell University 3
be no credit awarded to your solution for the winner—regardless of whether your program happens to get the right answer or not.
To help the graders understand how to construct tests, you must provide at least the following six clearly marked unit tests:
1. A test for the tally of a plurality election in which there are three can- didates named David, Anne, and Michael, who each receive a different number of votes.
2. A test for the winner of a plurality election in which there is a candidate named David who wins.
3. A test for the winner of a plurality election in which there is no winner.
4. A test for the tally of a Borda count election in which there are three can- didates named David, Anne, and Michael, who each receive a different number of points.
5. A test for the winner of a Borda count election in which there is a candi- date named David who wins.
6. A test for the winner of a Borda count election in which there is no win- ner.
Hints. The two voting systems use different styles of ballots, so in some sense these are independent functionalities. Nonetheless, a good programmer will find ways to eliminate redundancy. You get to choose the ballot representation. A good programmer will choose a representation that makes their life simple. A good programmer will also make use of standard library modules. You may use the OCaml standard library. The usual prohibitions of imperative features and deprecated functions do hold.
Submission. Run make zip to create voting.zip. Submit voting.zip in CMS. Double check before the deadline that you have submitted the intended ver- sion of your file.
Points. These are not hard functions. After all, I expect you can write them in less than two hours. My own solution requires fewer than 40 lines of non- testing code. So, I want you to concentrate on writing high-quality code, and on testing. Demonstrate what you have learned.
• Correctness: 20 pts • Testing 10 pts
• Code quality: 10 pts
© 2020 Cornell University 4