tag:blogger.com,1999:blog-3722233.post4205548308961867059..comments2020-05-31T01:14:25.681-04:00Comments on Computational Complexity: What is in MY automata theory course/What should beLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-3722233.post-68119974605895519042016-06-30T16:39:32.756-04:002016-06-30T16:39:32.756-04:00I've had the opportunity to TA several differe...I've had the opportunity to TA several different flavors of this course. Three of these courses were undergraduate level classes using Savage, Sudkamp, and Ullman-Hopcroft respectively. The last was a mixed undergrad/grad course using Sipser. It's given me a lot to chew on in terms of what I think is important, and I got to play around with some of this as the instructor for Automata Theory this summer. <br /><br />I think this subject is too deep to be confined to a one-semester course. It should be a two-semester sequence. I would use Savage the first semester to cover circuits, FSMs, a minimal exposition on PDAs, and TMs and Computability. Savage does a really good job in providing a perspective, and I like his proof of Cook-Levin in showing TMs and Circuits are logspace equivalent. CIRCUIT-SAT is a better first NP-Complete language than the standard SAT problem. Savage also provides exposition into the RAM model, which other standard texts omit; and he does a good job mentioning some algebra. It's a healthy perspective for someone going onto grad school to have. <br /><br />I would emphasize group theory and group actions, algebraic combinatorics, and complexity in the second semester (with Arora-Barak and Dummit & Foote as the texts). Algebra comes up enough in TCS (Babai's recent result on graph isomorphism, rings and fields in crypto) where it should be a staple in an undergraduate curriculum, rather than an obscurity for Math-CS double majors and grad school. Additionally, it provides a lot of solid relations to the discrete math prerequisites. Regular languages have a similar algebraic structure to the integers and are closely related to ordinary generating functions. I also like to teach the Brzozowski Algebraic Method and Brzozowski Derivatives instead of the State Reduction procedure, which provides a nice relation to solving recurrences with OGFs and walks on graphs. <br />Michael Levethttps://twitter.com/Michael_Levetnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75254505272127117992010-02-25T14:53:42.308-05:002010-02-25T14:53:42.308-05:00I think a big interest in automata these days are ...I think a big interest in automata these days are in the area of group theory -- namely, automatic groups. Your course description seems not touch this topic. On the other hand any modern course on automata should spend substantial time on this topic.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27955758665381565622010-02-25T12:07:09.222-05:002010-02-25T12:07:09.222-05:00Bill,
I often teach formal language theory, but h...Bill,<br /><br />I often teach formal language theory, but have just 27 lectures since Chicago is a quarter school. I have the students buy Kozen, but I supplement from Durbin, Eddy, Krogh, and Mitchison "Biological Sequence Analysis," Lindenmayer's "The Algorithmic Beauty of Plants," and from the 1st edition of Hopcroft and Ullman.<br /><br />I teach DFA minimization, because it enables me to talk about homomorphisms of DFAs, and my students find this helpful. I also talk about probabilistic automata as language generators, and do the standard biological sequence alignment algorithm as an application, and touch on Viterbi's algorithm.<br /><br />In terms of context free languages, I talk about weighted grammars (which makes it possible to adapt the CYK algorithm to RNA secondary structure prediction) and about Lindenmayer systems (which can be thought of as "parallel" CFLs, and have applications to computer graphics). I also teach LR(1) parsing. I think this is helpful for students who are going to take a compilers course later.<br /><br />I don't teach NP completeness, which it seems to me is better left to the algorithms course (for Cook's Theorem and the standard Karp 6), and to Razborov's complexity theory course for anything beyond that.<br /><br />I can usually squeeze in a lecture or two on general computability: time enough to introduce Turing Machines, the Kleene mu-calculus, the Lambda calculus, and a quick handwave of a proof that all three systems define the same set of computable number theoretic functions. We haven't had a general computability theory course in years :-(. If students want to learn the recursion theorem, they have to learn it from Soare.stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69463108980518625282010-02-25T10:01:39.703-05:002010-02-25T10:01:39.703-05:00Last Anon: Actually this is the first time I'v...Last Anon: Actually this is the first time I've taught it for a while, so your comments may be PREDICTIVE rather than<br />analysing the past. Also, I will modify the course as it goes, note what works and doesn't work for next time.<br /><br />Also- as my next post will show- the<br />course was far more popular this semester.<br />Why was that? Read it and find out.<br />(The reasons DO NOT contradict your obeservations.)GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86626108589898714862010-02-25T09:03:23.035-05:002010-02-25T09:03:23.035-05:00A problem with this course (and a possible reasons...A problem with this course (and a possible reasons students prefer crypto to this course) is that it seems to be trying to be many things at once:<br />(1) Introduction to basic theory of computer science (computability, halting, Turing machines)<br />(2) Theoretical basics that also have applications elsewhere (automata, regular expressions, grammars, NPC, etc.)<br />(3) Random "gems"(?) of theoretical computer science (all the other stuff you mentioned)<br /><br />It sounds like, at Maryland, (2) is sufficiently covered in other courses -- at least to the extent that doing it formally would not require a whole additional semester. Topic (1) is very important, but also not enough to fill a semester. So you pad the semester with (3), and I can imagine that some students do not like that.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87576818443618841822010-02-24T20:30:22.178-05:002010-02-24T20:30:22.178-05:00Hi Bill,
I think that adding one or two lecture...Hi Bill,<br /><br /> I think that adding one or two lectures along the lines of "automata/grammars in real life" could increase the appeal of the course. Some examples (some of which might require extensions to probabilistic grammars or automata, which might be interesting on their own):<br /><br />- comp bio: RNA folding<br />- verification: reachability of "bad" states<br />- graphics: generating fractal-like images<br /><br />EtcPiotrhttps://www.blogger.com/profile/13283386044289655376noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4125005084453533992010-02-24T16:24:15.115-05:002010-02-24T16:24:15.115-05:00Hi Bill --
This term I'm teaching both our un...Hi Bill --<br /><br />This term I'm teaching both our undergraduate and graduate automata-computability-complexity courses, except that the <a href="http://www.cs.umass.edu/~barring/cs601" rel="nofollow">grad course</a> is now all complexity, using Arora-Barak chapters 1-10 and 14. The <a href="http://www.cs.umass.edu/~barring/cs401" rel="nofollow">undergrad course </a>, using Sipser, is a third each finite-automata-and-CFL's, computability, and complexity. In both courses I go easy on practical NP-completeness, as that is covered in our undergrad and grad algorithms courses.<br /><br />I do DFA minimization in the undergrad course because it's cool, the students like it, and it illustrates Myhill-Nerode. (I do a whole lecture on MN whereas Sipser relegates it to a solved exercise.) I roughly agree with you about proving obvious things and programming TM's apart from one or two exercises. I do talk about space complexity a fair bit and (given that I am at UMass especially) do Immerman-Szelepcseyni in both courses. Not much logic, though -- in the grad course I mention descriptive complexity characterizations and use logic to explain nondeterminism and alternation. I agree about NON-ISO in AM in both courses -- I don't think I have time for any real ZK. I think I'll do the VC result in the undergrad course, but not the grad course because they are getting most of their NPC stuff elsewhere.<br /><br />Right now the undergrad course is optional for the degree though it's taken by most math-CS double majors. The grad course is required for Ph.D candidacy along with a grad algorithms course. Undergrad algorithms comes before this undergrad course, and is required for the degree. (For the BS, that is, we're also starting a BA which allows any five upper-levels.)<br /><br />More than you wanted to know, perhaps...DaveMBhttp://www.cs.umass.edu/~barringnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5799445032379568632010-02-24T13:23:09.839-05:002010-02-24T13:23:09.839-05:00... but we could have videos from many lecturers a...... but we could have videos from many lecturers and then let the crowd decide.<br /><br />Plus, it may be the case that one lecturer is quite strong on a particular topic but weaker on another. By having a larger collection of videos, there would be strong lectures on everything.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30382404595092407282010-02-24T00:45:58.914-05:002010-02-24T00:45:58.914-05:00Rani: Fix k. Form the following tree:
take an edge...Rani: Fix k. Form the following tree:<br />take an edge. ONE of the two vertices<br />that forms it must be in the VC.<br />So branch both ways, taking either<br />choice. Delete that vertex. Then repeat<br />this on each child. Keep doing this until you form a tree of depth k and size of course about 2^k. If any of the leaves is the empty graph then you have a VC of size k.<br /><br />Anon who wonders if I am being a hypocrite. what are you talking about? I listed what is in my course in my post. You may agree or disagree with my choice of topics but I don't see what there is here to be hypocritical about.<br /><br />Anon who wants my course on video.<br />Good idea that an EXCELLENT lecturer should do that. Not clear that that person should be me<br />(some would say its clear that person should NOT be me.)<br /><br />bill gasarchGASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44937733624880685242010-02-23T23:50:52.636-05:002010-02-23T23:50:52.636-05:00This is somewhat off topic, but I would recommend ...This is somewhat off topic, but I would recommend that if you could create a video lecture of your course and put it on the web like MIT does, that that would be a great way of getting more people interested in theory. Right now, there are not many *introductory* video lectures in CS Theory that young people can look at, and get excited about.<br /><br />I work in a corporate research lab, and I recently pointed a new colleague (he has a Ph.D. in Psychology and will work in the area of HCI) to MIT's algorithms course and I have never seen someone so excited about Algorithms before :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45198894880600752092010-02-23T18:59:35.477-05:002010-02-23T18:59:35.477-05:00Is this another exercise in hypocrisy, like Lipton...Is this another exercise in hypocrisy, like Lipton's complexity course at Georgia Tech which covers almost nothing from his high flying list of topics:<br /><br />http://rjlipton.wordpress.com/2010/01/12/a-course-on-complexity-theorem/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90240112724545658692010-02-23T18:56:34.499-05:002010-02-23T18:56:34.499-05:00About FPT-VC:
Papadimitrious-Yannakis takes $n * 3...About FPT-VC:<br />Papadimitrious-Yannakis takes $n * 3^k$, using maximal (not necessarily maximum) matchings.<br />What algorithm takes $n^2 * f(k)$?Unknownhttps://www.blogger.com/profile/04752384695446260553noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54198779872864195502010-02-23T18:54:42.899-05:002010-02-23T18:54:42.899-05:00In fact I once "programmed" a pushdown a...In fact I once "programmed" a pushdown automaton for actual research - I needed to show that a regular expression with squaring has a small context free grammar for the language (it also has a regular expression without squaring, but not a small one). Not a hard exercise actually.Eldarnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55486940812663523192010-02-23T16:16:09.872-05:002010-02-23T16:16:09.872-05:00What I think such a class should not be: spending ...What I think such a class should not be: spending lots of time with lots of pretty animations learning how to program Turing machines to perform simple string-matching and arithmetic tasks. The ability to program a Turing machine is almost completely useless. For similar reasons, if pushdown automata are mentioned at all they should be covered only very briefly — in the guise of LALR and LL parsers, they are useful, but not as something anyone needs to learn to actually program by hand.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30986363861591755772010-02-23T15:24:59.139-05:002010-02-23T15:24:59.139-05:00The course is usually 15 weeks (twice a week for
7...The course is usually 15 weeks (twice a week for<br />75 minutes each meeting).<br />This year it is 14 weeks because of the snow.<br /><br />I may rethink mininizing DFA's the next time I do the course. THANKS to all for making me rethink this.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23035845160462523662010-02-23T13:43:40.628-05:002010-02-23T13:43:40.628-05:00When you say "a course" you mean a 10-we...When you say "a course" you mean a 10-week course (a quarter) or a 16-week course (a semester)? There's a lot you can include in 6 weeks difference -like an algorithm for minimizing DFA, or, say, ambiguity in CFGs- without over-stressing the students. I studied both in my semester-long automata theory course, though I think the teacher went too far near the end, trying to make us multiply integers using lambda-calculus in the final exam.Janomahttps://www.blogger.com/profile/08125807104571129259noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5462947587319948362010-02-23T13:36:17.708-05:002010-02-23T13:36:17.708-05:00I'm scheduled to teach our undergraduate autom...I'm scheduled to teach our undergraduate automata theory course next year so this is of some interest to me. But I think algorithms for minimizing DFAs (and for testing nonemptiness of regular languages, etc) are actually somewhat important: for instance, they came up yesterday for me in a research meeting with some social scientists as something they should probably be using.<br /><br />That doesn't mean I think we should all switch to doing new research on these problems, but what we want to tell the undergrads about and what we want to research can be two different things.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42603372130000154672010-02-23T13:35:00.878-05:002010-02-23T13:35:00.878-05:00I took a computation course in undergrad from Sips...I took a computation course in undergrad from Sipser who used his book. It excluded this<br />http://en.wikipedia.org/wiki/Myhill-Nerode_theorem<br />but I later wished it were covered, it's pretty cool. Even if you don't like the minimizing algorithm, it is enough to state this theorem and then handwave that it yields a minimizing algorithm. The reason I like it is that it gives an alternate characterization of regularity... alternate characterizations are good :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72721997075872237402010-02-23T11:06:09.259-05:002010-02-23T11:06:09.259-05:00Having been a teaching assistant for similar cours...Having been a teaching assistant for similar courses, I think it's worth having students "program" at least a couple simple TMs. <br /><br />This is especially true if you're presenting non-determinism as "an accepting computation path existing" (as opposed to there existing some string that satisfies a deterministic verifier, which I think is Sipser's presentation.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62509224486065300502010-02-23T10:38:15.276-05:002010-02-23T10:38:15.276-05:00I think some of the logic stuff you mention as top...I think some of the logic stuff you mention as topic 1) is presented in Dexter Kozen's book "Theory of Computation". Or maybe I'm misremembering things.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8057158345223107662010-02-23T10:19:50.082-05:002010-02-23T10:19:50.082-05:00I really like the theory of primitive recursive fu...I really like the theory of primitive recursive function, and I do think that the proof, for example, that Ackermann-Péter function is not primitive recursive is a nice proof that is worth knowing.<br /><br />But as you said, you cannot teach everything!B.noreply@blogger.com