Some Strategies When
Teaching Theory Courses
DURING THE RECENT ACADEMIC
YEAR, I taught two upper-level theory-oriented courses: Analysis of Algorithms
and Automata, Formal Languages, and
Computational Complexity (really Theory
of Computation). Although various elements of the courses seem reasonably
common (e.g., a mix of lecture and discussion, small-group assignments, individual
assignments), this column describes three
additional elements that may be of some
interest to readers of ACM Inroads:
■ comparing versions of proofs;
■ oral presentations;
■ oral final exams.
My use of these elements has centered
on theory-oriented courses, but these
same elements might also be adapted for
other computing courses.
Comparing Versions of Proofs
In my experience, students often have
difficulties understanding what to include
in a formal argument and how to present their reasoning. What results can
be assumed? What details should be
stated? How much justification should be
included? How should an argument be
structured? And so forth.
To address such matters, at the beginning
of a semester, I commonly brainstorm
with students about common elements of
writing, such as the need to identify one’s
audience, the role of an introductory para-
graph, the logical flow of ideas, etc. My
students write many papers for humani-
ties and social studies classes, so they can
articulate many elements of good writing.
However, students often have difficulty
connecting writing for other disciplines to
writing formal proofs.
Of course, a main theme is that a proof
should convey an argument to a reader.
A well-written proof presents the appropriate steps clearly and in order, providing sufficient detail, but not belaboring
the obvious. To illustrate the notion of a
well-written proof, I consider a result that
students have seen in an earlier course on
Theorem: If S is a set with n elements,
then S has 2n subsets.
After stating the result, I distribute six
different proofs, three by induction,
two presenting a 1-1 correspondence
between subsets and binary numbers
0… 2n- 1, and one by contradiction. See
[ 2] for details of the proofs.
Students read the first three proofs for
the next class. The subsequent class discussion highlights strengths of each proof,
weaknesses, how well the argument is
conveyed, the level of detail presented,
etc. Then we brainstorm how the proof
might be improved. Following the discussion of the first three proofs, students read
the next three for the following class, and
again class discussion considers the relative merits of each proof.
Although I typically focus on class discussion, other exercises might be considered as well.
■ In preparation for a class, students
might submit their comments in writing (perhaps electronically or in an
■ Discussion could be in small groups
rather than a group of the whole.
■ Following discussion, students might
be required to write their own proof
that addresses the points identified
Although this exercise only starts the discussion of writing proofs, it seems to help
students consider issues of argument and
writing in the context of computing theory.
When discussing NP Completeness,
it seems common for students to be
able to parrot the definitions and high-level approaches, but understanding may
seem shallow. To encourage students to
delve into the subject, I identify 8-10 NP
Complete problems (typically from the
textbook or common sources). Students
then divide into groups of 2 or 3, pick a
problem, and present it to the class taking about 15 minutes ( 5-7 minutes per
student). In practice, this approach has
■ Students have strong motivation to
delve deeply into a problem, learning
why the problem is in Class NP and
how a known NP Complete problem
can be reduced to it.
When discussing NP
seems common for
students to be able
to parrot the
definitions and high-
level approaches, but