In my

last blog post I asked my readers to leave comments saying what the name of the course that has some of Regular Languages, Context Free Languages Decideability, P, NP (any maybe other stuff) in it. I suspected there would be many different names and their were. I was able to put all but 6 into 4 equivalence classes. So that's 10 names. Thats a lot especially compared to

(Introduction to) Algorithms

and

(Introduction to) Cryptography

which I suspect have far fewer names. One commenter pointed out that the reason for the many different names is that there are many versions of the course. That's not quite an explanation since there are also many different versions of Cryptography---at UMCP crypto is cross listed in THREE departments (CS, Math, EE) and its taught by 6 or so different people who don't talk to each other (I am one of them). I think Algorithms is more uniform across colleges.

I think that terms Algorithms and Cryptography are both rather broad and can accommodate many versions of the courses, whereas no term seems to be agreed upon to encompass the DFA etc course.

Even saying DFA etc is not quite right since some of the courses spend little or even no time on DFA's.

Below is a list of all the names I got and some comments. Note that some schools appear twice since they have two courses along these lines.

-----------------------------------------

TITLE: (Introduction to) Theory of Computation:

Swarthmore: Theory of Computation

UCSD: Theory of Computation

Saint Michaels: Theory of Computation

Univ of Washington: Introduction to the Theory of Computation

Waterloo: Introduction to the Theory of Computing

COMMENT: Theory of Computation could have been the term that encompasses all of these courses. I speculate that it didn't catch on since it sounds too much like computability theory which is only one part of the course.

------------------------

TITLE: Formal Languages and XXX

CMU: Formal Languages, Automata, and Computability

Florida Tech: Formal Languages and Automata Theory

UC-Irvine: Formal Languages and Automata Theory

Univ of Chicago: Introduction to Formal Languages

University of Bucharest: Formal Language and Automata

TU Darmstadt: Formal Foundations of CS I: Automata, Formal Languages, and Decidability

TUK Germany: Formal Languages and Computability

COMMENT: The title makes it sound like they don't cover P and NP. I do not know if thats true; however, I speculate that, it could never be the encompassing term.

Spell Check things Automata and Computability are not words, but I've googled them and they seem to be words.

--------------------------

TITLE: Computability/Decidability and Complexity/Intractability

Reed College: Computability and Complexity

Caltech: Decidability and Intractability

COMMENT: The title makes it sound like they don't cover regular or context free languages. I do not know if that's true; however, I speculate that, since the terms sound that way, they never caught on as the general term.

Spellecheck thinks that neither Decidability nor Decideability is a word. Google seems to say that I should leave out the e, so I will.

------------------------------

TITLE: Blah MODELS Blah

Tel-Aviv (a long time ago) Computational Models

UIUC: Algorithms and Models of Computation (also has some algorithms in it)

Waterloo: Models of Computation (enriched version)

COMMENT: Models of Computation sounds like a good name for the course! Too bad it didn't catch on. It would also be able to withstand changes in the content like more on parallelism or more on communication complexity.

------------------------------

TITLE: MISC

CMU: Great Ideas in Theoretical Computer Science

UCLouvain (Belgium) Calculabilite (Computability)

Moscow Inst. of Phy. and Tech.: Mathematical logic and Theory of Algorithms

Portland State University: Computational Structures

Germany: Informatik III (Not all of Germany)

Univ of Chicago: Introduction to Complexity

COMMENT: All of these terms are to narrow to have served as a general term.