understanding

Algorithms seem to keep coming up. Last week, my calculus class started asking what math classes they will take next in college. This made me realize that our educational system gives kids the very strong impression that math subject have an inherent relative sequence, and that there must be a fundamental mathematical reason that Algebra is taught before Geometry. Which, of course, is not true. So I told them about some of the different classes I took in college and sketched out the various directions that further study in math might lead: multivariable calculus being very close to what they’re learning now, and linear algebra, statistics, discrete math, and algorithms being some of the other points on the spectrum. I’m not sure why, but when I was explaining algorithms and how they relate to computer science (CS was my major), they suddenly perked up and got interested. I was describing sorting algorithms as an example and, I swear, someone said, “We should study that stuff!”

So here’s an algorithm question for you, based on the other time this topic came up last week: Assume you have 350 students in a school. Each student needs to be assigned to one of 15 special classes. The capacity of the classes varies from 18-36. Each student fills out a form expressing their preferences by ranking their top 5 most desired classes. How do you assign students to classes so that: 1, no class exceeds its capacity, 2, classes contain only students who ranked the class somewhere in their top five and 3, each student gets a class as high up on their preference ranking as possible. Now obviously we can’t make an algorithm that’s guaranteed to fulfill the second two conditions, because it’s theoretically possible that zero students choose a particular class, or that all students in the school have the same preferences. But in real life their choices are at least somewhat distributed. But either way, how can we do the best possible job?