Facts and opinions about Theory of Computation in Computer Science Curricula

Computing curricula are regularly reassessed and updated to reflect changes in the discipline, and, at the time of writing, the ACM/IEEE curriculum ‘CS2013’—also called the Srawman Draft [1], about which I blogged earlier—is under review. South Africa does not have its own computing organisation that for official accreditation and does not provide official guidelines on quality and curriculum planning, and therefore such international curricula guidelines provide the main guiding principles for curriculum development here. As is known, there’s theory and there’s practice, so a fact-based assessment about what the guidelines say and what is happening in the trenches may be in order. Here, I will focus on assessment of the curriculum with respect to one course in particular: theory of computation (ToC)—consisting of, roughly, formal languages, automata, Turing machines, computability, and complexity—which introduces the mathematical and computational principles that are the foundations of CS, such as the foundations of programming languages and algorithms, and the limits of computation. One may wonder (well, at least I did): How are ToC topics implemented in CS curricula around the world at present? Are there any country or regional differences? What is the sentiment around teaching ToC in academia that may influence the former?

To answer these questions, I examined how it is implemented in computer science curricula around the world, and the sentiment around teaching it by means of two surveys. The first survey was an examination of curricula and syllabi of computer science degrees around the world on whether, and if so, how, they include ToC. The second one was an online opinion survey (about which I reported before). The paper describing the details [2] has been accepted at the 21st Annual Meeting of the Southern African Association for Research in Mathematics, Science, and Technology Education (SAARMSTE’13), and here I will cherry-pick a few salient outcomes. (or go straight to the answers of the three questions)

Syllabi survey

The 17 traditional and comprehensive universities from South Africa were consulted online on offerings of CS programmes and also 15 universities from continental Europe, 15 from the Anglo-Saxon countries, 6 from Asia, 7 from Africa other than South Africa, and 8 from Latin America. It appeared that 27% of the South African universities—University of KwaZulu-Natal, University of South Africa, University of Western Cape, and the University of Witwatersrand—has ToC in the CS curriculum, compared to 84% elsewhere in the world, which is depicted in Figure 1. The regional difference between Europe (93% inclusion of ToC) and the Anglo-Saxon countries (80%) may be an artefact of the sample size, but it deserves further analysis.

Figure 1. Comparison of ToC in the CS curriculum in South Africa and in other countries around the world (FLAT = formal languages and automata theory, i.e., not including topics such as Turing machines computability and complexity).

The level of detail of the ToC course contents as described in the course syllabi online varied (but see below for better data from the opinion survey), and only 43 universities (of the 59 with data) had sufficient information online regarding timing of ToC in their degree programme. Five universities had it explicitly in the MSc degree programme, with the rest mainly in year 2, 3, or 4 (but see below for better data from the opinion survey), and 5 universities have it spread over 2 or more courses, whereas the rest offers it in a single course (sometimes with further advanced courses covering topics such as probabilistic automata and other complexity classes).

Opinion survey

The opinion survey was quite successful, with a response of n=77. 58 respondents had filled in their affiliation, and they were employed mainly at universities and research institutes: 12 respondents gave an South African academic affiliation and thus the majority of respondents were from around the world, including, among others, the USA, UK, Canada, Germany, Italy, Switzerland, Indonesia, China, Cuba, Brazil, and Argentina. A more detailed characterisation of the respondents, as well as the complete (anonymised) raw question answers with percentages, sorted by question (exported from LimeSurvey) are online at http://www.meteck.org/files/tocsurvey/.

There was a near-unanimous agreement (76 of the 77) that ToC should be in programme, 74 (96% of the answers) have it currently in the programme, and 82% had it in their degree programme when they were a student. Overall, the timing when it is taught in the programme has varied little over the years (see Figure 2). Further, for 90% of the responses, ToC is core in the curriculum, and secure in the programme for 86% (only few reasons were provided for “under threat/other”: that it has been removed from some specialisations but not all (in part due to the computer science vs. information systems tensions), or threatened due to low enrolment numbers).

Figure 2. Comparison between when the survey respondents did ToC in their degree and in which year in the programme it is taught at their university (where applicable).

