Sunday, December 08, 2019

What do you call your ugrad non-algorithms theory course?

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?






27 comments:

  1. At Waterloo, we have two versions of this course: a regular version and an enriched version.

    CS 360: Introduction to the Theory of Computing
    CS 365: Models of Computation

    ReplyDelete
  2. 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.

    ReplyDelete
  3. At 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

  4. The 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.

    ReplyDelete
  5. At Harvard this is called these days

    “Introduction to Theoretical Computer Science”

    https://cs121.boazbarak.org/

    ReplyDelete
  6. 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

    ReplyDelete
  7. Reed College calls it "Computability and Complexity", and UCSD calls it "Theory of Computation".

    ReplyDelete
  8. Portland State University - Computational Structures (https://www.pdx.edu/computer-science/cs311)

    ReplyDelete
  9. At 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.

    ReplyDelete
  10. When 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.

    ReplyDelete
    Replies
    1. P.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.

      Delete
  11. University 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'.)

    Btw 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'.)

    ReplyDelete
    Replies
    1. Ah- not communative! So algorihtms courses:
      Algorithms
      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.

      Delete
  12. We call ours Theory of Computation. (It covers all those topics.)

    ReplyDelete
  13. At University of California, Irvine, it's called "Formal Languages and Automata Theory".

    ReplyDelete
  14. At 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.

    ReplyDelete
  15. At Caltech the course was "Decidability and Tractability"

    ReplyDelete
  16. At Caltech, it's called "Decidability and Tractability". http://users.cms.caltech.edu/~umans/cs21/

    ReplyDelete
  17. Swarthmore's title is Theory of Computation.

    ReplyDelete
  18. At 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".

    ReplyDelete
  19. In Germany, we call it simply "Informatik III" ;)

    ReplyDelete
  20. At the University of Chicago, this area is split into two courses: "Introduction to Formal Languages" and "Introduction to Complexity Theory".

    ReplyDelete
  21. At 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.

    We 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.

    ReplyDelete
  22. At Princeton the ugrad non-algorithms class is COS 487 - Theory of Computation. The graduate complexity class is COS 522 - (sometimes Advanced) Complexity Theory.

    ReplyDelete
  23. Harvard -- Introduction to the Theory of Computation

    ReplyDelete