Due: 2024-03-17 23:59:00EDT
For this assignment and the next one you will be working within the same codebase to look at polling data for the 2020 U.S. presidential election. Before the two main political parties put forward their nominees for president, the Democratic and Republican parties hold primary elections to determine who their nominee will be. The Republican nominee was essentially predetermined to be the incumbent, President Trump. The Democratic party’s nomination was still very uncertain (at the time). In order to make repeated predictions about the likely outcome of the Democratic party nomination, pollsters (statisticians) regularly conduct polls (surveys) to sample Democratic primary voters and ask who they plan to vote for. These results are compiled, released, and eagerly tracked by the news media and public to determine which candidate currently has the largest percentage of support.
In this assignment, your job will be to take the poll results given as input via CSV files and update the entries of a binary tree so that it stores the name and current polling percentage for each candidate. In the next assignment you will modify this tree so that you can easily retrieve the name of the candidate currently leading in the polls.
Start by implementing the given BinaryTree
interface
as a LinkedBinaryTree
so that generic objects that implement
the compareTo
method from the Comparable
interface can be inserted into
your tree.
wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/hws/hw05/BinaryTree.java
Implement the BinaryTree
interface as a LinkedBinaryTree
. Make sure
the implementation is entirely recursive and is a linked data structure, i.e.,
you should NOT use any for
or while
loops, arrays, ArrayLists
, etc.
Your LinkedBinaryTree
should contain two constructors. One which takes no arguments and one which takes a generic data type to initialize the root node.
Hint: you may find it useful to use private helper methods that are called from the
publicly defined method in the interface.
Your implementation should be properly encapsulated, i.e. no implementa-
tion details should be made visible outside of the LinkedBinaryTree
class - it should only implement the BinaryTree
interface.
Hint: consider making
a private inner class to define a Node
of the tree.
Insertion should be done using the compareTo
method of the given element
so that smaller elements are put into the left subtree and larger element are
put into the right subtree. (This is a Binary Search Tree!). Insertion of elements that are already in the tree
should replace the current element. When you put your polling data into the
tree this will be equivalent to updating the poll numbers for a candidate.
As part of implementing the BinaryTree interface you will implement all
three orders for tree traversal: pre-
, in-
, and post-order
.
Each traversal will return a string in the form:
element1 element2 ... elementn
where the order is determined by the correct order of the traversal. Note
that these methods should also use a recursive design.
Implement a boolean contains(E element)
operation, which returns true
if the given element exists in the tree and false
otherwise.
Implement a boolean remove(E element)
operation, which returns true
if
the given element exisits and is removed, and false
otherwise. You should
be sure that this method works seamlessly with the other methods. For
example, in-order traversal should return a string containing the elements in
sorted order even after an element has been removed. Describe your chosen
design for this method in the README
.
You should override the toString
method to return a String
that looks like
the following:
Tree:
Pre: b a c
In: a b c
Post: a c b
Where the first traversal is a pre-order traversal, the second is in-order, and
the last is post-order. This assumes b
is the root, a
is the left child of b
,
and c
is the right child of b
.
The polling data you are given will include the candidate’s full name, their last name, and the percentage of the people polled who said they would vote for that candidate.
Create a class to store the polling data: PollingData.java
Have your created class implement the Comparable
interface so that polling
data objects are put in alphabetical order based on the candidate’s last name.
toString
method to return a String
with the following for-
matting:
Full Name:5.0
where Full Name
is the candidate’s full name and 5.0
was the candidate’s
polling percentage.
PollingData
class should have the following constructor: public PollingData(String lastName, String fullName, double percent)
The website FiveThirtyEight makes polling data for presidential primary candi- dates available (https://data.fivethirtyeight.com/). We have preprocessed this data for you so that only the relevant data is included and you will receive one file per conducted poll.
You can download the polling data here: https://github.com/BMC-CS-151/BMC-CS-151.github.io/blob/main/hws/hw05/poll_data.zip
Each polling data CSV has the following format:
answer,candidate_name,pct
Biden,Joseph R. Biden Jr.,25
Sanders,Bernard Sanders,16
The first column gives the last name of the candidate, the second column gives the candidate’s full name, and the final column is the percent the candidate is polling at in this poll. Note that the given percent can be a floating-point number.
Each file is named something like dempres_20190310_1.csv
where dempres
indicates that these are polling results for the Democratic party presidential primary,
20190310
indicates that the polling results were completed on March 10,
2019, and _1
indicates that these are the results for the first poll completed on
that date (there may be multiple from different sources).
Your job is to create a DriverHW05.java
that takes the polling data in each file and inserts it into the binary
tree. Your resulting tree should contain the polling data for each candidate from
the most recent date for which there is data from the files given on the command
line. Each polling result will only include some of the candidates.
dempres_20190210_1.csv dempres_20190210_2.csv dempres_20190310_1.csv
or:
dempres_20190210*.csv
.
Recall that unix shell will expand the *
for you.As in HW02, you must be able to handle relative paths. That is, if the csv files are not in the current directory. Ex: DriverHW05 ../../polls/dempres_20190210_1.csv
You should process the given files in increasing date order. You may assume that the files are given in this order.
Use your overridden toString
method to print the tree after polling results
from each new date are inserted. Thus, your resulting printed information
should include one snapshot of the tree per given polling data CSV.
Do not use any try-catches. The signature of your main
function should be: public static void main(String[] args) throws FileNotFoundException
All extra credit should only be done after successful completion of all of the base requirements for this assignment. If you implement the extra credit, you must add that to your README so that our grading will know to test for them and grant credit accordingly.
For an input file containing:
answer,candidate_name,pct
Biden,Joseph R. Biden Jr.,25
Sanders,Bernard Sanders,16
Harris,Kamala D. Harris,8
Warren,Elizabeth Warren,8
O'Rourke,Beto O'Rourke,7
Booker,Cory A. Booker,5
The output should be:
Tree:
Pre: Joseph R. Biden Jr.:25.0 Bernard Sanders:16.0 Kamala D. Harris:8.0 Cory A. Booker:5.0 Beto O'Rourke:7.0 Elizabeth Warren:8.0
In: Joseph R. Biden Jr.:25.0 Cory A. Booker:5.0 Kamala D. Harris:8.0 Beto O'Rourke:7.0 Bernard Sanders:16.0 Elizabeth Warren:8.0
Post: Cory A. Booker:5.0 Beto O'Rourke:7.0 Kamala D. Harris:8.0 Elizabeth Warren:8.0 Bernard Sanders:16.0 Joseph R. Biden Jr.:25.0
Submit the following files to the assignment on Gradescope
LinkedBinaryTree.java
PollingData.java
DriverHW05.java
Make sure to name these files exactly what we specify here. Otherwise,
our autograders might not work and we might have to take points off.
DO NOT submit a .docx or .pdf file.
DO NOT submit any .class
files or any of the csv
files.
DO NOT submit any of the provided interfaces. We will use the ones
we provide for testing.
You will likely want to submit the files from your own laptop/computer.
To copy the files from goldengate
to your own machine,
open up a terminal on your own computer. If you have a mac or linux, you can use the
Terminal application, if you have a windows you can use the Powershell app.
Run the following command:
$ scp <username>@goldengate.cs.brynmawr.edu/home/<username>/cs151/homeworks/hw00/*
Make sure to replace <username>
with your username. scp
is a command to secure-copy files
from one server to another. In this case, from goldengate
to your own machine.