(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.
Models of Computation sounds like you spend a whole semester talking about stuff like Wang tiles and membrane computing.
ReplyDeleteI would have absolutely taken that course as an elective if it existed.
DeleteTo me, Models of Computation sound more like what "Structure and Interpretation of Computer Programs" is about. I.e. lazy vs eager evaluation, prolog, language design, circuit design, etc...
ReplyDeleteThe problem with cryptography is that there are at least two cryptographies.
ReplyDeleteOne is about one-way functions and random number generators; the other one is about RSA and CBC cyphers.
Why is “Great Ideas in Theoretical Computer Science?” too narrow?
ReplyDeleteAt Harvard I changed the name of the course from “Introduction to the theory of computing” to “introduction to theoretical computer science” because I thought the latter term is broader and hints at topics such as cryptography, randomness in computation, and quantum computing that intersect with computational complexity but are not a subset of it.
Good Point.
DeleteActually `Great ideas' sounds like a Great course, but is to wide a name to be a good universal name for a DFA and/or CFG and/or... course I am talking about.
On a related note: the ACT of SIGACT *used* to stand for "Automata and Computability Theory" and now stands for "Algorithms and Computation Theory".
ReplyDeleteThe different titles are really a function of the starting point and content for the course (as well as inertia) not some lack of consensus on what to call the same material.
Some of the big differences:
- Does the course have a large focus on finite state machines/grammars/PDAs, along with computability?
If so, you will tend to have the "formal languages/automata" or MAYBE "theory of computation", but maybe only if the course extends into complexity.
- Does the course have a significant focus on computability?
If so, "Theory of Computing/Computation Theory/Theory of Computation" seem appropriate.
- Course titles like "Great Ideas in TCS" and "Intro to Theoretical Computer Science" suggest that the material covers substantial algorithmic content as well. The idea is fine, but I think it is another apples and oranges comparison.
Just posed this question to a coworker who went to UCF. Apparently these topics are spread out among the "Discrete Structures" (discrete math) ugrad courses there, with most of it concentrated in Discrete Structures II. That's about as informative a course title as "Informatik III", if not less so.
ReplyDeleteMy coworker texted me later to mention that the two Discrete Structures courses are commonly referred to by the student body as "Little Discrete" and "Big Discrete".
DeleteBill, I doubt that Informatak is a term. please check and get back to me. did you mean informatik ? If so, make correction.
ReplyDeleteWas a your spell-checker that turned Calculabilité (perfectly good French) into Calulabitite (huh?)? What algorithm was it using?
ReplyDeleteThe algorithm was `me copying a comment from the last post' which is, as evidenced from your correction and the last comment, not a prefect algorithm. I have fixed it.
Delete