Next up from SIGCSE 2018 is John MacCormick's session on Strategies for Baing the CS Theory Course on Non-decision Problems

MacCormicks's stance is that CS theory is tough the first time around and using non-decision problems is a viable approach to make theory more accessible to beginners. As MacCormick said in his paper:

… a decision problem may ask the yes/no question, "Does this graph have a Hamilton cycle?" The corresponding non-decision problem is, "Please give me a Hamilton cycle of this graph if it has one."

This leads to writing programs to explore concepts in CS theory rather than just living in the world of proof.

MacCormick goes on to say that:

For this audience, the key advantage of non-decision problems is that they are more realistic: they match the previous programming and algorithms experience of undergraduates more closely.

I love the idea. Writing a program can make an abstract problem more concrete and can lead to better understanding for those of us who are less math inclined.

My next thought was that this shouldn't just be a change implemented in theory courses. Some of these ideas should move down to more introductory CS classes. Not the hardcore stuff but light introductions to the topics so that we can layer the learning. If we introduce some of these concepts in CS 1 classes then when they get to the theory class it won't be the students first rodeo.

I've had success with this when teaching recursion early. I've also done it with other concepts. When we teach the Towers of Hanoi, yes, it's a nice recursion problem but really it's to get the students thinking about run time and a bit of proof. likewise, when we do a maze solver in NetLogo we're alluding to dynamic programming, search, and path finding.

I don't have too much more to say on this topic right now. I'm not enough of a theory guy to sensibly design these experiences. The good news is that MacCormick has written an soon to be released book on the subject. I signed up for a reviewer copy at SIGCSE and look forward to receiving a copy. Once I do I hope to be able to find some gems that I can work into CS 1 experiences.