Late in the evening more than 30 years ago, Tom Rona, math department head at the Middle School, had been puzzling over the best way to sort students into classes. Hours passed; he relented and went to bed. In the middle of the night, he “had this most amazing dream…a very detailed dream in which an algorithm was pretty much laid out in front of me.” He jolted out of bed in excitement with a metaphorical cry of “Eureka!” and immediately scribbled down the details. The next morning he implemented the code, and SharpSchedule, the engine of Lakeside’s scheduling program, was born.
The Upper School has more than 550 students, about 130 classes, and nearly 100 teachers. To give an analogy of how daunting course assignments are, imagine playing Sudoku, except the usual two-dimensional nine-by-nine grid is supplanted with a four-dimensional hypercube with lengths in the hundreds. The task of assigning students and teachers to classes and classrooms seems a Sisyphean undertaking. Accounting for each individual student’s course list as well as class section and room placement, “the number of possible distinct student schedules is larger than the number of particles in the known universe,” says Mr. Rona. And the tiniest adjustment in a single student’s schedule could butterfly-effect into gaping imbalances later on.
However, Mr. Rona’s first version of the scheduling crystal ball made years ago was less than 30 kilobytes in size, data and all (for comparison, an iPhone photo is about 100 times larger, at 3000 kilobytes). The program was written back in the days when computing power was severely limited; Mr. Rona says that this forced him to write a “zero graphics” program, essentially “an implementation of the Hungarian Algorithm that I wrote for my master’s thesis.” Thankfully, computers are much faster nowadays, and the scheduling program now runs an exhaustive search which produces schedules for the entire school in under a minute.
When Mr. Rona took charge of scheduling, he got the job from Dean Ballard, former math teacher and Lakeside’s longtime math team coach. Mr. Ballard created a scheduling algorithm and ran it on a computer which he built by himself, nicknamed “Clem.” (Mr. Rona compliments Mr. Ballard as an exceptional and inspirational “peerless mathematician and programmer.”) Before Mr. Ballard, teacher John Jamison wrote a scheduling program on his calculator hooked up to a mini printer. And even earlier, of course, Bill Gates developed scheduling code in Fortran during the 1970s, back in the days of paper tape programs and time sharing systems. Gates remarked in a 2005 talk at Lakeside, “By the time I was done, I found that I had no classes at all on Fridays. And even better, there was a disproportionate number of interesting girls in all my classes.”
As the succession of schedule masterminds highlights, the scheduling program has evolved countless times. “Lakeside has benefitted from the in-house nature of the project,” says Mr. Rona, “because we could make changes without waiting for a software company to make them and sell us a new version.” Faculty working on the program have modified it to reflect scheduling changes such as the new AB schedule, to add a graphic user interface, and to interact with Veracross.
The program takes input ranging from course offerings, teacher availability, room sizes, and (of course) students’ course requests. The data is stored in SQL Server and Access databases. From there, the algorithm kicks in.
The first phase of course assignments, “scheduling,” determines the list of classes for each student. The second phase, “sectioning,” assigns students to particular class sections. Sectioning is a recursive algorithm (a process in which a function calls itself) akin to a depth-first search on a graph. Upon the completion of these steps, Mr. Rona performs fine-tuning, which mostly consists of fixing schedules with deadlocks that must be manually resolved.
Throughout the program, an underlying cost function considers the many qualitative aspects of a “good schedule” and quantifies them into a single index for ranking. For example, one of the primary concerns is student balance—each section of a specific class should all have about the same number of students with a roughly equal distribution of genders. Other times, heuristics come down to priorities: seniority establishes precedence, and graduation requirements are scheduled before electives. This hierarchy is the reason why students are asked to list multiple elective preferences, says Mr. Rona: electives are further down the scheduling priority order and thus will face more conflicts.
The presentation of the schedule itself has also changed over the years. Upperclassmen may have nostalgic memories of picking up their schedules from their mailbox; underclassmen are probably used to receiving emailed schedules from their advisors. However, decades ago, Mr. Rona recalls, “I printed the schedules on fanfold paper from a dot-matrix printer, and the paper stretched across my lawn into the neighbor’s lawn. So I had to print on a dry day!”
As high-schoolers caught up in the tumultuous flows of daily life, Lakesiders rarely stop their endless cycle from class to class to pause and appreciate all that happens behind the scenes. But come next fall, when schedules are published—on paper, PDF, or a Veracross page—remember to thank the magic program and the magicians pulling its strings.