The Classroom Problem

Abstract

"Who do you want to sit next to?'' In this thesis we develop an algorithm that optimizes a classroom lay-out based on this question. Besides the couples that sit next to each other, it also matters who sits in front (or behind). Even the relations across the aisles matter in the lay-out optimization. Each student chooses three other students and divides ten point points between them, thus creating a weighted graph with potential matches. To fill the classroom we have to address three problems: ``Who are the couples?'', ``Where do the couples sit?'' and ``How do the couples sit?''. First, three algorithms for creating couples are explained. Two of these will, ultimately, not be used. The third is the Blossom algorithm. This algorithm is the one we will be using to create the couples. To determine the positions of the couples, we first use the Repeated Nearest Neighbor algorithm to create a string of couples. Secondly, we use a brute-force approach to determine in which direction this string fills the classroom. For the last problem another brute-force approach is used to determine the orientation of each of the couples: ``Who sits at the left / right table?'' Finally, the created algorithm is tested on an actual class.