Theory of Computation topics mostly as elective in the planned ACM/IEEE CS2013 curriculum

As part of the intermittent research I have taken up on teaching Theory of Computation, I have been reading a few papers on curriculum development for Computer Science. As it happens, there is currently a draft—the so-called ‘Strawman draft’—up for discussion until July 15 in this forum. Upon community input, that draft may be updated and it will become the new version of ACM curriculum guidelines for CS (and its variants) in 2013; see [1] for a 2-page context.

One thing that may surprise the CS researcher and professor who is in the system since a while, is that since the Computing Curricula CC2001 version, and carried over in the Strawman draft, most of automata is elective, only a little complexity is core, and, e.g., Turing machines is elective—which was unlike the seminal first version that described computing as a discipline and principal curriculum topics in 1989 [2] that did have formal languages, automata, Turing machines, complexity and computability in the core. More precisely, the CS2013 proposal is as follows (layout edited):

AL/Basic Automata Computability and Complexity

[3 Core-Tier1 hours, 3 Core-Tier2 hours]

Topics:

[Core-Tier1] Finite-state machines, Regular expressions, The halting problem

[Core-Tier2] Context-free grammars (cross-reference PL/Syntax Analysis), P vs NP (tractable and intractable problems), Definition of P, NP, and NP-complete, Exemplary NP-complete problems (e.g., SAT, Knapsack)

AL/Advanced Computational Complexity

[Elective]

Topics: Review definitions of the classes P and NP; introduce EXP, NP-completeness (Cook’s theorem), Classic NP-complete problems, Reduction Techniques,

AL/Advanced Automata Theory and Computability

[Elective]

Topics: Sets and languages, Regular languages (Review of deterministic finite automata (DFAs), Nondeterministic finite automata (NFAs), Equivalence of DFAs and NFAs, Review of regular expressions; their equivalence to finite automata, Closure properties, Proving languages non-regular via the pumping lemma or alternative means), Context-free languages (Push-down automata (PDAs), Relationship of PDAs and context-free grammars, Properties of context-free languages), Turing machines, or an equivalent formal model of universal computation, Nondeterministic Turing machines, Chomsky hierarchy, The Church-Turing thesis, Computability, Rice’s Theorem, Examples of uncomputable functions, Implications of uncomputability,

Aside from pondering how one can do DFAs and regular expressions but not also NFAs (to name but one), this list contrasts quite markedly with the one from the survey I conducted earlier, which I blogged about and whose results are online. One of the questions of the survey was whether something like a theory of computation course should be part of a CS curriculum, which was responded with a near-unanimous “yes”, in contrast with the CC2001 and the Strawman report. Another question was about which topics should be covered, where a list of 46 topics was provided and respondents could add more. For each topic, they had to select it as being ‘essential’, suitable for an ‘extended version’ of a ToC course, or as ‘peripheral/may be skipped’. Summarizing the full computed preferences of the topics, we see a different picture than the categorization in the Strawman Draft, above; the top-20 topics with their corresponding percentage where the respondents answered with ‘essential’ are:

Regular expressions 98.55, Deterministic Finite Automata (DFA) 95.71, The Turing Machine (basics) 94.37, Context-free Grammars (definition, ambiguity, simplification, derivations) 94.20, Non-Deterministic Finite Automata (NFA, epsilon-NFA) 88.41, Equivalences & conversion RE and automata 85.29, Problems a computer cannot solve 85.29, Halting problem 82.81, Properties of Regular languages 80.30, Regular grammars (RG) 80.00, Examples of some undecidable problems/languages 78.13, Church-Turing thesis 77.94, Computability and decidability 76.81, Equivalences & conversion DFA, NFA, epsilon-NFA 73.85, P, NP, NP-complete, NP-hard, co-NP 73.53, Universal Turing Machine 72.06, Undecidability 68.57, Pumping lemma for Regular languages 68.18, Some well-known NP problems (e.g., TSP, SAT, Node cover) 68.18, Chomsky normal form, hierarchy 67.16.

I understand that not everything can go in the curriculum, as there are more and more topics that ought to be in a CS curriculum whilst the study programme time remains the same, but the rationale behind the Strawman Draft’s lists on ToC topics eludes me. Meanwhile, my COMP314 students will get a full plate of ToC in the upcoming semester (including, among others, Turing Machines, and they will be reminded of Turing’s centenary this year [as an aside: even Nature finally recognized something from Computer Science [3], honouring it with a special, too]).

References

[1] Mehran Sahami, Ernesto Cuadros-Vargas, Steve Roach, David Reed. Computer Science Curriculum 2013: Reviewing the Strawman Report from the ACM/IEEE-CS Task Force. SIGCSE’12, February 29–March 3, 2012, Raleigh, North Carolina, USA.

[2] Peter J. Denning, Douglas E. Comer, David Gries, Michael C. Mulder, Allen Tucker, A. Joe Turner, and Paul R. Young. Computing as a Discipline. Communications of the ACM, 1989, 32(1): 9-23.

[3] Chouard, T. Turing at 100: Legacy of a universal mind. Nature, 2012, 482 (7386), 455-455.

Advertisement