Skip to main content

Homework 5: Binary Trees & Polling

Due: 2024-11-03 23:59:00EDT

Overview

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.

1. Implement a Binary Tree

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

The HW5 LinkedBinaryTree interface is an extension of the LabBinaryTree interface you implemented in Lab7. You can copy over the size, contains, isEmpty, and insert methods from your lab.

Requirements

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

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

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

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

  5. Implement a boolean contains(E element) operation, which returns true if the given element exists in the tree and false otherwise.

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

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

2. Storing Polling Data

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.

Requirements

  1. Create a class to store the polling data: PollingData.java

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

  3. Override the 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.

  4. Your PollingData class should have the following constructor: public PollingData(String lastName, String fullName, double percent)

3. Polling Data from CSVs

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.

Requirements:

  1. Take filename input from the command line into the main method of your DriverHW05.java. You may be given multiple filenames. An example of given arguments might be: 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

  1. You should process the given files in increasing date order. You may assume that the files are given in this order.

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

  3. Do not use any try-catches. The signature of your main function should be: public static void main(String[] args) throws FileNotFoundException

4. Extra credit (5 points)

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.

  1. Make sure that the polls are processed in date order no matter what order they are given to you in on the command line.

Sample Input and Output:

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

Submitting

Submit the following files to the assignment on Gradescope

  1. README: The usual plain text file README
    • Your name
    • Discussion: Design of remove as explained above, and any extra credit implementations you chose to do.
    • How much time you spent on the assignment
    • What did you learn?
    • (Optional): Any feedback or comments
  2. Source files:
    • LinkedBinaryTree.java
    • PollingData.java
    • DriverHW05.java
    • Any other java files you created

You do not need to submit any files from you Lab7.

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.

Copying the files

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.