tag:blogger.com,1999:blog-3722233.post8874083265173166722..comments2023-03-20T03:45:56.651-05:00Comments on Computational Complexity: What should be in an automata course: Two views based on recent experienceLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-51796836480786193312010-05-22T19:02:28.638-05:002010-05-22T19:02:28.638-05:00Bill,
I took automata from Elaine Rich while she ...Bill,<br /><br />I took automata from Elaine Rich while she was writing her textbook on the subject. There's an about 150 page appendix of applications at the back of the book. I'd recommend checking that out for some ideas.Gilberthttps://www.blogger.com/profile/12848246894741812189noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70327522601441193562010-05-21T18:03:23.869-05:002010-05-21T18:03:23.869-05:00We have a similar second year course, but it seems...We have a similar second year course, but it seems that sometimes some students pass those courses while they still can't write rigorous proofs, and therefore fail automata & complexity course. But I guess we can't do much about this. Thank you both for the your responses, and the posts about the course.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33485188648378819052010-05-21T15:31:26.947-05:002010-05-21T15:31:26.947-05:00Anonymouses : Like Bill says above, this is a seni...Anonymouses : Like Bill says above, this is a senior level course, so the students typically are aware of proving techniques. <br /><br />Moreover, I do not wish to eliminate all obvious looking proofs. For example, when teaching DFA's next, I would teach the closure properties rigorously. Similarly for DFA = NFA. But I think the proof that Regular Expressions are equivalent can be omitted, I would just give an outline and have the students read through the details. Once you have the outline, the details can be worked out and they are not so instructive. I think Bill would agree with this too.subrukhttp://www.cc.gatech.edu/~subruknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74606008627029131382010-05-21T09:35:01.937-05:002010-05-21T09:35:01.937-05:00At UMCP there is a Discrete Math course they take ...At UMCP there is a Discrete Math course they take in their sophmore year BEFORE taking automata theory or algorithms which is supposed to teach them how to prove things.<br /><br />I've taught the course several times myself.<br /><br />It works some.<br />I"ll post on that next time I teach it.GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56757985193250429072010-05-21T03:03:13.700-05:002010-05-21T03:03:13.700-05:00I agree with the anonymous above. But I am not sur...I agree with the anonymous above. But I am not sure what is the best way to teach students to be rigorous. I have developed this skill by writing proofs and getting feedback on them. I am not sure that a lecture is a good place to teach these, or if this course is appropriate. In an ideal world, one would expect a student to have developed these skills by 3rd year, but we are not living in such a world. <br /><br />Any suggestions one this?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31824068430672628622010-05-20T22:29:55.284-05:002010-05-20T22:29:55.284-05:00I didn't do proofs of obvious things.
I think...<em>I didn't do proofs of obvious things.</em><br /><br />I think you lose something here. There is some value in teaching students to think and write formally. Yes, the proofs can sometimes get boring, but you will be amazed how many students in your class could not write (a proof sketch for) an obvious statement.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-482446562735419432010-05-20T09:30:08.773-05:002010-05-20T09:30:08.773-05:00I (Bill) alos did indeed cover Pumping Lemmas for ...I (Bill) alos did indeed cover Pumping Lemmas for REG and CFL. The reason that the post seems like its topics in complexity is because we discussed the<br />EXTRA topics we did, not the standard ones.<br /><br />We both did the standard topics <br />(DFA,NDFA, REG EXP, Pumping, CFL, PDA,<br />Pumping, Computable, c.e. sets, Cooks theorem, reductions).GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-587536808945083332010-05-20T00:21:13.578-05:002010-05-20T00:21:13.578-05:00Mitch & Anonymouses : The class I taught was c...Mitch & Anonymouses : The class I taught was called 'Automata and Complexity'.<br /><br />And I did talk about Pumping Lemma for Regular and Context Free Languages, in detail. Just thought it was too obvious to mention. I only wanted to mention where I possibly deviated from a standard class.subrukhttp://www.cc.gatech.edu/~subruknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36552012645033531392010-05-19T20:50:09.880-05:002010-05-19T20:50:09.880-05:00CS 4510, Automata and Complexity
title seems to c...CS 4510, Automata and Complexity<br /><br />title seems to cover any combination of both or eitherAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33047295769874555272010-05-19T20:48:41.091-05:002010-05-19T20:48:41.091-05:00CMSC452 Elementary Theory of Computation
seems ni...CMSC452 Elementary Theory of Computation<br /><br />seems nice and vague enough for almost anythingAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7056645365959683752010-05-19T20:25:03.811-05:002010-05-19T20:25:03.811-05:00I second Mitch's first comment. The topics see...I second Mitch's first comment. The topics seem to me to be more suitable for a complexity course than an automata course. The title of the course may need a change.<br /><br />In an automata theory course, I would follow more or less Hopcroft-Ullman (Motwani) ( I prefer the previous edition) with some updates. I am also a bit surprised to hear that neither of you had pumping, Ogden, ... in an automata theory course.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83915882696701921812010-05-19T13:14:58.109-05:002010-05-19T13:14:58.109-05:00- the topics you're suggesting really sound li...- the topics you're suggesting really sound like they would be part of a computational complexity syllabus rather than an automata class.<br /><br />- for 'natural' problems that cover both automata -and- complexity -and- are known not to be in P, how about regular expression equivalence (when you have extra operators like squaring or complement).<br /><br />- if you don't care about 'known to be in P' how about 'QSAT is PSPACE complete'? I consider that natural.Mitchhttps://www.blogger.com/profile/06352106235527027461noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17985746702597593722010-05-19T13:09:47.661-05:002010-05-19T13:09:47.661-05:00Nowadays, to do any serious systems engineering, i...Nowadays, to do any serious systems engineering, it seems like one needs a whole <a href="http://faculty.washington.edu/sidles/misc/QSE_syllabus.png" rel="nofollow">stack of graduate-level textbooks</a>.<br /><br />Our QSE Group is trying trying to compress this stack using the idea of <i>naturality</i>. For younger systems engineers this is a matter of professional survival ... students can't afford to spend seven years in graduate school!<br /><br />So, if an automata class were organized around the idea of "naturality", which of the (many) automata-related concepts/theorems mentioned in the post would be most central?<br /><br />And, how might one link these concepts together "naturally", to help speed student understanding, both in the narrow context of computational complexity, and perhaps in the broader context of naturality-driven systems engineering?John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70084139187833903372010-05-19T11:35:37.111-05:002010-05-19T11:35:37.111-05:00Dave : When I talked about Sigma_2, I gave the exa...Dave : When I talked about Sigma_2, I gave the example of smallest equivalent formula. But yet it was hard to sustain interest. I was aware of the survey, but might have picked a wrong example. As PH was what I considered an optional topic, I decided to not cover it.<br /><br />Gilbert : When I was doing the CYK algorithm for CFG's, I mentioned that a compiler would have to parse and recognize the syntax of a programming languages and so understanding the structure in an efficient manner is important. While doing P vs NP, I mentioned that P represents the notion of efficient problems. Similarly, talked about why space efficiency is important. Like Bill Gasarch says, this was mostly lip service and not real applications.subrukhttp://www.cc.gatech.edu/~subruknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29624495288305290562010-05-19T11:16:46.651-05:002010-05-19T11:16:46.651-05:00Gilbert- good question. I (Bill) Mentioned compile...Gilbert- good question. I (Bill) Mentioned compiler applications and that reg exp are used in grep, and I did talk about Minimization of automata.<br />However, I would say no, not much on applications. Some lip service.<br /><br />There is a required PL class that does some of that, and a non-required compiler design course. However, if you have som <br />suggestions I would love to hear them.<br />(comment on this blog).GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34543083330520925042010-05-19T10:42:28.252-05:002010-05-19T10:42:28.252-05:00Did either of you do any applications for non-theo...Did either of you do any applications for non-theoreticians?Gilberthttps://www.blogger.com/profile/12848246894741812189noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22420099980858154712010-05-19T10:35:38.237-05:002010-05-19T10:35:38.237-05:00Dave Doty: THANKS for the pointer!
Some of the pro...Dave Doty: THANKS for the pointer!<br />Some of the problems in the paper you point to DO indeed look natural. I may well teach PH next time I do the course!<br /><br />Bill (me) means problems that APPEAR to be in <br />PH-NP (of course we do not know any that<br />ARE there).GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44995997805949038392010-05-19T09:53:10.642-05:002010-05-19T09:53:10.642-05:00When he was talking about Sigma-2-P he found that ...<i>When he was talking about Sigma-2-P he found that it was hard to keep students interested, and so decided to not cover PH. BILL speculates that this may be true since there are no natural problems there.</i><br /><br />Come again? <a href="http://ovid.cs.depaul.edu/documents%5Cphcom.ps" rel="nofollow">http://ovid.cs.depaul.edu/documents%5Cphcom.ps</a><br /><br />By "there", does BILL mean "in PH - NP"?Dave Dotyhttp://www.csd.uwo.ca/~ddoty/noreply@blogger.com