Skip to Main Content

Data Structures

Computer Science Department

RU Kindergarten – 90 course points

The purpose of this assignment is to practice your understanding of linked list structures.

This assignment will take longer to complete than the labs.

Start your assignment early! You will need time to understand this assignment and the many questions it may present.

Refer to our Programming Assignments FAQ for instructions on how to install VSCode, how to use the command line and how to submit your assignments.

NOTE: You will also need to submit a reflection for this assignment here once you’re finished coding. It’s accessible through your scarletmail: https://forms.gle/NAZwPFbUhXTmAPGj6

 

Overview

In this assignment you will simulate activities in a kindergarten classroom.

You will simulate the students standing in a line, the students on their seats, and students playing musical chairs.

The assignment uses:

  • a Singly Linked List to simulate student standing in a line.
  • a 2D array to simulate students at their seats.
  • a Circular Linked List to simulate students sitting on chairs to play the musical chairs game.
A Singly Linked List simulates student standing on a line
A 2D array simulates students at their seats
A Circular Linked List simulates students sitting on chairs to play the musical chairs game

Implementation

Overview of files provided

  • The Student class holds a student’s information.
  • The SNode class represents the node object to be used in the linked structures. It contains a reference to a Student object and a reference to the next node in the list.
  • The Classroom class holds all of the methods to be written and that will be tested when running the game. Edit the empty methods with your solution, but DO NOT edit the provided ones or the method signatures of any method. This is the file you submit. 
  • The Driver class, which is used to test your methods interactively. The classroom state will be printed after every method is used. Feel free to edit this file, as it is provided only to help you test your code. It is not submitted and it is not used to grade your code.
  • The StdRandom class contains the StdRandom.uniform(n) method that you will use in the method that plays the musical chairs game.
  • The StdIn and StdOut classes, which are used by the driver. Do not edit these classes..
  • Multiple text files. Feel free to edit them or even make new ones to help test your code. They are not submitted. They consist of:
    • Files containing student information.
    • Files containing seat locations in the classroom.

Classroom.java

  • DO NOT add new import statements.
  • DO NOT change any of the method’s signatures.
  • You are encouraged to write helper methods as you see fit. Just make sure that they are private.

The class contains:

  • studentsInLine which is an SNode reference to the first student in line. 
  • musicalChairs which refers to the LAST student in the circularly linked list when musical chairs is being played.
  • openSeats, which is a 2D boolean array that shows which seats exist for students to sit at. (Imagine that if a position is false, a seat doesn’t exist at that position.)
  • studentsInSeats which is a 2D Student array that contains the students when they are sitting.
  • NOTE: openSeats and studentsInSeats are parallel arrays meaning that openSeats[i][j] also refers to the same seat in studentsInSeats[i][j]
  • provided methods that are used by the driver and empty methods you are expected to write your code in.
  • the printClassroom() function can be used to show the state of the classroom (eg. the states of students in line, seats, and musical chairs) at any time in your code.

Methods to be implemented by you:

1. enterClassroom

This method simulates students standing in line and coming into the classroom (not leaving the line).

To complete this method do the following:

  1. Read a student from the input file (see below).
  2. Create a Student object with the information read from the file.
  3. Create a SNode object that holds the Student object from step 2.
  4. Insert the SNode from step 3 to the front of the singularly linked list studentsInLine. 

You have been provided some input files to test this method (students1.in, students2.in, students3.in, students4.in). The format is as follows:

  • One line containing an integer representing the number of students in the file (one per line)
  • Several lines (one per student) containing students’ first name, last name, and height, space separated

Use the StdIn library to read from a file:

  • StdIn.setFile(filename) opens a file to be read
  • StdIn.readInt() reads the next integer value from the opened file (whether the value is on the current line or on the next line)
  • StdIn.readString() reads the next String value from the opened file

To read one student do the following :
String firstName = StdIn.readString();
String lastName = StdIn.readString();
int height = StdIn.readInt();

The input file has Students in reverse alphabetical order; so at the end of this method the list will have all students in alphabetical order. DO NOT implement a sorting algorithm, there is no need — simply add each student to the front of the list. 

  • Submit Classroom.java with this method completed under Early Submission to receive extra credit.

This is the expected output for students1.in:

2. createSeats

This method creates the classroom seats. Imagine that someone is putting down seats in a rectangular or square room.

  • We will use a 2D array to simulate a room where each cell of the array can have a seat or not.
  • The instance variable openSeats is the 2D boolean array that shows which seats exist for students to sit at. Once the array is read, it will not change.
  • The instance variable studentsInSeats is the 2D array that contains the students when they are sitting in seats.

To complete this method do:

  1. Read the input file to create the seating arrangement for the 2D boolean array openSeats 
  2. Initialize the 2D Student array studentsInSeats to be of the same size.