Regarding the topics that should be part of a ToC course, the following is observed. The survey listed 46 topics and for each one, a possible answer [essential/extended/peripheral/no answer] could be given. The complete list of ToC topics ordered on percent ‘essential’ is shown in Table 1. In short: it is perceived decidedly that formal languages, automata, Turing machines, complexity, computability and decidability themes form part of one coherent offering, although the detail of the sub-topics covered may vary.

Table 1. Ordering of the 46 ToC topics, by calculating the percentage of responses that marked it as ‘essential’ out of the given answers.

Given the plentiful anecdotes, hearsay, and assertions in other articles about teaching ToC concerning difficulties with ToC teaching and learning, the survey also included some questions about that. The data provided by the respondents do substantiate the existence of issues to some extent: 44% of the responses answered that there are no issues and everything runs smoothly, or: a slight majority does, which can be subdivided into 32% ‘causes problems in the academic system each year’ and 24% where ‘management/student affairs has gotten used to the fact there are problems’. Several respondents provided additional information regarding the issues, mentioning low pass rates (n=3), that students struggle because they do not see the usefulness of ToC for their career (n=4), that it also depends on the quality of the teacher (n=2), and low enrolment numbers (n=2). For 45%, the first-time pass rates remain below 60% and with 80% of the respondents, the pass rate remains below 80%. The correlation between pass rate and issues is 0.79 (n is to small to draw any conclusions for the other combinations of pass rates, class sizes, extrapolated course content, and having issues).


There is much one can discuss about with respect to the data (and more is included in the paper than I cover here in this blog post). Considering the curriculum analysis first, it can be summarized that ToC in CS is solidly in the programme, is oftentimes taught in a single course, and mostly in 2nd and 3rd year of the undergrad CS programme. Interestingly, there is a discrepancy between the ‘essential’ content according to the survey and the newly proposed ACM curriculum guidelines; compare Table 1 with Figure 3.

Figure 3. Proposed CS2013’s ToC topics in the Strawman draft (layout edited). 100% of tier-1 and >80% of tier-2 is core and has to be covered, and an undefined amount of the elective topics to facilitate track-development (no tracks have been defined in the CS2013 draft yet).

Considering the Strawman’s “core” topics, one may question the feasibility of imparting a real understanding of complexity classes P and NP without also touching upon computability and Turing machines. Furthermore, the hours indicated in Figure 3 are meant as minimum hours of fact-to-face lectures (i.e., 8 lessons at a South African university, or at least almost 3 weeks of a standard 16 credit course), which, if this minimum is adhered to, amounts to a very superficial treatment of partial ToC topics. As an aside: my ToC students at UKZN now go through all of it (in accordance with the topics listed in the handbook). Comparing the ‘essentials’ list with the older curriculum guidelines [3, 4], however, one observes that they are much more in agreement.

Quite a bit has changed in the computing arena since the late 1980s, and most notably the specialization and diversification of the field. ToC matters more for CS than other recently recognised specialisations within computing—e.g., software engineering, net-centric computing, information systems, and computational biology—and this diversification is, or has to be, recognised by the curriculum developers [5, 6], which should result in putting more or less weight on the core topics (see [7] for a detailed analysis on sub-disciplines within computing and a proposed weighting of curriculum themes). But recall that the Strawman draft is about (different track within) CS only. The diversification and its effect on computing curricula is noticeable clearly only when one compares it with the Software Engineering curriculum guidelines [8]: these guidelines include only a little bit on finite state machines, grammars, and complexity and computability in the “Data structures and algorithms” and “Discrete structures II” themes. It may be the case that, in praxis, those degree programmes called “computer science” indeed do contain the more fundamental topics, such as ToC (and logic, formal methods etc.), and that other ‘tracks’ actually have been given different names already, hence, would have been filtered out unintentionally a priori in the data collection stage of the curriculum survey.

Concerning issues teaching ToC, on an absolute scale, that 56% faces issues with their ToC courses is substantial, and, conversely, it deserves a comparative analysis to uncover what it is that the other half does so as to not have such issues. Based on the comments in the survey and outside (follow-up emails with survey respondents), there are a few directions: it may help to demonstrate better the applicability of ToC topics in the students’ prospective career, have experienced good teachers, and appropriate preparation in prior courses to increase the pass rates. Further, having issues might be related to the quantity and depth of material covered in a ToC course with respect to nominal course load. The data hints also to another possible explanation: even with a 80-100% pass rate and no low enrolment the ‘gotten used to the issues’ was selected occasionally, and vv., with a 41-60% pass rate that everything runs smoothly, thereby indicating that having issues might also be relative to a particular university culture and expectations of students, academics, and management.

