One of the challenges in teaching theoretical CS – or at least, the more abstract parts of computer science – is that many of the topics can seem completely divorced from reality. Given that a lot of students take introductory CS courses to build up their programming skills – for interest, because they need them in a research lab, or because they’re looking for a safe and stable career path – it’s just as important to sell the students on the topics as it is to provide a clear and easily understood presentation.
A question I frequently ask myself when I’m teaching a class is whether the material has stakes. Are the motivating examples and questions things that students would consider inherently interesting independent of their technical merits?
About six months ago, I had the pleasure of teaching CS106B, the second course in Stanford’s introductory programming sequence. Topics include recursion, recursive problem-solving, and algorithmic efficiency. This is where students learn to solve problems like “list all the subsets of a set ” or “generate all permutations of a given string.” I have to confess that I’m the sort of person who really gets a kick out of problems like these (and likes playing around with ways of using nonstandard number systems to generate them), but the fact that I think it’s cool to generate all partitions of a set doesn’t really matter if I can’t get the students to find the topic interesting as well.
Over the course of teaching CS106B, I had a ton of fun taking classic algorithms problems (often from Karp’s 21 Problems) and dressing them up in a way that motivated student engagement. One particular example of this that students found interesting (but challenging!) came up on the eve of the 2016 US Presidential Election. NPR had reported that it would be possible to win the presidency with 27% of the popular vote by winning a majority of votes in the 11 states with the highest number of Electoral College votes. Someone tweeted at them that it would be better to instead win a majority of votes in the least-populous states, which would require only 23% of the popular vote. I thought about the setup to this problem: you know the number of votes required to carry each state, along with the number of electoral votes for each state, and you want to find the way to get to 270 electoral votes using as few popular votes as possible. Which states do you choose to do this?
I pretty quickly realized that I’d seen this problem before – this is the 0/1 Knapsack Problem! We can think of each state as an object whose “weight” is the number of popular votes needed to win a majority, and whose “value” is its number of electoral votes. This means that all of the theory built up over the years for the knapsack problem easily transfer over to this new problem of winning the presidency with the fewest number of electoral votes.
I ended up turning this problem into a programming assignment for CS106B. I asked some of my undergraduate section leaders to pull up historical voting data for different presidential elections, and to my astonishment two of them (Nick Bowman and Eli Echt-Wilson) pulled up historical data going back to 1828 by the end of the day. Using some shape data files for US states that I’d downloaded back in 2011 (unfortunately, I cannot remember the source), I whipped up a little visualizer and asked students to code up the back-end logic to take in a list of states (along with popular votes cast and electoral vote totals) and output the minimum collection of states necessary to win the presidency. I gave some high-level guideposts about how to proceed – start off by writing a brute-force recursive backtracking solution, then add memoization – and provided starter code that hooked their answer into the visualizer.
The results were quite interesting. It turns out that the NPR article still had it wrong. Based on voting patterns from 2012, and making some simplifying assumptions (that electors never defect, that states that split their electors instead decide to send them as a bloc, that there’s a majority in the Electoral College, that there aren’t any third-party spoilers, etc.), it turns out that you’d only need around 21.1% of the popular vote to win the presidency. Just win the states highlighted in gold:
The particular states you’d need to win here seem like a pretty eclectic assortment. It turns out it is a good idea to win some big-population states like California and Texas, though you’d forgo others like New York and Florida. I’m curious what sort of platform you’d need to campaign on in order to win these states. 🙂
It’s interesting to run this program over data from different years to see what other trends emerge. You can run it in 1860 versus 1864 to see that, for some reason, in 1864 a bunch of states from the South didn’t cast Electoral College votes. You can run it over a longer period of time to see the addition of new States to the Union and the change in population centers over time.
One of the advantages of framing the knapsack problem this way is that many students were genuinely curious to explore this problem independently of the underlying CS theory. It motivates students to ask questions about how their government (or the government of their temporary host country) operates, its history, and questions of fairness and electoral power. In the end-of-quarter evaluations, many students reported this problem to be one of their favorites from the quarter.
I think there were some rough edges with the way the question was deployed the first time around – it’s a pretty tricky problem to assign to students who are still getting comfortable with recursion – but with a few touchups I think it could have a lot of staying power.