tag:blogger.com,1999:blog-3722233.post2882806551953695987..comments2022-05-17T19:30:53.024-05:00Comments on Computational Complexity: ACM/IEEE Curriculum 2013Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-72736293727529245072012-04-18T04:11:41.239-05:002012-04-18T04:11:41.239-05:00I agree with the previous comment: P and NP are a ...I agree with the previous comment: P and NP are a Tier 1 topic in my opinion (see page 39 in the report).<br /><br />However, to me it seems Finite-state machines and Regexps could be put into Tier 2, and Context-free grammars can be removed from the core altogether...Thomasnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75670713962322605032012-04-17T15:39:20.923-05:002012-04-17T15:39:20.923-05:00I'm suprised that students are not necessarily...I'm suprised that students are not necessarily supposed to know complexity classes like P and NP anymore. The fundamentals of complexity theory do not seem to be important enough to include them into Tier 1 ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79680232091810464712012-04-17T08:26:55.255-05:002012-04-17T08:26:55.255-05:00This is very interesting and useful. My initial i...This is very interesting and useful. My initial impression, as someone at a liberal arts school where students have a lot of outside-the-major requirements and can only take a limited amount of major courses, is that it looks a bit daunting hitting all Tier 1 and 80% of Tier 2. It is nice that things have been divided into those two tiers though; I like that approach.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60779545764150834712012-04-16T15:39:15.776-05:002012-04-16T15:39:15.776-05:00Looks like a careful and thorough proposal.
My m...Looks like a careful and thorough proposal. <br /><br />My main comment about algorithms curriculum though is that it seems "backward looking" (carefully summarizing the material typically taught in algorithm courses over the last few decades) as opposed to "forward looking" (selecting the material that will be most helpful to the students graduating from now on). The corresponding materials are not disjoint, but are not entirely matching either.<br /><br />For an example of the latter perspective, see e.g., a recent book:<br /><br />John MacCormick,<br />"Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers"<br /><br />Some of the material (e.g., inverted indices, iterative algorithms) could easily be incorporated into undergraduate algorithms curriculum.Piotr Indykhttp://people.csail.mit.edu/indyk/noreply@blogger.com