Viraj's Weblog

I had an idea of going back to school to take some courses. I have no final decision on this, but for fun I was looking at FAU's summer course listings and was trying to come up with a course schedule.

At some point I realized this course scheduling procedure, which involves checking to make sure the classes don't conflict and corequisites are taken, was rather time-consuming. I thought, why don't I just just write a program that takes as input the courses wanted, parses the listings, and devises a list of possible schedules for me that don't conflict and have all the corequisites.

So I started writing some Python. The main algorithm underwent alot of changes, and I got some good algorithm advice from Randall. Writing it out on paper helped me. The output of the program looks like this. In general it works as follows:

Let's say I have the list wanted which contains the list of courses that I want to take: (A, B, C). Next I have the full courselist: (A1, A2, A3, B1, B2, C, D1, D2). The numbers represent different times for the same course. I used a recursive function to get the various permutations, though they are not exactly permutations because they should only have one of each course.

First I strip from courselist any course that is not in wanted, which reduces the set quite a bit. From the example above, the 'D' courses would be removed. I keep a list called schedule that keeps track of the current schedule. I split the courselist into 2 lists, one containing the first element and all courses that are the same as that element. These can be thought of as parent nodes in a tree. The rest becomes the second list. So I end up with something like this:

schedule = ()
roots = (A1, A2, A3)
rest = (B1, B2, C)

Next I loop through roots, building a schedule for each. On the next recursion, it would look like:

schedule = (A1)
roots = (B1, B2)
rest = (C)

... next recusion

schedule = (A1, B1)
roots = (C)
rest = ()

The recursion should be apparent. Once either rest or roots is empty, I save the schedule. That operation does other checks such as making sure none of the classes conflict, and that the schedule contains all the needed corequisites.

Might not be useful to others, but was to me . Anyhow its good to do little programming projects every now and then or I get rusty.