tag:blogger.com,1999:blog-3722233.post1914804453534526701..comments2023-03-25T10:00:22.914-05:00Comments on Computational Complexity: What is more importantt: Automata Theory or Crypto?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-3722233.post-11871852316893860142010-02-24T19:17:54.675-06:002010-02-24T19:17:54.675-06:00It is somewhat of a pity that the students need to...It is somewhat of a pity that the students need to decide between crypto or automata. I think both courses are very important, useful and appealing. For me, automata theory was certainly one of the most enjoyable courses during my undergrad years (we did not have crypto courses).<br /><br />Just to keep things in perspective, automata and grammars are *very* useful notions. They play an important role in compilers, natural languages, comp bio, verification, etc. And this does not even take into account the structural appeal of the progression from finite automata all the way to turing machines.<br /><br />PiotrPiotrhttps://www.blogger.com/profile/13283386044289655376noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15889466563058552262010-02-23T09:33:11.744-06:002010-02-23T09:33:11.744-06:00Automata theory is fundamental to computing and is...Automata theory is fundamental to computing and is a very important research area. In my school, undergrads have to take a course on automata theory. In the grad scene, students have to choose either advanced algorithms and analysis, or theory of computation which includes the automata theory for a credit of 3 untis for their theory - one of the core courses required. Students can take crypto if they wish to either under the theoretical computer science specialization track or the security specialization track.Sosoukehttps://www.blogger.com/profile/01713191828079901839noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26227774519675117762010-02-23T09:18:11.619-06:002010-02-23T09:18:11.619-06:00Yeah, crypto is MUCH sexier than Automata.
"...Yeah, crypto is MUCH sexier than Automata.<br /><br />"Crack some exciting codes" vs "Blah blah blah computability, recursive sets, ZZZZZZZZZZZZZZ" is pretty much a no-brainer.<br /><br />"Research into parsing theory is an excellent way to gain obscurity" (David Dill, possibly apocryphal)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6947312712684251452010-02-23T02:46:21.735-06:002010-02-23T02:46:21.735-06:00I am not sure if the right question is asked here....I am not sure if the right question is asked here. I submit the students are NOT deciding which one is "more important", Crypto or Automata Theory.<br /><br />They are deciding which one sound more exciting or sound sexier an option to take. With general/technical blog from the likes of http://www.schneier.com/ there are a lot more CS students/"geeks" aware of Crypto topics (the good old DeCSS, etc) and would like to learn more.<br /><br />I am guessing here. So others' guesses may be as good or better than mine.Kemptonhttp://kempton.ideasrevolution.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70170405837808660502010-02-22T20:40:17.890-06:002010-02-22T20:40:17.890-06:00@rgrig
the right name is "Green web innovati...@rgrig<br /><br />the right name is "Green web innovation"Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8144009696523021852010-02-22T19:01:33.462-06:002010-02-22T19:01:33.462-06:00http://www.diamondbackonline.com/news/teaching-twe...http://www.diamondbackonline.com/news/teaching-tweeting-1.1167737Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23015308290812822792010-02-22T18:09:57.895-06:002010-02-22T18:09:57.895-06:00Why do students get to decide which of databases, ...Why do students get to decide which of databases, graphics, and artificial intelligence is more important at UM? At my school it was a "choice" between algorithms and compilers. There was no reason to take both. Why did we get to decide which was more important? Also, aren't most CS departments the trade school of the modern era anyway?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27108291343386730152010-02-22T17:37:09.716-06:002010-02-22T17:37:09.716-06:00As a first year undergrad course we had "Form...As a first year undergrad course we had "Formal languages and automata" course which covered regular languages, FSA, RE, context-free languages, PDA, turing machines, reductions, and PCP. It's somewhat watered down now, but still compulsory. At the end of their five year master's degree students tend to say they liked the course, but it used to be the case that less then 50% passed the course first year they took it.Jonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16791532234589480282010-02-22T16:59:51.426-06:002010-02-22T16:59:51.426-06:00Automata theory may not be a hot research area its...Automata theory may not be a hot research area itself, but it's certainly relevant for many other research areas. In natural language processing, for instance, a working knowledge of automata theory comes in very handy.Adam Lopezhttps://www.blogger.com/profile/17867208640531628374noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64446829277323534812010-02-22T14:39:13.791-06:002010-02-22T14:39:13.791-06:00It sounds like your students are getting the most ...It sounds like your students are getting the most important automata theory material in other courses, so their decision to take crypto sounds like a good one. The halting problem and undecidability are key concepts, so if they aren't currently exposed to those in another course perhaps they should be.<br /><br />I don't think the students are missing much in not learning about Turing machines. Turing machines were important historically, but these days they're rarely used (at least in STOC/FOCS/SODA community) since they're so awkward to program. The best reasons I see to pick Turing machines as the universal machine to teach (rather than e.g. a RAM model or even lambda calculus) are:<br />i. Needed for CS GREs, reading old papers, and other legacy uses<br />ii. The DFA, PDA, TM progression is cute.Unknownhttps://www.blogger.com/profile/01106301822827737278noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64942697956122348232010-02-22T13:47:46.254-06:002010-02-22T13:47:46.254-06:001) It is an ugrad course I am talking about.
2) N...1) It is an ugrad course I am talking about.<br /><br />2) Noam- Crypto is crosslisted<br />with Math. The Comp Sci students who take it have as prereq an alg course which has about 2 weeks of NPC. While more would help, this seems to be okay.<br /><br />3) Guil is CORRECT (he was a grad student here so he knows!) that we have a PL course with SOME of the material done<br />non-rigorously. (DFAs and<br />PDA's). That may make the need for Automata theory less.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74880095632239621832010-02-22T13:22:07.214-06:002010-02-22T13:22:07.214-06:00Since you mentioned that your automata course incl...Since you mentioned that your automata course includes also NP-completeness, I assume that your crypto course does NOT have NPC as a pre-requisite? Does that make sense?Unknownhttps://www.blogger.com/profile/03679302468810979223noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79141801898328108712010-02-22T12:46:56.031-06:002010-02-22T12:46:56.031-06:00Maryland covers a lot of regular languages and CFG...Maryland covers a lot of regular languages and CFG in Organization of Programming Languages (330). The students are not asked for formal proofs, but we show the algorithms to convert between NFA, DFA, RE, and RG. Also, NPC is normally covered in Algorithms (351). Both are compulsory classes. Unfortunately, I don't think important topics such as Turing Machines and Halting problem are covered in any compulsory class. I don't think PDA or pumping lemmas are very important. So, crypto may make sense...Guilhermehttps://www.blogger.com/profile/16356657960297015642noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7022050617742395332010-02-22T12:42:50.092-06:002010-02-22T12:42:50.092-06:00Anonymous Six is right. 'Theory' sounds sc...Anonymous Six is right. 'Theory' sounds scary. 'Web' is much more friendly. Call it Web Search.<br />(I'm half joking.)rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57192052244764297032010-02-22T11:50:44.607-06:002010-02-22T11:50:44.607-06:00In my school Crypto is optional, and there are two...In my school Crypto is optional, and there are two compulsory undergraduate courses that overlap with "Automata Theory":<br /><br />- Logic and Computability theory.<br />- Formal languages and intro. to compiler design.<br /><br />Basic Complexity theory is spread in two Algorithm courses.<br /><br />(Here in Argentina, it's a joint bachelor's and master's degree after five years.)Diegohttps://www.blogger.com/profile/09627662189360325919noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49525499338341469842010-02-22T11:22:32.708-06:002010-02-22T11:22:32.708-06:00Students need some amount on
* finite automata/reg...Students need some amount on<br />* finite automata/regular expressions <br />* basic undecidability <br />* NP-completeness (reductions but not proof of Cook-Levin)<br />and they probably should see what a CFG is at some point but PDAs, detailed grammar manipulations, and detailed computability theory are not so critical.<br /><br />Also, if you called the course something other than "Automata Theory" I think that you would get more students.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18708043330175762242010-02-22T11:21:24.758-06:002010-02-22T11:21:24.758-06:00You may need to market the automata theory course ...You may need to market the automata theory course more to the undergraduates. One selling point was I heard at Stanford their automata theory course was topping the scale on some sort of survey of "which courses turned out to be important to you some number of years after you graduated" survey. Another selling point (probably related) is that regexps, string matching, suffix trees are very important in web search.JohnMounthttps://www.blogger.com/profile/01471301836502765734noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70645366694020557372010-02-22T11:10:23.383-06:002010-02-22T11:10:23.383-06:00Addition and subtraction of natural numbers are no...Addition and subtraction of natural numbers are not important research areas, yet we teach every student in America these concepts. Point: "Active research area" and "Should take a class on it" are only sometimes related.<br /><br />I think automata theory should be taught just because it is so amazingly beautiful. Also, it makes a great introduction to proofs. Why don't they teach that in high school in place of calculus (which I found terribly boring)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13787215124940923862010-02-22T11:01:45.749-06:002010-02-22T11:01:45.749-06:00I do not think that automata theory is an importan...I do not think that automata theory is an important research area.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16621001028639984422010-02-22T10:49:13.199-06:002010-02-22T10:49:13.199-06:00Isn't automata theory kind of archaic already?...Isn't automata theory kind of archaic already? I notice a trend where Complexity/TCS texts seem to try to move away from it, and compiler courses seem to be self-sufficient nowadays.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85519954143398371222010-02-22T10:40:45.065-06:002010-02-22T10:40:45.065-06:00My school propose a course on Automata Theory for ...My school propose a course on Automata Theory for undergrads, which is pretty much compulsory*. Cryptography is proposed as a graduate course, and is not compulsory. I precise that it is in Europe, so undergrad/grad has not the exact same separation as in the US.<br /><br />* What I mean is that there are a few courses proposed for undergrads, and they need to take a big proportion of those courses. Therefore, Automata Theory is not compulsory but most student take it.B.noreply@blogger.com