then carrying them out in precise detail. The latter skill certainly has to be
learned, and I thinkthat the proof sketches in this text provide very appropriate
starting points for such a practice.
Computer science students sometimes view a course in the theory of
computation as unnecessarily abstract and of no practical consequence. To
convince them otherwise, one needs to appeal to their specific interests and
strengths, such as tenacity and inventiveness in dealing with hard-to-solve
problems. Because of this, my approach emphasizes learning through problem
solving.
By a problem-solving approach, I mean that students learn the material
primarily through problem-type illustrative examples that show the motivation
behind the concepts, as well as their connection to the theorems and definitions.
At the same time, the examples may involve a nontrivial aspect, for which
students must discover a solution. In such an approach, homeworkexercises
contribute to a major part of the learning process. The exercises at the end of
each section are designed to illuminate and illustrate the material and call on
students’ problem-solving ability at various levels. Some of the exercises are
fairly simple, picking up where the discussion in the text leaves off and asking
students to carry on for another step or two. Other exercises are very difficult,
challenging even the best minds. The more difficult exercises are marked with a
star. A good mix of such exercises can be a very effective teaching tool. Students
need not be asked to solve all problems, but should be assigned those that
support the goals of the course and the viewpoint of the instructor. Computer
science curricula differ from institution to institution; while a few emphasize the
theoretical side, others are almost entirely oriented toward practical application. I
believe that this text can serve either of these extremes, provided that the
exercises are selected carefully with the students’ background and interests in
mind. At the same time, the instructor needs to inform the students about the
level of abstraction that is expected of them. This is particularly true of the
proof-oriented exercises. When I say “prove that” or “show that,” I have in mind
that the student should think about how a proof can be constructed and then
produce a clear argument. How formal such a proof should be needs to be
determined by the instructor, and students should be given guidelines on this
early in the course.
The content of the text is appropriate for a one-semester course. Most of the
material can be covered, although some choice of emphasis will have to be
made. In my classes, I generally gloss over proofs, giving just enough coverage
to make the result plausible, and then ask students to read the rest on their own.
learned, and I thinkthat the proof sketches in this text provide very appropriate
starting points for such a practice.
Computer science students sometimes view a course in the theory of
computation as unnecessarily abstract and of no practical consequence. To
convince them otherwise, one needs to appeal to their specific interests and
strengths, such as tenacity and inventiveness in dealing with hard-to-solve
problems. Because of this, my approach emphasizes learning through problem
solving.
By a problem-solving approach, I mean that students learn the material
primarily through problem-type illustrative examples that show the motivation
behind the concepts, as well as their connection to the theorems and definitions.
At the same time, the examples may involve a nontrivial aspect, for which
students must discover a solution. In such an approach, homeworkexercises
contribute to a major part of the learning process. The exercises at the end of
each section are designed to illuminate and illustrate the material and call on
students’ problem-solving ability at various levels. Some of the exercises are
fairly simple, picking up where the discussion in the text leaves off and asking
students to carry on for another step or two. Other exercises are very difficult,
challenging even the best minds. The more difficult exercises are marked with a
star. A good mix of such exercises can be a very effective teaching tool. Students
need not be asked to solve all problems, but should be assigned those that
support the goals of the course and the viewpoint of the instructor. Computer
science curricula differ from institution to institution; while a few emphasize the
theoretical side, others are almost entirely oriented toward practical application. I
believe that this text can serve either of these extremes, provided that the
exercises are selected carefully with the students’ background and interests in
mind. At the same time, the instructor needs to inform the students about the
level of abstraction that is expected of them. This is particularly true of the
proof-oriented exercises. When I say “prove that” or “show that,” I have in mind
that the student should think about how a proof can be constructed and then
produce a clear argument. How formal such a proof should be needs to be
determined by the instructor, and students should be given guidelines on this
early in the course.
The content of the text is appropriate for a one-semester course. Most of the
material can be covered, although some choice of emphasis will have to be
made. In my classes, I generally gloss over proofs, giving just enough coverage
to make the result plausible, and then ask students to read the rest on their own.