Seat a Student - Maker of seating charts


Start Date:

Winter 2015

Completion Date:

Summer 2016

Languages & Technologies Used:

Java, Machine Learning/Genetic Algorithm, Graphs (data structure)

Description:

“Seat a Student”, uses student preferences and classroom layout to generate a seating chart. Data is modeled using graph data structures (implemented using adjacency lists). An evolutionary algorithm then iterates over the data to converge on an optimal seating arrangement.

Inspiration:

One day I watched my high school computer science teacher as she slogged through completing seating charts for each of her 5 classes. She would always pass around half sheets asking students about their seating preferences (who they did/didn’t want to sit next to, preference to sit closer to windows or front of the room, etc.). It seemed like such a repetitive and arduous task and it made me wonder if there was a way to automate it…

The idea had slipped out of mind for a few months until I learned about a data structure called a graph. Graph's instantly reminded me of the Seat a Student problem: each student could be a node while each listed preference for another student would be an edge connecting the two students! (I dubbed the problem “Seat a Student” to parody the intro programming class’s assignment called “Pick a Student”) I got to work coding and white boarding, and I soon realized that although I had a powerful way of modeling the problem. I had yet to find a decent way to solve it. Once again the project faded back into the depths of my mind.

That summer I participated in an internship at a startup company called “The Wireless Registry”, and they wanted me to look into methods to optimize their mobile API. One day while looking for machine learning algorithms and libraries I could implement, I came across evolutionary algorithms. I realized this was the last piece of the seat a student puzzle! I came up with a way to represent possible seating arrangements in chromosomal form and ran these in the algorithm to optimize the seating charts.

Development & Challenges:

Several times during this project, I ran into road blocks that hindered me from proceeding simply because I didn’t know enough about what I was doing to know where to even look for solutions. I overcame this just by keeping the idea/project in the back of my mind and trying to learn as much as I could. By not giving up on this project, I ended up creating a solution to a problem I had no idea how to solve when I started working on it!

Shortcomings:

The UI/UX. The whole program was text based and I never really got around to building a GUI and that made it pretty difficult to use.

External links: