- The students overwhelmingly take crypto. One year 150 students took Crypto (one section of 50 in the fall, two sections of 50 each in the spring) and 8 students took automata theory. Both courses are always taught by people who are regarded as good teachers, so that is not the issues.
- I tend to think that Automata Theory is more important, but I may be biased. I also think that Automata Theory can be understood pretty well, whereas to understand crypto you really need to understand some Number Theory and even some security. Hence it is a strange stand-alone course.
- Some students think that the crypto course will get them a job. A course in security may get them a job, but just crypto I kind of doubt.
- Since more students choose Crypto we offer it more often. Since we offer it more often more students take it. (I exaggerate the circularity.) Also, its cross listed with Math so some math majors take it. This may account for some of the difference but not even close to all of it.
- So, how does your school do this? In particular, do you let the students tell you what course is more important, or do you tell them? Is it bad if they tell us? YES if we end up with courses on twitter, NO if the students are more aware of what is important then we old academics are.
Monday, February 22, 2010
What is more importantt: Automata Theory or Crypto?
The way the requirements are set up at Univ of MD at College Park,
without getting into details, has set up a competition between
Crypto and Automata Theory
That is, a student might take one or the other, but taking both
does not serve her well for the requirements.
Hence the students get to decide which one is more important, Crypto or Automata Theory.
We did not plan it this way, it just happened.
Automata Theory is Reg Languages, CFG/PDA, Computability theory, NPC.
(A later post will expand on this since I am teaching it this semester.)
Subscribe to:
Post Comments (Atom)
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.
ReplyDelete* 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.
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.
ReplyDeleteI do not think that automata theory is an important research area.
ReplyDeleteAddition 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.
ReplyDeleteI 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)?
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.
ReplyDeleteStudents need some amount on
ReplyDelete* finite automata/regular expressions
* basic undecidability
* NP-completeness (reductions but not proof of Cook-Levin)
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.
Also, if you called the course something other than "Automata Theory" I think that you would get more students.
In my school Crypto is optional, and there are two compulsory undergraduate courses that overlap with "Automata Theory":
ReplyDelete- Logic and Computability theory.
- Formal languages and intro. to compiler design.
Basic Complexity theory is spread in two Algorithm courses.
(Here in Argentina, it's a joint bachelor's and master's degree after five years.)
Anonymous Six is right. 'Theory' sounds scary. 'Web' is much more friendly. Call it Web Search.
ReplyDelete(I'm half joking.)
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...
ReplyDeleteSince 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?
ReplyDelete1) It is an ugrad course I am talking about.
ReplyDelete2) Noam- Crypto is crosslisted
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.
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
non-rigorously. (DFAs and
PDA's). That may make the need for Automata theory less.
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.
ReplyDeleteI 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:
i. Needed for CS GREs, reading old papers, and other legacy uses
ii. The DFA, PDA, TM progression is cute.
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.
ReplyDeleteAs 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.
ReplyDeleteWhy 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?
ReplyDeletehttp://www.diamondbackonline.com/news/teaching-tweeting-1.1167737
ReplyDelete@rgrig
ReplyDeletethe right name is "Green web innovation"
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.
ReplyDeleteThey 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.
I am guessing here. So others' guesses may be as good or better than mine.
Yeah, crypto is MUCH sexier than Automata.
ReplyDelete"Crack some exciting codes" vs "Blah blah blah computability, recursive sets, ZZZZZZZZZZZZZZ" is pretty much a no-brainer.
"Research into parsing theory is an excellent way to gain obscurity" (David Dill, possibly apocryphal)
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.
ReplyDeleteIt 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).
ReplyDeleteJust 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.
Piotr