I'll use “TCS” — theoretical computer science — as the name of your course
Should an introductory TCS course have coding assignments?
Yes and no.
Since there are two parts to that let me start with the third — the And!
When Johnny will only have candy and momma insists that spinach is good for him the result can be a difficult impasse. Yeah we all know because we've all been that Johnny/Debbie some time. And if we've grown well its because Momma is firm. And kind. And tells lies when needed. In the case of momma the lie may take the shape of some "tasty" — more likely colorful — jam added to the spinach.
Programming in a TCS course can be relevant, even central. Mostly its unhealthy but necessary jam. The point of this post is not to harp on the unhealthy jam but to remind about the underlying spinach!
Yeah the typical CS student resists theory/math. And the resistance can be as bad as Johnny above so that some artful lying helps. Here's a difficult story from the fringes, where I am sure that some of the kind of stuff you are trying to do would be helpful. But that it is helpful doesn't make it relevant.
The first course I taught in the 80s was a discrete math course. I've never worked harder in my life. And students have never hated me more😆. So over years I changed my tack — less time on the course more on the engagement with students. You learn with time that education is not happening if engaging is not. So that has to become a priority. So then over time the tables turned and while students stopped complaining, even showed their enjoyment, colleagues sometimes expressed their resentment — You are charismatic. You can get away with murder. Doesn't mean what you are doing is right! The doing could be a wide variety of things… including teaching programming in a TCS course. And it can certainly help the larger teaching objective. But it doesn't make it right. Because its not relevant. To be fair maybe 98% students appreciated my ways. But there are the 2% who protest the irrelevant intrusions. And they are right in doing so.
So we need to explore what are the aims and purposes of a TCS course.
Here are the basic ones that come to my mind:
1. Negative Results
I think these "Can't Do" results are the biggest and most significant content. You cannot…
1.1 Write a regular expression/DFA that accepts anbn
Even though the almost identical a*b* is trivial. Usually in TCS context that goes by the moniker pumping lemma.
So your "programming assignment". here would be (say): Write a python regexp that matches brackets. And of course the answer is NO CAN DO. The larger learning goal would be the appreciation of this classic regexp to match html tags
1.2 Subsume Syntax under Context Free Syntax
If a language like C say is "statically" typed that means the type-system is syntax. So if it is syntax why is it not part of the CFG? Because while it is syntax its not context free syntax.
1.3 Detect whether an arbitrary Turing machine will halt
And of course the TM egs are most famous — You cant detect an infinite loop in the most general case. I find it amazing how even PhDs in CS from good universities don't get halting. I've sat in masters degree defenses where the great professor asks (in effect) Why did your compiler not prove correctness? If the student had a good grounding in TCS he would say: Well respected Sir… There's is the Rice theorem…
2. Universality Results
These are fuzzier — more philosophic than scientific — than the above. And yet closer to the heartbeat of the field.
A colleague who was teaching TCS made the following insightful observation :
CS is the conjunction of machines, computation, logic, languages and information theory. TCS should highlight these connections.
He candidly said that his course is light on logic and zero on information theory. Nevertheless it doesn't take more than a few minutes to 3-way connect Shannon, Information theory and the Bit.
Some of these profoundly wide-ranging ideas...
- Church Turing thesis
- The equivalence of widely different formalisms
- The relation of Turing-undecidability with Gödel-incompleteness with the lesser known Tarski undefinability
- The deep links of logic and computability...
- ...Going to the fact that Gödel is where it all starts, Turing is "just" an engineering improvement...
- ...To the use-mention distinction and why its central to CS.
[I sometimes tickle my students with this "proof":
Cat is a mammal.
Mammal is a a 6-letter-word.
Therefore cat is a 6 letter word
Perhaps mre recognizable in CS as the language-metalanguage distinction.
- To the giddy labyrinths of the famous Gödel-Escher-Bach
[I recently learned that a large no of CS-ists of today became that because they read GEB 30+ years ago. Heh! I'm one of them!]
- The AI-TCS link. From Minsky back to Turing AI and CS has strong links. Coincidence?
- The matching of the Chomsky hierarchy with the machine hierarchy. Floyd Beigel is good here.
Do you really cover all this?!
As I said above its ok to lie 😉
No we cant do all of that, we cant do most of that. But if the teacher doesn't even have a sense of this direction I'd say the course has lost its way.
3. CS = Math
Turing was a mathematician, as was Church, von Neumann, Babbage, Ada Lovelace, Leibniz, Pascal… Is it simply coincidence that they are foundational in CS?? All the way back to al Khwarizmi whose book gives us algebra and whose name gives us algorithm!
In Turing's seminal paper "a computer" was a mathematician doing a computation that was so dumbed-down that it was mechanizable in principle.
Real computers made it so that that mechanizability goal would become practical as well
Unfortunately we've gone so far down that road that most of us find ourselves on the wrong side of Dijkstra's sneer:
And I don't need to waste my time with a computer just because I am a computer scientist.
One long term goal of having undergone a successful TCS course is that the student – later computer scientist – be firmly placed in the science side. Else default to the computer side!
How far does programming in there help?
Note that's not a rhetorical question!]
I do not wish to dissuade you from teaching programming in the TCS course… Just to give a feel for the sense of its relevance.
If you want a programming-centered course that is directly and fully relevant to the aims of TCS look at Neil Jones' Computability and Complexity from programming perspective.
Note: i am not recommending it! It's a monograph not a text and heavy going for the less than well-equipped and strongly motivated.
More historical math-logic-CS-programming stuff
[Yeah first three my writings...]
4. The Human Context
Most of us accept that our modern world is largely based on something vaguely called "science". Notice the overlap "science" and "computer science"?
And that this science is the creation of some remarkable individuals called "scientists". Maybe we teachers have some role to play in producing the scientists of tomorrow?
On the one hand...
Look at the typical CS curriculum. How much science is there?
- Some "surrounding" subjects eg discrete math, statistics...
- Some soft subjects eg management, economics...
- a great deal of technology which is typically classified as "core"
eg programming in some fashionable langauge, databases and OS that showcase some technology and so on and so forth
In short you will find very little actual science in a typical CS curriculum... Other than the TCS course! So TCS teachers have a special responsibility.
On the other...
Beyond being CS-ists and teachers we're ultimately humans ... Participating in inducting our students into the fold of responsible adults.
CS has a rather dubious role on the human scene...
In the larger CS curriculum, TCS a very special place toward this responsibility as follows:
No one needs to be told that humanity finds itself in a mess from its burgeoning self-destruction capability.
And its hardly an exaggeration that this self-destruction capability is a direct consequence of our technological super prowess — nuclear winter? ecological disaster?? Pandemic mgmt for the big-corps not the living beings??? Just plain ol' drowning in our plastic garbage????
And computer technology is ever the servile hand-maiden of every world-destructive possibility
If we wish to contrinute to a world that will withstand our insane self destruction capability we need to have inhabitants that will withstand this insanity. And a key element of that is humans who can withstand the onslaught of so-called intelligent/AI systems that are mechanical at their core.
To be able to do that the future generation needs to understand the nature of this technological insanity without losing their humanity.
From the standard CS curriculum, a well-directed TCS can be one of the key components to that humane sane understanding.