Figure 1: Example of input and output of the driver program.
University of Toronto
CSC148H: Introduction to Computer Science
Summer 1997
Assignment 1: Election Night
Due: Thursday, May 29, 6pm.
It's federal election time again, and your local TV station wants to have the most up-to-date results on election night so that they can predict the winner before anyone else does. So, you've been asked to write a program that will maintain the election results for every riding in the country. It should be able to determine who is currently winning in each riding and which party is winning overall.
This assignment is intended as a warm-up to the course, particularly for those who haven't taken CSC108 and may therefore be unfamiliar with the Turing language or the computing facilities. You will need to know basic programming skills such as variable declaration, structured data types, looping, functions, arrays, and sorting. Additionally, the assignment introduces the concept of a class, which is a central idea throughout the course. The algorithms should be straightforward for you, so if you find this assignment very difficult, then you may need to acquire more programming experience before taking CSC148.
An abstract data type (ADT) consists of a data structure and a set of operations that work on the data structure.
First of all, you will need a data structure, or several data structures, that contain all the information about the election results. The country is divided into a number of ridings. Each riding has a number of candidates. Each candidate is affiliated with a political party. Each candidate also receives a number of votes. It is up to you to design the structure. [Hint: consider having an array of ridings, each of which has an array of candidates; or, consider a two-dimensional array of candidates. Draw pictures of your structure before you think about how to write the code.]
Some details: a riding is identified by a positive integer in the range of 1 to the total number of ridings. A candidate is identified by his/her name, which is a string. A political party is also identified by its name, a string.
The TV station requires the following operations:
- Init (total_ridings : int)
- Initialize the data structures, given the total number of ridings in Canada.
- RegisterCandidate (riding_n : int, name : string, party : string)
- Add a new candidate, in the given party, to the riding.
- AddResults (riding_n : int, name : string, votes : int)
- Given the name of a candidate in the given riding, add the number of votes to his/her total vote count. This function could be called multiple times for the same candidate.
- RidingReport (riding_n : int)
- Produce a report for the given riding. Computes the percentage of votes that each candidate received in the riding, and outputs the candidates in order of most votes to least votes. It must call PrintCandLine to ensure that the output conforms to the standard.
- PartyReport (party : string)
- Produce a one-line report about the given party. It should output the number of ridings won, and the party's popular vote (that is, the percentage of voters in Canada who voted for any candidate in the party). It must call PrintPartyLine to meet the output standards.
When you implement an abstract data type (i.e., write the code that defines the data structures and the operations), it makes sense to group everything together in one place. That way, it's easy for you to understand, debug, and change it. If you take this one step further, then you would isolate the ADT so that the details of its implementation are hidden from the user. The user of the ADT would only be told what it needs to know to use the type, and nothing else.
In Turing, a class is used to define an ADT. It is like a pattern or template for creating instances of the ADT, which are called objects. The creation of objects actually happens while a program is running, and is analagous to creating a variable of a certain type: the class corresponds to the type, and the object to the new variable. Look at the driver program, discussed below, to see how this is done.
We have provided a skeleton of the class ElectionResults which implements the ADT described above. The class is stored in a separate file (election.tu) called a unit. Any program that wants to use the class, such as the driver program, just has to import the file using the statement import ElectionResults in "election.tu".
The driver program, also in a separate file (a1driver.t), is used to test the class. It imports the ElectionResults class, creates and initializes one ElectionResults object, and accesses the object's subprograms at your command. To run the whole thing, make sure that you have both files stored in your own directory, and simply run the driver program. Of course, it won't do much until you complete the class.
Before you begin work on the class, you should read over the two programs and make sure you understand how the driver uses the class.
You are required to you finish the ElectionResults class by filling in the data structure and the subprograms that operate on it. The design of the data structure and subprograms is up to you. Do not change any of the code supplied; just add your own. You may write additional `helper' subprograms. All output that the class produces should be made by calling PrintCandLine or PrintPartyLine, as appropriate.
The driver program is provided for testing purposes. It takes input in three stages. In the first stage, the total number of ridings is input, followed by the candidates in each riding, specified by riding number, candidate name, and party name. In the second stage, voting results are recorded by giving a riding number, candidate name, and the number of votes received. In the final stage, reports are produced by entering a riding number or a party name. The stages are separated by the token -1. Figure 1 shows an example of input to the driver, and the output that it should produce. Take note: you should test your program thoroughly on other input to make sure that it works in all possible cases. You can assume that all the input will be in the correct format, without errors. You may write your own driver if you like.
Figure 1: Example of input and output of the driver program.
IMPORTANT: Your class will be graded automatically by a computer program, which will run it on a series of test cases, using our own driver. We will not tell you what these tests are beforehand. The automatic tester will match your program's output with the correct output on a character by character basis. If your output is different in any way, then it will be considered wrong. This is why it is very important to use the output functions supplied in the ElectionResults class, and to not change them in any way.
You will submit your assignment electronically. Do not submit a report or a hardcopy version. All we need is your ElectionResults class. Make sure that it's named election.tu and submit it using the ``Hand in (submit)'' command, found under the ``File Utilities'' icon on the CDF-PCs. If you submit more that once, then the most recent submission will replace any previous ones. If your file is not named election.tu, the automatic tester won't find it, and will assign a mark of zero.