[STOC 2012 Early Registration Deadline Thursday]

On a roughly ten-year cycle, the ACM and IEEE Computer Society get together to create a list of core topics that every getting an undergraduate CS degree should know. The joint task force has a strawman draft proposal and would like your comments for a final report hopefully next year.

This version breaks the requirements into Core-Tier 1 and Tier 2 with the more critical material in Tier 1 and also suggests some elective topics.

In Algorithms and Complexity there is a combined 21 lecture hours of material for Tier 1 and Tier 2 that should comfortably fit into a single quarter long course though that seems aggressive given the list of material. That is built on 41 hours of "Discrete Structures" that includes basic combinatorics and proof techniques. It's a testament to the fundamental importance of theory that it holds more core hours than most other areas.

While I'm always wary of outside committees setting courses and topics, these reports do give guidance in what the "community" believes are important topics for all well-trained computer scientists to know. They can heavily influence curriculum in theoretical computer science especially at the too many CS departments that don't a significant theory group. So take a look at the draft and give your comments to the task force.

Looks like a careful and thorough proposal.

ReplyDeleteMy 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.

For an example of the latter perspective, see e.g., a recent book:

John MacCormick,

"Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers"

Some of the material (e.g., inverted indices, iterative algorithms) could easily be incorporated into undergraduate algorithms curriculum.

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.

ReplyDeleteI'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 ...

ReplyDeleteI agree with the previous comment: P and NP are a Tier 1 topic in my opinion (see page 39 in the report).

ReplyDeleteHowever, 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...