The input file format is as follows:

  • The first line contains an integer representing the number of rows in the classroom, say r
  • The second line contains an integer representing the number of columns in the classroom, say c
  • r lines, each containing c true or false values (true denotes a seat exists, false denotes that there is no seat at that position in the classroom).

Use the StdIn library to read from a file:

  • StdIn.setFile(filename) opens a file to be read
  • StdIn.readInt() reads the next integer value from the opened file (weather the value is in the current line or in the next line)
  • StdIn.readBoolean() read the next boolean value from the opened file (weather the value is in the current line or in the next line)
This method DOES NOT seat students in the seats.

This is the expected output for students1.in and seating1.in — run enterClassroom in the driver BEFORE testing this method. 

3. seatStudents

This method simulates students taking their seats in the Kindergarten classroom. Assume that the students are currently in studentsInLine and that there are enough available seats to seat all students in the line.
  • This method will populate the 2D array studentsInSeats.
  • Students will be seated starting at the first row, first seat (studentsInSeats[0][0] if a seat is present at that location). Once the first row is filled, continue into the next row.
  • It uses the openSeats array to determine if a seat exists at a location.
    • A student can sit at seat studentsInSeats[i][j] only if openSeats[i][j] is true (seat exists). 
  • Then seat the first student in studentsInLine and move on to the second, third and so on.

NOTES

  • A student is only in one place (musical chairs, seats, or in line) at a time. At the end of this method studentsInLine is empty.
  • This method depends on enterClassroom and createSeats. Run those individually with the driver prior to testing this method.
  • ONLY seat a student in a specific position if a student is NOT already in that position. This will be important for later methods. 
  • DO NOT change the openSeats array if a student sits; openSeats denotes seat positions and should be left unchanged. 
This is the expected output for students1.in and seating1.in after running enterClassroom, createSeats, and seatStudents in order. 

4. insertMusicalChairs

This method represents students preparing to start musical chairs! Assume that the students are in studentsInSeats.

  • Imagine this as a circle of chairs.
  • This method will take students from the studentsInSeats array and add them to the musicalChairs circular linked list.
  • Students are to be inserted at the end of the linked list by traversing row-wise, then column-wise in the studentsInSeats array.
  • REMEMBER: the pointer to a circular linked list points to the LAST item in the list, and that item points to the front. musicalChairs refers to the last student in the list. 

NOTES

  • At the end of this method studentsInLine and studentsInSeats have no students.
  • This method depends on the previous methods from parts 1, 2, and 3. Test those before testing insertMusicalChairs.

This is the expected output using students1.in and seating1.in, after running enterClassroom, createSeats, seatStudents and insertMusicalChairs in order in the driver:

playMusicalChairs

This method simulates the game of musical chairs!

  • This method is implemented for you.
  • Write the following methods to make it work.

This is the expected output using students1.in and seating1.in, after running enterClassroom, createSeats, seatStudents and insertMusicalChairs in order in the driver AND after implementing the methods described below.

UPDATE: On 2/15, we updated the random seeds in the driver to be 2025, instead of 2022. If you see J. Keer as a winner, replace 2022 in Driver lines 77, 138, 148, and 165 with 2025. 

5. moveStudentFromChairsToLine

This method simulates a student being eliminated during the musical chairs game. 

  • This method randomly chooses a student to be eliminated from musicalChairs. 
  • Use StdRandom.uniform(x), where x is the number of students currently in musicalChairs, to get a number n between 0 (inclusive) and x (exclusive).
  • Remove the student at position n from musicalChairs. Position 0 is the first student.
    • Notice that the driver is setting a seed for the random number generator. The seed value is 2025.
    • Running this method 15 times will result in a different result than if you were to run eliminateLosingStudents, due to how the driver sets a seed (it sets a seed each time before the method is executed). Autolab replicates the same behavior as the driver.
  • Once the student is removed from the chairs call insertByName to insert the student into studentsInLine.

Note: this method depends on insertMusicalChairs and insertByName. This is the expected output using students1.in and seating1.in, after running enterClassroom, createSeats, seatStudents, insertMusicalChairs and this method in order in the driver:

HINT:

– When removing the front of a CLL, the last node’s next will be the front’s next node.
– When removing the last node of a CLL, the previous node’s next will be the old last’s next, and the previous node will be the new last node.
– When removing from the middle, the previous node’s next will be the old node’s next.

6. insertByName

