Date of Award

Spring 2014

Degree Name

Honors Bachelor of Arts

Department

Mathematics

Sponsor

Jay Yellen

Abstract

We describe our research on the course-timetabling problem, which we model using graph-coloring. We focus on the development of a high-level algorithm that approaches the problem via state-space search using a priority queue. The speed and effectiveness of this algorithm varies based on the properties of two key components: the priority function and the branching procedure. We detail the challenges of developing each component, our current approaches to these challenges, and possible directions of future research.

For testing our algorithm, it is desirable to have a large set of characteristic course-timetabling problems to work with. To this end, we present our implementation of a random problem generator. It begins with existing problems as seeds and uses techniques adapted from genetic learning to generate similar problems. We also describe how the resulting sets of random problems could be used to improve our priority queue algorithm via machine learning.

Lastly, we describe the Java implementation of our algorithm, including the high-level structure of the code and solutions to specific problems encountered in the implementation process.

Rights Holder

Jordan P. Rickman

Download

Share

COinS