## Friday, April 06, 2007

### Space Optimization

Our enrollment has been growing by leaps and bounds, which naturally makes other things want to grow too. Recently we've been discussing the "classroom crunch." Extra sections of service classes create pressures to find new places to teach classes. At the most popular hour, we're simply out of space. Or are we? I ran a query to tally up how many sections are taught in each of the standard time slots. This ignores a few oddball arrangements, but includes the 8am - 2pm MWF 50-min. sections as well as the usual TTh ones (e.g. 8:00am-10:45am TTh). There are 12 in all. There are 164 sections being taught in those slots, or 13.7 on average per slot.

The most popular time turns out to be TTh at 9:30am. (My favorite is 8:00am TTh, which is the least-used, so I can have about any classroom I want). The actual table is shown below.

I think it's fairly obvious that the perfectly optimal arrangement would be to have all slots used at the average level of 13-14 classes per slot. This not only reduces competition for space when scheduling, but reduces demand too. To see this, imagine that you are a student trying to fill out a schedule. If you must take a TTh 9:30am class, then there are 27 other classes that you cannot take because you can't be in two places at once. The graph below shows the actual and optimal distributions of sections across slots.

Can we quantify the difference this makes to students? At first I thought that using information entropy would be a likely metric. This is a cute idea, but doesn't seem to make sense on closer inspection. We're not communicating information here, but talking about course combinations. So the more prosaic solution is in order: the number of arrangements of possible classes is what's important. Ideally, I would like to compute the total number of schedules possible with the actual versus optimal arrangements. This is possible, although it requires some programming. I'll assume that most students would want to choose a five course schedule, which is typical. First, you'd need to generate all of the combinations of 12 objects taken 5 at a time (there are 792 of these) and associate those with the weights in the table, multiply those to get a product that represents the number of class schedules possible for the chosen slots and finally sum those to get the total number of schedules. That sounds like more fun that doing my taxes this morning, but unfortunately April 15 is just around the corner! Let's approximate instead.

Assume that a student's five desired classes are randomly distributed among the twelve slots. Then the expected number of schedules (i.e. average) would be the average number of classes available in a given slot, raised to the fifth power. But here we don't want to use the usual arithmetic average because we're multiplying. So we use the geometric average instead. To do this, we multiply the numbers in the table above and take the 12th root to get 11.9. By comparison, the geometric average of the optimal arrangement is the same as the arithmetic average (because all the numbers are the same--this is the only case where they're equal).

So we can say that after a student has chosen his or her most important class (crossing off one time slot), there are about two more sections available in each of the remaining ones in the optimal arrangement than in the actual one. We can now compute the (average) number of possible schedules that this represents.

Actual: 19,967 ways to fill in the four elective classes, after choosing the favorite.

Optimal: 34,886 ways.

This represents a 75% increase in schedule selections available to the student. I may put a computer science student on the job of actually calculating the exact answer, but this ought to be pretty close. With that kind of positive outcome, I'd argue that it's worth taking up the issue.

UPDATE: After doing the taxes I messed around with this a little more. Suppose a student has a roster of his or her top three picks for classes. All other factors being equal, what is the probability that the student can get all three of these classes? If ALL university classes are taught in one or two time slots the probability is obviously zero. I calculated this for both the given distribution and the optimal one and got 71% and 77%, respectively. So there's a six percent chance increase in the probability that a given student will be able to get his or her top three choices in the optimal distribution. This would increase the number of 'happy' students (using this definition) by about 8%. Not as dramatic as the analysis above, which was based solely on number of permutations available, but still significant.