tag:blogger.com,1999:blog-3722233.post693865784966232415..comments2020-04-04T11:22:04.819-04:00Comments on Computational Complexity: What do you call your ugrad non-algorithms theory course?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger27125tag:blogger.com,1999:blog-3722233.post-91353101165587038832019-12-20T00:21:43.709-05:002019-12-20T00:21:43.709-05:00Harvard -- Introduction to the Theory of Computati...Harvard -- Introduction to the Theory of ComputationAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80484843859229701242019-12-15T18:39:33.598-05:002019-12-15T18:39:33.598-05:00At Princeton the ugrad non-algorithms class is COS...At Princeton the ugrad non-algorithms class is COS 487 - Theory of Computation. The graduate complexity class is COS 522 - (sometimes Advanced) Complexity Theory. Rahul Mehtahttps://www.blogger.com/profile/08358387698036669439noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57963385392450872502019-12-12T02:05:39.867-05:002019-12-12T02:05:39.867-05:00At Carnegie Mellon our required non-algorithms the...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.<br /><br />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.Calvinhttps://www.blogger.com/profile/04188732386555748518noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57418887411612444872019-12-10T21:43:46.506-05:002019-12-10T21:43:46.506-05:00Moscow Institute of Physics and TechnologyMoscow Institute of Physics and TechnologyAnonymoushttps://www.blogger.com/profile/11067659793463483481noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26701665584929825472019-12-10T17:44:42.667-05:002019-12-10T17:44:42.667-05:00At the University of Chicago, this area is split i...At the University of Chicago, this area is split into two courses: "Introduction to Formal Languages" and "Introduction to Complexity Theory".Elliottnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60566438828297464372019-12-10T07:33:37.133-05:002019-12-10T07:33:37.133-05:00In Germany, we call it simply "Informatik III...In Germany, we call it simply "Informatik III" ;)Hajdukhttp://rolandglueck.de/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14964247919194946792019-12-09T23:55:53.090-05:002019-12-09T23:55:53.090-05:00P.S. One more thing that I remember about this - h...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.Aaron Rotenberghttps://www.blogger.com/profile/04025704694247832990noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62446990866404853912019-12-09T15:46:38.093-05:002019-12-09T15:46:38.093-05:00At the TUK in Germany our introduction course was ...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".Michaelnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27866579367941883852019-12-09T13:13:11.449-05:002019-12-09T13:13:11.449-05:00Swarthmore's title is Theory of Computation.Swarthmore's title is Theory of Computation. Andyhttps://www.blogger.com/profile/15483688748769764445noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75741586505044930932019-12-09T11:47:22.500-05:002019-12-09T11:47:22.500-05:00At Caltech, it's called "Decidability and...At Caltech, it's called "Decidability and Tractability". http://users.cms.caltech.edu/~umans/cs21/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64554314061319480952019-12-09T11:41:07.230-05:002019-12-09T11:41:07.230-05:00Ah- not communative! So algorihtms courses:
Algori...Ah- not communative! So algorihtms courses:<br />Algorithms<br />Algorithms and Data Structures<br />Data Strutures and Algorithms<br />Into to any of the above.<br /><br />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.GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47560941777295793632019-12-09T11:38:50.542-05:002019-12-09T11:38:50.542-05:00What school was this at?What school was this at?GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60142794866805778562019-12-09T09:47:02.111-05:002019-12-09T09:47:02.111-05:00At Caltech the course was "Decidability and T...At Caltech the course was "Decidability and Tractability"Benhttps://www.blogger.com/profile/10262657220474004642noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49626861799598426962019-12-09T09:41:25.662-05:002019-12-09T09:41:25.662-05:00At University of Washington it is called "Int...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. Paul Beamehttp://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11836158397740371552019-12-09T09:17:35.642-05:002019-12-09T09:17:35.642-05:00At University of California, Irvine, it's call...At University of California, Irvine, it's called "Formal Languages and Automata Theory".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42465336083538680802019-12-09T06:47:37.784-05:002019-12-09T06:47:37.784-05:00We call ours Theory of Computation. (It covers al...We call ours Theory of Computation. (It covers all those topics.)Jim Hefferonhttps://www.blogger.com/profile/09292836035665054384noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7157906428516642572019-12-09T05:34:57.019-05:002019-12-09T05:34:57.019-05:00University of Bucharest: there is a course in the ...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'.)<br /><br />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.<br /><br />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'.)Andreihttps://www.blogger.com/profile/02656015432967049103noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6790308326895585992019-12-09T03:14:46.970-05:002019-12-09T03:14:46.970-05:00When I was an undergrad at Florida Tech, this clas...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.Aaron Rotenberghttps://www.blogger.com/profile/04025704694247832990noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28669136809475248862019-12-09T02:52:15.724-05:002019-12-09T02:52:15.724-05:00At UIUC, the introductory course for these topics ...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.Nathanhttps://www.blogger.com/profile/17010149544829211595noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24418503616366062862019-12-09T02:07:11.416-05:002019-12-09T02:07:11.416-05:00Portland State University - Computational Structur...Portland State University - Computational Structures (https://www.pdx.edu/computer-science/cs311)Zachnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38708052938273064502019-12-09T01:38:35.950-05:002019-12-09T01:38:35.950-05:00Reed College calls it "Computability and Comp...Reed College calls it "Computability and Complexity", and UCSD calls it "Theory of Computation". Markhttps://www.blogger.com/profile/17563688458495404020noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90167045238096263352019-12-09T01:14:13.554-05:002019-12-09T01:14:13.554-05:00Btw one reason for variations in the name is that ...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 Boaz Barakhttps://www.blogger.com/profile/01023091208435407661noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69352697029139515452019-12-09T01:07:06.592-05:002019-12-09T01:07:06.592-05:00At Harvard this is called these days
“Introducti...At Harvard this is called these days <br /><br />“Introduction to Theoretical Computer Science”<br /><br />https://cs121.boazbarak.org/Boaz Barakhttps://www.blogger.com/profile/01023091208435407661noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6043982226627784612019-12-09T00:44:51.351-05:002019-12-09T00:44:51.351-05:00The closest to what you're speaking of was, pe...<br />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.Anonymoushttps://www.blogger.com/profile/11067659793463483481noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75855726611105696432019-12-09T00:09:29.694-05:002019-12-09T00:09:29.694-05:00At Columbia it is called "Computer Science Th...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.Anonymoushttps://www.blogger.com/profile/10453516411390753222noreply@blogger.com