Each student that is eliminated from the musical chairs game is put back in the line (studentsInLine linked list) in alphabetical order.

  • The eliminated student is given as a parameter
  • Iterate through studentsInLine searching for a student that is later in the alphabet than the eliminated student. You will have 3 cases:
    • eliminated student is the earliest in the alphabet, insert at the front of the list.
    • eliminated student is the latest in the alphabet, insert at the end of the list.
    • eliminated student is not the earliest or latest, insert after the earlier student in the middle of the list.
    • student.compareNameTo(otherStudent) will compare a Student by last name, then first if last names are the same. > 0 indicates the student is greater than the other, < 0 less than, and == 0 equal. This is similar to compareTo. 
    • If the list is empty, update studentsInLine accordingly.
  • When inserting into the list, a student will be inserted AFTER all students who have the same name.
  • This method is called from moveStudentFromChairsToLine() to insert a student that was eliminated from the musical chairs game. In the driver, you can test this method independently using moveStudentFromChairsToLine.

7. eliminateLosingStudents

This method eliminates all students from musicalChairs except the winner.

  1. Obtain the number of students currently in the musicalChairs, call it size.
  2. Repeatedly call moveStudentFromChairsToLine with the size until one player is left.
  3. Don’t forget to update size after each call as the number of students in the chairs decreases by 1.

At the end of this method one student will remain in musicalChairs, this is the winner! The winner doesn’t leave the musical chairs to enter the line.

All other students will be standing on the line in ascending order by name.

NOTE: this method depends on all previous methods.

This is the expected output using students1.in and seating1.in, after running enterClassroom, createSeats, seatStudents, insertMusicalChairs and this method in order in the driver:

UPDATE: On 2/15, we updated the random seeds in the driver to be 2025, instead of 2022. If you see J Keer as the winner, replace 2022 in Driver lines 77, 138, 148, and 165 with 2025. Please disregard any mentions of inserting by height — you’ll only use names to insert. 

8. seatMusicalChairsWinner

This method will seat the winner of the musical chairs game!

After the game in musical chairs, you must seat the winner first!

  • If musicalChairs contains only one node (that is, the winner), delete the node. The list will be empty.
  • Insert the student object into the first empty spot in the classroom (studentsInSeats). Make sure that seatStudents only seats a student if no other students exists at a given position. 
This is the expected output using students1.in and seating1.in, after running enterClassroom, createSeats, seatStudents, insertMusicalChairs, eliminateLosingStudents, and this method in order in the driver:
 
UPDATE: On 2/15, we updated the random seeds in the driver to be 2025, instead of 2022. If you see J Keer as the winner, replace 2022 in Driver lines 77, 138, 148, and 165 with 2025. 

Implementation Notes

  • YOU MAY only update the methods with the WRITE YOUR CODE HERE line. 
  • DO NOT add any instance variables to the Classroom class.
  • DO NOT add any public methods to the Classroom class.
  • YOU MAY add private methods to the Classroom class. 
  • DO NOT use System.exit()

Writing JUnit Tests

You do not have to submit this, this is for you to test your own code and is OPTIONAL.

Since this implementation contains public methods, we can test it independently of the driver using a test class.

In the main project folder, there exists a “test” folder next to the “src” folder. This contains a JUnit test class, which can run and test pieces of your code. To compile and run these tests, you must install the Test Runner extension. See the Programming FAQ for more info on VScode extensions.

There are spaces for you to write tests for each method, and you must fill these tests in. Once you do, remove the fail() statements at the bottom and run. 

You are provided with a premade JUnit test class for RUKindergarten. You can finish writing the test methods, by using JUnit test methods (assertTrue(), assertFalse(), assertEquals()) in order to test your code.

Again, writing JUnit tests is optional and is only as good as the tests that you write.

Tests not running? 

First, make sure you’re in the right folder and the tests are implemented. Next, if you have the “Code Runner for Java” or Oracle “Java” extension, make sure you uninstall those extensions. Remember that you must fill in the tests for enqueue() and dequeue().

VSCode Extensions

You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:

Importing VSCode Project

  1. Download RUKindergarten.zip from Autolab Attachments.
  2. Unzip the file by double clicking.
  3. Open VSCode
    • Import the folder to a workspace through File > Open

Executing and Debugging

  • You can run your program through VSCode or you can use the Terminal to compile and execute. We suggest running through VSCode because it will give you the option to debug.
  • How to debug your code
  • If you choose the Terminal:
    • first navigate to RUKindergarten directory/folder
      • to compile:  javac -d bin src/kindergarten/*.java
      • to execute: java -cp bin kindergarten.Driver

Before submission

Collaboration policy. Read our collaboration policy here.

Submitting the assignment. Submit Classroom.java separately via the web submission system called Autolab. To do this, click the Assignments link from the course website; click the Submit link for that assignment.

Getting help

If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.

  • Find instructors and head TAs office hours here  
  • Find tutors office hours on Canvas -> Tutoring -> RU CATS
  • In addition to office hours we have the CAVE (Collaborative Academic Versatile Environment), a community space staffed with lab assistants which are undergraduate students further along the CS major to answer questions.

Problem by Ethan Chou, Maksims Kurjanovics Kravcenko, and Kal Pandit