Lab Coordinates

For all remaining CS 2 labs (including this one), you will have one lab session to complete the lab. You will have the option to work solo or in a pair:

If you choose to work in a pair, you must attend your lab in person. If you work alone, you are welcome to skip the actual lab session and work anywhere. We recommend you read this page about pair programming if you choose this option. You are allowed to work on the lab with your partner after your lab section if you do not finish.
If you choose to work solo, you may either attend or skip your in-person lab section.

Setup

As always, register for the lab using the registration tool: https://register.caltech.codes. Then, follow the same instructions as last time to clone the repository and use IntelliJ.

Goals and Outcomes

By the end of this lab, you will…

have more experience working with Maps, Lists, and Sets in Java
understand how to implement common data manipulations

An Interesting Data Structures Problem

The Problem

Pasadena has more restaurants per capita than New York City. With so many choices, it’s hard to get a large group of friends to agree on which one to eat at for dinner.

Approval Voting

To decide where to go, every friends will vote on restaurants they approve of (i.e., “are okay going to”). Each person can approve of an unlimited number of choices. The restaurant with the highest number of approvals wins and is selected; ties are broken by alphabetical order.

Example

Inputs

The three friends choosing where to eat are Aiden, Bailey, and Classic.
The four available restaurants to vote for are Nine & Nine, BCD Tofu House, Main Chick, Zankou Chicken.
Their approval votes are as follows:
- Aiden approves of \(\{\text{BCD Tofu House}, \text{Nine & Nine}\}\)
- Bailey approves of \(\{\text{Nine & Nine}, \text{Zankou Chicken}\}\)
- Classic approves of \(\{\text{BCD Tofu House}, \text{Main Chick}, \text{Nine & Nine}\}\)

Output

The winner is Nine & Nine (with 3 votes) since every other option has two or fewer votes.

Data Structures to the Rescue!

As we’ve discussed in class, a large part of solving algorithmic problems is choosing the right data structure. In this lab, you’ll implement one version with Lists (the “wrong” data structure), and another version with Maps (the “right” data structure). Both versions will use a two-part algorithm: (1) record the votes for each restaurant in a temporary data structure, and (2) use the temporary data structure to solve the actual problem.

Attempt 1: “bag of restaurants”

This attempt will look very similar to our IntBag from the first lecture. We will make a List by adding each restaurant one time per approval vote. Then, to process the list, we will count the number of occurrences of each restaurant to find the winner. Each of the two steps of the algorithm will be its own function:

public static List<String> processVotes(List<Set<String>> input)

Constructs and returns a List of restaurants where each one appears the number of times it occurred in the input.

public static String findMostVoted(List<String> processed)

Finds the winner for the processed set of votes.

To do this, you should:

Construct a list of restaurants
For each restaurant:
- Count how many votes it got
- Update the winner so far if necessary

Task 1. Implement processVotes and findMostVoted in the src/edu/caltech/cs2/datastructures/ApprovalVoteList.java file.

Attempt 2: “tally map”

This attempt will use a “tally map” which uses resturants as keys and vote counts as values. Each of the two steps of the algorithm will, again, be their own functions:

public static Map<String, Integer> processVotes(List<Set<String>> input)

Constructs and returns a Map from restaurants to counts representing where the number of times that restaurant occurred in the input.

public static String findMostVoted(Map<String, Integer> processed)

Finds the winner for the processed set of votes.

Hint: You will likely want to use the keySet method discussed in lecture.

Task 2. Implement processVotes and findMostVoted in the src/edu/caltech/cs2/datastructures/ApprovalVoteMap.java file.

Submitting Your Code for Credit

Your code will be autograded when you submit it to gitlab. You may submit to gitlab as many times as you like, and only the last submission will be counted.

Committing and Pushing to the Repository

A “commit” is version control language for a chunk of changes that mean something when grouped together. Importantly, commits will only stay locally on your machine until you push them to the gitlab server.

Task 3. To commit to the repository, click the green checkmark on the top-right of IntelliJ’s interface. A window will pop up and ask you to type in a message. Choose some meaningful description of your feature, then click the little down arrow next to the “Commit” button on the bottom right of the dialog.
Choose “Commit and Push” in the little menu that pops up. If IntelliJ asks you if you’re sure you want to commit and push, say yes.

Checking the Results on `gitlab`

When you go to https://gitlab.caltech.edu, you should see your lab02 repository listed. Click on it. All the way on the right, there should be a red “X”, an orange “pause” symbol, a blue “time” symbol, or a green “check” symbol. This symbol indicates the status of the automated tests which will check the correctness of your code. Click on it. On the new page, you should see a table, and under “status”, there should be another symbol. Click on it. The new page will list the “categories” of tests for this repository. These will be some combination of “A”, “B”, “C”, and “D”. These letters indicate what grade you earned on the assessment for passing those tests. If you click on one of them, it will detail for you which sub-tests you passed and failed which might help you debug.

It is good practice to always check gitlab after submitting a project or lab in this course.

Task 4. Check to make sure you are passing all the tests on gitlab.