Seating Chart Optimizer

Introduction

Recent education research suggests that seating arrangements are the single most important factor in student learning. Students who are seated near friends exhibit better concentration, perform better on tests, and express greater satisfaction with the classroom experience.

This research has inspired EduCorp's latest product: SitRite3K. SitRite3K will automate the tedious process of developing seating charts to maximize learning outcomes. After a teacher enters a list of students, along with each student's seating preferences, the program will display an optimized seating chart that places students near their preferred classmates.

The user interface group has already completed a cutting-edge GUI front-end for the SitRite3K system. It will be your responsibility to program the optimization logic.

Your goal for this project is to complete a SeatingChart class that represents a rectangular seating arrangement and provides the functionality for optimizing seating assignments.

The following UML diagram illustrates how SeatingChart relates to the existing classes developed for PA1:

SeatingChart

The SeatingChart class represents a grid of seating locations as a two-dimensional array of Student objects. It is not necessary for every entry to contain a Student: null entries are used to represent empty seats.

The SeatingChart class must conform to the following UML diagram:

You are free to add additional private helper methods, but the public methods must match the UML specification exactly.

Detailed Requirements

Constructor

The constructor must instantiate the two dimensional array seats. It is not the responsibility of the constructor to populate seats with Student objects. Initially, all entries should be null, representing an empty seating chart. No data validation is required for the constructor arguments.

getRows, getColumns

These methods must return the number of rows and columns in the SeatingChart.

getStudent

This method must return a reference to the student at the indicated location. If the location is invalid, this method must return null. A location is invalid if it is outside the bounds of the seating chart.

placeStudent

This method must place the provided student into seats at the indicated location.

• The row and column of the provided Student object must be updated to reflect the student's new location.
• If there was already a student in the indicated location, the existing student must be replaced. That student's row and column must not be modified. (For students who are no longer in the seating chart, the row and column values represent their last valid position.)
• If the indicated location is invalid, this method must have no effect.
• If the provided student reference is null, then a null value should be stored in the indicated location.

getTotalUnhappiness

This method must return the sum of the unhappiness values of all Student objects stored in the seating chart.

swap

This method must swap the students at the two indicated locations. If either location is invalid, then this method must have no effect. Empty seats (null entries) should not be treated as a special case. It must be possible to swap a Student with a null or vice-versa.

stepGreedy

This method must iterate once through the entire seating chart, performing local seating changes where those changes will decrease the total unhappiness of the classroom. This method must conform to the following pseudocode:

for each row in the seating chart, starting with row 0, do:
    for each column in the seating chart, starting with column 0, do:

         Determine which neighbor, if swapped with the value at the
         current location, would lead to the largest decrease in total
         unhappiness.  Perform that swap if the decrease will be greater
         than zero.

In this pseudocode, "neighbor" refers to one of the eight (or fewer) valid locations immediately surrounding a chart position.

The logic above is guaranteed to decrease the total unhappiness of the classroom, or to leave the total unchanged if there are no local swaps that would help.

It is possible to encounter a tie when searching for the most advantageous swap. In the case of a tie, your algorithm must select the first neighbor encountered in a row-major-order traversal of the neighbors. Be careful! If you use a different mechanism for breaking ties your program will appear to work correctly, but it will not pass our submission tests.

solveGreedy

It may be necessary to call the stepGreedy method multiple times before the students reach a configuration where no further improvements are possible. The solveGreedy method must repeatedly call stepGreedy until no additional improvements occur.

Note that the seating chart optimization algorithm expressed in the stepGreedy and solveGreedy methods is not guaranteed to find the best possible arrangement of students. It is easy for this algorithm to get stuck in a sub-optimal configuration that cannot be improved through local swaps. See the "Going Further" section below for more information.

Provided Code and Configuration Files

A .jar file is a compressed archive that can hold any number of Java classes in either source or binary form (as .java files or as .class files). For this project, SitRite3K.jar contains classes that may be used to visualize the operation of your completed code. The following two classes are provided:

• SitRite3K This class contains the main for the SitRite3K application. It provides a graphical interface to the functionality provided by your SeatingChart class.
• SeatingChartUtils This class provides utility methods for working with SeatingChart objects. You shouldn't need to interact with this class directly, but here is the Javadoc in case you are curious: SeatingChartUtils. This documentation describes the file format for loading configuration files in case you want to create your own files for testing.

The following steps should allow you to access these classes within an Eclipse project:

1. Create a new folder named "lib" in your Java project. Download the .jar file and drag it into the newly-created folder.
2. Right click the .jar file and select Build Path -> Add to Build Path.
3. There should now be a "Referenced Libraries" entry in your project explorer. Expanding that entry should allow you to inspect the details of the archive. All classes included in that archive are now available within your project.

