Thesis Christ: Anna Wu on Scheduling Algorithms

What is your thesis about, generally?

Technically speaking, Anna Wu is a computer science major working on “stable bipartite one-sided matching under proportionality constraints.” They said that when people ask “what are you thesising on?” they like to “give them the math-y answer so that they get confused and stop asking me questions.” 

So what is their thesis about for the rest of us? Wu is “working with the registrar on a potential solution to a potential problem.” The problem is actually a multitude of issues falling under one umbrella: freshmen (being the endearing innocents they often are) encountering various challenges with HUM 110. Types of problems that might occur are signing up for a different section of HUM 110 each semester, not knowing anything about the professors of the class that students are choosing between, and diminished major diversity within each section due major-related scheduling constraints, like chem majors who have a monster of a Friday lab. 

To solve this, Wu is hoping to write an algorithm that will take survey data and use it to create valid suggested schedules that maximize adherence to student preferences, cross-semester consistency, and major diversity within each section. The survey would be given to all incoming students and ask them to rank preference over all the available HUM 110 sections.

What got you inspired in this?

Wu wanted to avoid a comp sci thesis entirely devoid of practical application. They stated, “I was afraid that I would get pushed into this only-theory route” and said, “I was originally feeling like I wanted to do something that would have a tangible way I could help Reed… or some other institution or system.” One of their ideas was to work on scheduling. So, they went and asked the registrar if there was any possibility of working with real data to create a real solution to a problem. Luckily, everyone at the registrar has been super supportive and sweet. Wu said, “I feel inspired by the fact that the registrar was very open to this sort of idea,” and because of that, it feels like “it’s really possible for a Reed student to make a lasting impact on this place.” The fact that their years of learning might result in an improvement to the institution that allowed this learning to happen means that “it feels extra culminating.” 

What has the process been like for you?

“It’s been good overall.” Wu described the process as “a lot less scary than [they] initially thought going into the year.” The first semester was full of literature review, working with advisor Harper Knittel, and coordinating with the registrar to get anonymized data. Of course, the problem of schedule creation has already been very extensively studied, so the real challenge was asking “what about this problem makes it unique?” The answer to this question would define how to find an appropriate solution. So far the thesis has  been mostly theory, even though Wu wanted an applications-based thesis. “I say this having written about five lines of code so far,” they admitted. However, Wu is optimistic this coming semester will be implementation-centric. 

Regarding workflow, Knittel (who is in their  first year advising theses) has “helped [Wu] structure the work a lot,” as well as “provided feedback on [their] proofs.” Very conveniently, they also “taught [their] mechanism design course,” which means there was a good communal basis to start on. 

What was the wackiest thing you learned about in researching? Any other fun facts?

Within the area of research called “fair division” (which is an overlap of mechanism design and comp sci), there exists a “canon example” of cutting a cake. Simply posed, we ask, “given a cake and n people to share it, how shall we cut it?” Wu was initially lost as to how to properly cite such a ubiquitous problem, but they ended up finding the original source in  Genesis 13:5-9 of all places. 

As the story goes, Abraham and Lot needed to divide up a piece of land fairly and came to the simple solution: Abraham would choose where the dividing line went, and Lot would then pick which plot they preferred. This is still widely regarded as one of the simplest solutions to the problem. “So I’ve cited the bible in my [comp sci] thesis,” Wu said, which is pretty cool.  

Any advice for thesising, or soon to be thesising students?

Wu advised that students approaching the monolithic thesis project shouldn’t feel overwhelmed or unprepared. “What was really comforting for me was talking with all of [her] friends about their thesis, and [finding that] everybody is so knowledgeable.” She continued, “Reed really did what it was trying to do over the past four years” in preparing her to thesis. She found that overall, people underestimated their own expertise in their subject. “It made me feel really good about my education,” she commented, and then elaborated that she felt that students should be proud of themselves for all that they’ve learned in the past three years. 

Anything else you’d like to share with the Reed student body?

Wu hopes that if their algorithm ends up being implemented, that it works out well and that the incoming freshmen don’t hate her for locking them into a Kafkaesque system. At the very least, she said, “I tried my best.”