Introduction
Problem
Undergraduate students face an interesting and complicated decision when registering for courses for an upcoming semester. A student needs to meet the requirements of his degree using only courses that are actually offered in the coming semester, certainly, but also wants to schedule courses at convenient times throughout the week.
This exercise can quickly get tedious and repetitive and can easily get drawn out over a period of days or weeks. "I'd like to take all Tuesday/Thursday classes," a student might say, "but I need CS-107 and that's only offered on Monday/Wednesday/Friday. I guess I could take that and BSAD-190 since it ends just before CS-107 starts, but that's not a prerequisite for anything so I'd be delayed in taking courses next semester."
I propose building a software application that can automatically produce a schedule of classes based on a student's degree requirements and personal preferences. A program could produce a schedule that satisfies degree requirements through traditional means, but to select the best schedule (or the "top N" schedules) would be significantly more complex. It would also, however, be of far greater utility to students and their instructors. This application will be called Course Correct.
This problem appears simple, but does not have any obvious solution. There is some significant related research into the problem of building a university-wide timetable of courses for a semester; much of this is applicable to the smaller problem of choosing one student's schedule from a fixed slate of courses.
Features and Requirements
Terminology
- A "course" here refers to the abstract course (e.g. CS-107) which may be offered in different semesters at different times and with different instructors.
- A "section" is a particular offering of a course (CS-107 section C in Spring of 2005, taught by Prof. Smith, meeting at )
Manual Searching
- The Manual Searching requirements have already been partially satisfied as part of my semester project for CS-296: Human Computer Interaction. The user interface is functional for the majority of these features, but only a few work reliably with real data.
- The user can search for courses based on any combination of the
following criteria (listed here in no particular order):
- Department (e.g. "Computer Science" or "CS")
- Number or Title (e.g. 021, 2XX, "Java", et cetera)
- Instructor (by exact spelling or phonetic spelling)
- Time of Day (starts at exactly X, ends at exactly X, is anywhere between X and Y)
- Location (campus, building, room)
- Class size (less than X, more than X, between X and Y)
- Number of credits (minimum and maximum)
- CourseCorrect will offer a list of all sections meeting those criteria, including all the pertinent details (course number and title, days and times, instructors, credits, capacity, and enrollment availability).
- The application will be able to keep track of multiple sets of search results without automatically mixing them. The user might, for example, search for all 100-level BSAD classes in one list and all 200-level CS classes in another.
- The user can refine a search at any time by editing the original criteria (that is, the application displays the old criteria and the user makes changes).
- The user may specifically move or copy items from one set of results
to another. The user can still refine the search after this has
happened, in which case the application may do any of the following
(per the user's preference):
- Remove all sections produced in the original search, keep any sections added manually, and add sections produced in the new search.
- Remove everything in the list and add sections produced in the new search (which would result in the loss of any sections added manually)
- Keep the old list unchanged and create a new list for the results of the new search (where the same set of search criteria is associated with both lists).
- Move any sections added manually to a new list, then remove everything and add the sections produced in the new search. Of course, the user could achieve this result manually as well.
Degree Requirements
- The application will understand the requirements for a given degree program and will be able to select courses that meet those requirements.
- This includes an understanding of the prerequisite / co-requisite relationships among courses. The application must not recommend taking a course that a student is not yet qualified to take.
- A new user (or a user like a faculty advisor who will need to consider a different degree program with each use of the application) may select a possible degree program and proceed with using the application without further input.
- "The requirements for a degree program" implicitly includes the prerequisite relationships among courses. The application must not suggest a schedule that includes courses the student is not yet qualified to take.
- A returning student may specify classes she has already taken, which will be considered when analyzing prerequisites and will obviously be excluded as valid courses for the generated schedule.
Student History
- To preserve security and privacy for the University, CourseCorrect will not be able to access any personal information about a student through University records, including any list of classes s/he has already taken.
- If a student downloads and installs the program, she may save locally a list of courses she has taken, which CourseCorrect can then load on future uses.
Schedule Builder
- CourseCorrect will understand a variety of preferences students might
have about a schedule. These include (but are not necessarily limited
to):
- Time of day a section is offered ("I don't want any sections after", for example)
- Day of the week ("I prefer sections that meet on Tuesdays and Thursdays")
- Spacing between sections ("I want two or fewer sections within any 4 hour period.")
- One course over another ("I'd rather take CS-108 than CS-107")
- One course over any other ("I'd like to take CS-109")
- One instructor vs. another ("If I take CS-107, I'd prefer to take it with Prof. Smith", or "I'd like to take any course with Prof. Jones" )
- Total credits in the suggested schedule ("I want to take between 12 and 15 credits")
- Any preference may be assigned a "severity" - the level of concern the user has about that particular preference being met. A student may have a mild preference for afternoon classes but a strong preference for avoiding CS-109.
- The Schedule Builder will recommend a slate of courses that are appropriate for the student's degree program. This need not necessarily guarantee the student will meet his or her degree requirements in time for graduation. Rather, this means the application will recommend courses that are appropriate for degree categories that have not yet been met ("This course meets your Fine Arts requirement.")
- Schedule Builder must not recommend a schedule that includes any courses a student has already taken (assuming the user has supplied this information) and must not recommend a schedule containing any courses for which the student has not met all prerequisites.
Manual Schedule Management
- The user can create schedules manually by adding and removing specific courses; s/he should see the results of this immediately. This means the user can either edit a schedule recommended by CourseCorrect or create a new schedule from scratch.
- The software will allow the user to build, examine, and edit many schedules simultaneously. That is, the user may create one schedule with one set of courses, and a separate schedule with another set of courses.
- The user can add or remove any section of any course to any schedule (even if it's one the computer has proposed), and can copy or move sections from one schedule to another.
Development Plan
- Algorithm Research
I'll begin by researching existing algorithms in areas ranging from basic scheduling problems to logical programming. The scheduling problem I need to solve is novel in its particulars, but has already been solved in pieces by many other researchers. From their experience I'll build an algorithm on paper to solve the schedule-building problem. - Schedule Requirements and Prerequisite Graphs
Based on the input needs of the Schedule Builder algorithm, I'll implement the ability to understand and parse requirements in CourseCorrect. - Algorithm Implementation
After having constructed data for a sample degree program, I'll implement the algorithm itself, without regard (yet) to the user interface. - Application Development
This part of the project is a complex but routine software development task. I'll need to construct an interface for all the features listed above (including all the interaction with the Schedule Builder), test it, and allow users (students) to try it and offer feedback.
Deliverables
Upon completing this project, I'll provide the following deliverables to the department:
- CourseCorrect Executable
I will supply the complete application in a fully functional state, usable by any student or faculty member at UVM. - User's Guide
This documentation will be written for the end user, describing all the application's features and how to apply them toward creating the ideal schedule, verifying the integrity of a proposed schedule against degree requirements, et cetera. It may come in the form of built-in help pages, or of an online reference manual. - Systems Manual
This documentation, separate from the inline comments in the code and from the user's manual, will describe the construction of the overall application, including full details on the algorithm used to build a schedule. It will be produced as a website. - Presentation and Demonstration Finally I will discuss the application from a technical perspective (how it's constructed and how the algorithm functions) and demonstrate its most interesting features before an open audience of interested Computer Science faculty and students and any others who wish to attend.