I am in the process of reviewing
What can be computed: A Practical Guide to the Theory of Computation
by John MacCormick
and I need YOUR help for the first SENTENCE. I began by saying
This is a text book for a course on Formal Language Theory
but then I realized that this is not what we call the course at UMCP. Then I got to thinking: what do other schools call it? I have the following so far:
UMCP: Elementary Theory of Computation
Harvard: Introduction to Theory of Computation
MIT: Automata, Computability, and, Complexity
Clark: Automata Theory
(My spellcheck does not think Automata is a word. Also Computability. Usually I listen to my spellcheckers, but I checked and YES, I spelled them right.)
For some other schools I either hit a place I needed an account, or I just got titles without a description so I could not be sure.
This is where YOU come in!
Please leave comments with your school and the title of the course at your school that covers a reasonable overlap with: Regular Sets, Context Free Sets, Decidable and Undecidble and r.e. sets, P, NP, perhaps other complexity classes, and NP-completeness. Its FINE if your answer is one of the above ones, or one of the other comments--- I plan to later set this up as a pigeonhole principle problem.
I suspect that courses in algorithms are called Algorithms or Introduction to Algorithms.
I suspect that courses in cryptography are called Cryptography or Intro to Cryptography.
Why does the non-algorithm, non-crypto theory course have more names?
At Waterloo, we have two versions of this course: a regular version and an enriched version.
ReplyDeleteCS 360: Introduction to the Theory of Computing
CS 365: Models of Computation
At Technion CS this material is not contained in a single course. I recall a course at Tel-Aviv University called "Computational Models" a couple of decades ago, that covered about everything you mentioned.
ReplyDeleteAt Columbia it is called "Computer Science Theory". At UCLouvain (in Belgium) it is simply called "Calculabilité" ("Computability"). Both cover almost exactly the topics you list.
ReplyDelete
ReplyDeleteThe closest to what you're speaking of was, perhaps, the "Mathematical Logic and Theory of Algorithms" course, which started from Boolean Logic, first-order logic, predicate logic, Turing machines, lambda calculus, etc.
What school was this at?
DeleteMoscow Institute of Physics and Technology
DeleteAt Harvard this is called these days
ReplyDelete“Introduction to Theoretical Computer Science”
https://cs121.boazbarak.org/
Btw one reason for variations in the name is that there are variations in the material. I spend very little time on regular expressions and languages, and don’t cover context free at all, nor talk about recursively enumerable sets. Apart from the topics you mentioned (uncomputability, NP hardness and other complexity classes), I do spend a good amount of time on randomized computation (I.e. BPP), and also talk a little about crypto and quantum computing
ReplyDeleteReed College calls it "Computability and Complexity", and UCSD calls it "Theory of Computation".
ReplyDeletePortland State University - Computational Structures (https://www.pdx.edu/computer-science/cs311)
ReplyDeleteAt UIUC, the introductory course for these topics is bundled in with introductory algorithms in "Algorithms and Models of Computation". Most of the non-algorihtms stuff takes place in the last month and first month or so.
ReplyDeleteWhen I was an undergrad at Florida Tech, this class was called "Formal Languages and Automata Theory". At the time at least, it covered almost nothing about complexity theory (P, NP, etc.) - I think these were covered in a different course.
ReplyDeleteP.S. One more thing that I remember about this - having "automata" in the name of the course resulted in the highest concentration I had ever heard of people (myself included) mispronouncing the word "automata", since us students were reading from the course list and hadn't ever heard the correct pronunciation until we actually took the class. This resulted in some strange flashbacks for me upon the release of NieR: Automata.
DeleteUniversity of Bucharest: there is a course in the 2nd semester called 'Formal Languages and Automata' (with some Turing machines at the end) continued in the 3rd semester with the name 'Computability and Complexity' (covering the rest of what you said). (In the 1st semester there is a logic course called 'Mathematical and Computational Logic'.)
ReplyDeleteBtw the algorithms course is called there 'Algorithms and Data Structures', and at the Polytechnic University of Bucharest it's 'Data Structures and Algorithms', so even there, there isn't a canonical choice.
At TU Darmstadt, where I'm doing now a postdoc, the first course is called 'Formal Foundations of Computer Science I: Automata, Formal Languages and Decidability' and it's in the 1st semester. (The 2nd semester has part II, called 'Propositional and Predicate Logic'.)
Ah- not communative! So algorihtms courses:
DeleteAlgorithms
Algorithms and Data Structures
Data Strutures and Algorithms
Into to any of the above.
6 options, though perhaps for algorthms, cryptography, and whatever we want to call non-alg, non-crypto, we should not consider X and Intro to X as different names.
We call ours Theory of Computation. (It covers all those topics.)
ReplyDeleteAt University of California, Irvine, it's called "Formal Languages and Automata Theory".
ReplyDeleteAt University of Washington it is called "Introduction to Theory of Computation". Its focus is computability and complexity. The full regular languages part, context-free grammars as inductive definitions, and a quick look at the undecidability of the halting problem are covered in the first "Foundations" course along with logic and induction much earlier in the curriculum, right after the usual CS1/CS2 programming courses.
ReplyDeleteAt Caltech the course was "Decidability and Tractability"
ReplyDeleteAt Caltech, it's called "Decidability and Tractability". http://users.cms.caltech.edu/~umans/cs21/
ReplyDeleteSwarthmore's title is Theory of Computation.
ReplyDeleteAt the TUK in Germany our introduction course was called "Formal Basics of Programming", but was renamed recently to "Formal Languages and Computability". The more advanced courses on automata and complexity classes are called "Complexity Theory", "Verification of Reactive Systems" and "Advanced Automata Theory".
ReplyDeleteIn Germany, we call it simply "Informatik III" ;)
ReplyDeleteAt the University of Chicago, this area is split into two courses: "Introduction to Formal Languages" and "Introduction to Complexity Theory".
ReplyDeleteAt Carnegie Mellon our required non-algorithms theory course is "Great Ideas in Theoretical Computer Science", which covers everything from your list except context free grammars and recursively enumerable sets, as well as some material on randomized algorithms, approximation algorithms and cryptography, and a smattering of other topics that vary between semesters.
ReplyDeleteWe also have "Formal Languages, Automata, and Computability", which goes into more detail on automata and covers context free grammars and recursive enumerability, as well as "Undergraduate Complexity Theory", which goes into a lot more complexity classes.
At Princeton the ugrad non-algorithms class is COS 487 - Theory of Computation. The graduate complexity class is COS 522 - (sometimes Advanced) Complexity Theory.
ReplyDeleteHarvard -- Introduction to the Theory of Computation
ReplyDelete