EDUCATION FORUM: An Introductory Computer Science Curriculum Incorporating Theory

I mentioned in the last installment of the Forum that I would be attending the SIGCSE Symposium in Indianapolis. Some of the presentations and open sessions there concerned new "breadth-first" approaches to the introductory computer science curriculum. A lot of interest was evidenced in these new curricula, but so far only a few institutions have forged ahead towards actually implementing one. Our approach at Montana State University, which we presented at the symposium, is representative. A few years ago when we were required to switch from an academic quarter calendar to a semester calendar at MSU (in a somewhat hilarious and misguided attempt to save money), we decided we might as well be brave (recognizing, at least tacitly, that there is a fine line between bravery and bravado): we axed the entire freshman and sophomore introductory curriculum in one fell swoop and replaced it with a breadth-first approach. We were dissatisfied with the old way of doing things for a number of reasons. Specifically, with respect to theory, we weren't happy that our students were reaching their junior year without even being exposed to the science in computer science. None of them seemed to know that there were unsolvable problems (although in retrospect, many students were treating all problems as unsolvable); most didn't recognize the difference between tractable and intractable problems; and the idea of NP-completeness had not even reached their ears. Thus, as far as the theory portion of our new scheme was concerned we had two objectives: early and ongoing exposure-introducing students early to many of the fundamental concepts of theoretical computer science so that they would begin to appreciate these ideas immediately and assimilate them slowly and more thoroughly over the course of their academic careers; and natural integration-presenting theory as a natural part of the study of computer science, interweaving 2 theoretical issues into the "usual" topics of computer science (e.g., programming, data structures, and so forth), so that students would come to view theory as an integral and natural part of computer science, not a distasteful potion to swallow as a rite of passage to a degree. In actuality, these were our objectives for all aspects of our new course sequence, of which theory was just one part. Our plan proceeded along the following lines: 1. Embracing an integrative approach: In keeping with our objectives, we decided to commit to a completely integrated presentation of …