Answers to the questions

Looking again at the questions raised at the start, here are the (short) answers to them:

  1. How are ToC topics implemented in CS curricula around the world at present? ToC topics in the actual international curricula are more in line with the older curriculum guidelines of [3, 4] than the more recent versions that put less weight on ToC topics. The timing in the curriculum regarding when to teach ToC remains largely stable and for a majority is scheduled in the 2nd or 3rd year.
  2. Are there any country or regional differences? There are country/regional differences, the largest one being that ToC is taught at only 27% of the South African traditional and comprehensive universities versus at 84% of the consulted curricula elsewhere in the world. Even including those SA universities with partial ToC coverage does not make up for the differences with elsewhere in the world or any of the proposed CS curriculum guidelines. Other geographic or language-based differences are not deducible from the data, or: based on the data, region does not matter substantially regarding inclusion of ToC in the CS curriculum, except that the slight difference between Europe and the Anglo-Saxon countries deserves further attention.
  3. What is the sentiment around teaching ToC in academia that may influence the former? Opinion on ToC is overwhelmingly in favour of having it in the curriculum, and primarily in the 2nd or 3rd year. Also, a large list of topics is considered to be ‘essential’ to the course, and this list is substantially larger than the recent international curricula Strawman drafts’ core for ToC topics (and more like the Strawman drafts’ total ToC list). Despite noted issues with the course, the voices from the field clearly indicate that ToC is here to stay.

In closing (for now): ToC is solidly in the CS degree programme, and perhaps ought to be introduced more widely in South Africa. And just in case you think something along the line of “well, we have pressing issues to solve in South Africa and no time for follies like doodling DFAs and tinkering with Turing machines”: CS and development of novel and good quality software requires an understanding of ToC topics. For instance, to develop a correct isiZulu grammar checker for text processing software or a parser for natural language processing, scalable image pattern recognition algorithms to monitor wildlife tracks with pictures taken in situ in, say, the Kruger park, an ontology-driven user interface for the Department of Science & Technology’s National Recordal System for indigenous knowledge management, and proper data integration to harmonize and streamline service delivery management, to name but a few application scenarios. Foreigners will not do all this for you (and they have their own problems they want to solve), or only for large consulting fees that otherwise could have been used to, among others, install potable water for the 1.3 million South Africans that don’t have it now, provide them closed toilets, ARV etc.


[1] ACM/IEEE Joint Task Force on Computing Curricula. (2012). Computer Science Curricula 2013 Strawman Draft (Feb. 2012). ACM/IEEE.

[2] Keet, C.M. An Assessment of Theory of Computation in Computer Science Curricula. 21st Annual Meeting of the Southern African Association for Research in Mathematics, Science, and Technology Education (SAARMSTE’13). BellVille, South Africa, January 14-17, 2013.

[3] Denning, P.J., Comer, D.E., Gries, D., Mulder, M.C., Tucker, A., Turner, A.J. & Young, P.R. (1989) Computing as a discipline. Communications of the ACM, 32(1), 9-23.

[4] UNESCO-IFIP. (1994). A modular curriculum in computer science. UNESCO and IFIP report ED/94/WS/13. 112p.

[5] Sahimi, M., Roach, S., Cuadros-Vargas, E. & Reed, D. (2012). Computer Science curriculum 2013: reviewing the Strawman report from the ACM/IEEE Task Team. In: Proceedings of the 43rd ACM technical Symposium on Computer Science Education (pp. 3-4). Raleigh, North Carolina, USA, February 29 – March 3, 2012. New York: ACM Conference Proceedings.

[6] Rosenbloom, P.S. (2004). A new framework for computer science and engineering. IEEE Computer, 37(11), 23-28.

[7] ACM/IEEE Joint Task Force on Computing Curricula. (2005). The overview report. ACM, AIS, IEEE-CS, September 30, 2005.

[8] ACM/IEEE Joint Task Force on Computing Curricula. (2004). Software Engineering 2004. ACM, IEEE-CS, August 23, 2004.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.