Here are a few classroom configuration files that you may use for testing. Unhappiness values are rounded to two decimal places.

• small.txt - A tiny example with only four students.
  • Initial unhappiness: 5.24
  • Greedy Unhappiness: 4.00
  • Optimal unhappiness: 4.00
• small_sparse.txt - The same four students in a larger classroom. This example includes empty seats.
  • Initial unhappiness: 6.00
  • Greedy Unhappiness: 4.00
  • Optimal unhappiness: 4.00
• small_tie.txt - This is an example where you may get a different result depending on how you handle ties. If your code is breaking ties correctly, Sara should switch places with Robert.
  • Initial unhappiness: 1.41
  • Greedy Unhappiness: 1.00
  • Optimal unhappiness: 1.00
• pairs.txt - Eight pairs of friends in a 4x4 seating chart.
  • Initial unhappiness: 31.66
  • Greedy Unhappiness: 17.66
  • Optimal unhappiness: 16.00
• easy_cliques.txt - Four groups of four seated in a 4x4 seating chart.
  • Initial unhappiness: 107.24
  • Greedy Unhappiness: 67.31
  • Optimal unhappiness: 54.63
• hard_cliques.txt - Sixty groups of four in a 12x20 seating chart.
  • Initial unhappiness: 6445.05
  • Greedy Unhappiness: 948.80
  • Optimal unhappiness: 819.41
• challenge.txt - 252 students with randomly determined friend lists containing between zero and ten friends each.
  • Initial unhappiness: 12658.74
  • Greedy Unhappiness: 3406.59
  • Optimal unhappiness: ?????

Submitting and Grading

Submission for this assignment is divided into two parts that must be completed in order.

Part A: Understanding the Project

You should start by carefully reading the project specifications. After you are confident that you understand the specifications, you should log into Canvas and complete the "quiz" for Part A.

Since you must completely understand the project specifications, YOU MUST ANSWER ALL QUESTIONS CORRECTLY TO GET ANY CREDIT FOR THIS PART. You may take the "quiz" as many times as necessary. If you find that it takes many attempts to complete the quiz correctly, you probably aren't doing a good job reading the specification. This is likely to cause problems on future assignments.

Part B: Code Construction

Submit SeatingChart.java through Web-CAT.

Code that fails any of the Web-CAT submission tests will receive at most 50% of the possible credit for this assignment. This includes both the functionality tests and the Checkstyle tests.

Grading

Part A	10%
Part B Style	10%
Part B Correctness	60%
Part B Code Quality	20%

This assignment will include a penalty for excessive Web-CAT submissions. You are allowed ten submissions with no penalty. There will be a one point deduction for each submission beyond ten.

Going Further

As stated above, the optimization algorithm we are implementing for this assignment is not guaranteed to find the best possible seating arrangement. You may be wondering why we are bothering with this imperfect algorithm. In fact, it may be that there is no efficient algorithm that is guaranteed to find the best possible solution for this problem.

There are certainly inefficient algorithms that can find the best solution. For example, we could simply try every possible arrangement of students and keep the arrangement with the lowest total unhappiness. Unfortunately, for a classroom containing 30 students there are \(30! \approx 2.65 \times 10^{32}\) possible arrangements. This calculation would take trillions of years to complete.

I won't present a formal proof, but I suspect that this problem is in the class NP-Hard. (It bears some similarity to the quadratic assignment problem, which is known to be NP-Hard). Such problems probably don't have efficient algorithms: no matter how hard we try, we will never be able to find an algorithm that is guaranteed to solve the problem in a reasonable amount of time.

Of course, just because we can't develop an algorithm to find the best answer doesn't necessarily mean that we can't develop an algorithm to find a pretty good answer in a reasonable amount of time. The algorithm that you implemented for this assignment is known as a "greedy" algorithm. Greedy algorithms make local improvements until no more improvements are possible. Such algorithms may find decent solutions quickly, but they tend to get stuck in "local minima": solutions that are not optimal, but that can't be improved through purely local changes.

Your challenge, if you choose to accept it, is to implement a better algorithm than the greedy algorithm described above. Some version of simulated annealing would probably work well and wouldn't be too difficult to implement. You may be able to think of something even better.

On the challenge.txt input, the greedy algorithm generally finds an arrangement in the range of 3300-4000, depending on the initial arrangement of the students. Eternal glory will be yours if you can beat this mark by a significant margin.

If you choose to work on this portion of the project, you should not include the code in your Web-CAT submission. The Web-CAT tests will be configured to test that the greedy algorithm is operating as expected.

---