Preliminary results of the Theory of Computation survey

As you may remember from the post on making Theory of Computation (ToC) more lively, I taught ToC for the first time last year at UKZN, where it also was a new core course in the CS degree programme, i.e., the students and the system also had to get used to ToC. As usual, anything can be improved upon (if you think not: look harder; they always can, at least in theory). To commence with that in a solid way, we’ve decided first to collect some data to go beyond the familiar anecdotes.

Internationally, many stories make the rounds through the grapevine about ToC. Those stories revolve around, among others, it being a difficult subject for the students, low pass rates, the course being threatened from being removed from a the programme, and textbooks becoming out of print (e.g., Pearson does not want to make reprints of Hopcropft, Mottwani & Ullman’s book unless they get single orders for more than 300 books, according to their rep for SA).

While the individual stories are true, how prevalent are they really?  How widespread are ‘low pass rates’, and when is it ‘low’? What are the enrollment numbers elsewhere? Do they have problems in the university system? It being a new course in the programme here as a result of merging a 16 credit Formal Languages & Automata Theory and a 16 credit Algorithms & Complexity, what topics are really essential in a ToC course? Should it be a core course, and if so, in which year of the programme?

These are some of the questions we were curious about as to what the answers would be. To find out, there’s a (still ongoing) survey of ToC syllabi at the various universities around the world and an opinion-survey to obtain data that cannot be found by just looking at syllabi, but concern the context around ToC, like enrollment numbers, pass rates, whether it should be in the programme vs. actually in the programme, and so on. The opinion-survey was open from 16 March to 1 April (accessible here), and I’ve put the preliminary results online, as promised in the announcement. (A paper summarizing the results and integrating it with the results of the syllabi-survey is in the pipeline, but somehow it struck a chord, and relatively many survey respondents wanted to know the results and all the details can’t go in the page-limited paper anyway).

In total, there were 77 people—mainly academics—who completed the survey, mostly from outside SA and covering all continents of the world. There’s the survey setup, results in digested format, discussion, and conclusions, as well as the raw data with aggregated numbers by question answer, and the list of ToC topics ordered by being essential. In short: The survey responses show an overwhelming agreement that ToC should be taught and a majority prefers to have it in the 2nd or 3rd year in an undergraduate programme. It is taught at most of the institutions that the respondents are affiliated with, and the course is mostly solidly in the programme as a core course. About half of the respondents note there are issues with the course, for various reasons, including, but not limited to, low pass rates and low enrollment. Roughly half observe first-time pass rates below 60%, and for only 20% the pass rate exceeds 80%. Whilst noting that several respondent spread ToC content over more than one course or integrate it with other courses, there is agreement on the typical topics that are considered as essential to ToC, covering regular and context-free languages (and grammars), automata (at least DFA, NFA, epsilon-NFA), Turing machines, undecidability, computability and complexity, where the subtopics covered vary a bit.

Several respondents also gave additional feedback and opinion via email. In case you would like so, too, drop me a line, or add it in the comments section here on the blog.

Advertisement