Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
Algorithms and Data Structures: The Science of Computing contains material that neither students nor instructors usually expect in a second computer science course. Students may therefore resist learning the material, and instructors may be unsure how to make it meaningful to students. These notes describe some of the tactics the authors have used to overcome these problems. While the authors’ approaches are based on years of classroom experience, much of it teaching a course based on Algorithms and Data Structures: The Science of Computing, the most effective teaching styles will vary from instructor to instructor. Instructors should therefore judge the following in light of their own personalities, institutions, and students, and should freely combine the following ideas with their own.
Students do not learn unless they actively apply their new knowledge. Getting students to use the material from a course is probably the single most important thing an instructor can do. It is even more important that readers engaged in self study make themselves do exercises as well as read the text.
Laboratory exercises, homework assignments, and in-class problems are all excellent ways to get students to use knowledge. The Web site for Algorithms and Data Structures: The Science of Computing offers a number of laboratory exercises that can either be used as-is or be adapted by instructors to their own taste. The book itself contains end-of-chapter exercises that can be used for homework or in-class practice.
Instructors and students are, of course, encouraged to use the exercises in the book and on its Web site. Please, however, do not publish solutions on the Web or in other forms that reach beyond your own course, as too many students elsewhere will find and “borrow” your solutions instead of devising their own. (This is also why the book’s Web site does not provide solutions to labs or book exercises.)
Whether or not students should be allowed to work together, and, if so, what the limits of fair collaboration are, are endlessly debated questions. On one hand, it is clear that students who exploit collaboration by not doing their share of the work, or by not understanding their collaborators’ work, short-change their own educations (recall the comments above on the importance of personally applying new knowledge). On the other hand, there is a plausible argument that truly equal collaboration helps all parties involved — explaining ideas to peers forces a clarity of understanding that using ideas privately doesn’t, some students are more willing to ask questions and debate answers among themselves than in front of a professor, etc.
One reasonable position on collaboration is to allow students to help one another in out-of-class exercises, but require everyone to turn in an individual solution. Students who give or receive help should acknowledge that fact, and those who neglect acknowledgements should be gently penalized (one of the authors, who uses this approach regularly, finds that detected failures to acknowledge collaboration are almost always oversights, not deliberate cheating). These rules force every student to at least understand solutions well enough to describe them in the student’s own words. Collaboration on exams should be strictly forbidden, and students should keep this in mind as they decide whether or not to collaborate on exercises.
A very different form of collaboration involves deliberately collaborative learning via in-class exercises. In the classical form, the instructor poses a question, and then divides the class into groups of three or four students. Each group works collaboratively to answer the question and report their solution to the whole class. There may be explicit mechanisms to encourage every student to share their ideas with the rest of their group. One of the authors occasionally uses similar collaborative exercises, in a more casual form: as class time permits, he poses a problem to the class, and invites students to work with one or two neighbors to find solutions. Students who want to work individually may, although group work is the norm. After most groups seem to have made substantial progress towards solving the problem (typically five to ten minutes), the class reconvenes as a whole, and each group gives a short oral summary of their results or questions to the rest of the class. These exercises make a good, spontaneous, way to engage students in short exercises during class meetings, or to address certain questions that emerge from class discussions.
Many computer science concepts can be acted out by students. For example, a group of students can act out the central concepts of arrays by forming themselves into a line, and identifying themselves by their position (1, 2, 3, etc.) in the line. Other students can then access the “array:” to store data in it, tell the student at a particular position in the line to remember a word or other value; to retrieve data, ask the student at a particular position to say the word they are remembering. In all cases, of course, the students in the “array” can only be identified by their position in line. Concepts such as the size of the array, why one cannot access elements outside the bounds of the array, etc., can also be illustrated through this play-acting.
Concepts in Algorithms and Data Structures: The Science of Computing amenable to play-acting include objects and messages (students can be objects exchanging verbal or written messages), recursion (students can be activations of a recursive algorithm), any data structure, and more. The instructor notes for individual chapters contain detailed descriptions of some play-acting exercises.
By getting students out of their seats and interacting with one another, play-acting livens up a class and catches students’ attention. It can also bring out questions, both because students acting out a concept may realize that they don’t understand certain aspects of it, and because play-acting tends to relax the overall classroom atmosphere, thus encouraging students to speak. However, play-acting does not automatically explain the concepts being acted out — instructors should be careful to supplement play-acting exercises with discussion that points out how the play-acting corresponds to algorithmic concepts. It is often useful to interrupt a play-acting session at key points to explain the computing issues that the actors are portraying. Also, remember that shy students may not be as eager to play a part in these exercises as more extroverted students (although even the shy students will probably enjoy watching the exercise and may ask questions about it).
Like play-acting, physical models that represent a concept catch students’ attention and give them something to remember the concept by. Models can be created cheaply and quickly from almost anything — children’s toys; nuts, bolts, and similar household hardware; paper, string, tape, and other office supplies; etc. Often, the sillier the materials of the model, the more memorable it will be for students.
Most data structures are ideal candidates for models. Algorithms can also be demonstrated using models — a common example is to demonstrate searching or sorting algorithms using a deck of cards. The instructor notes for individual chapters of Algorithms and Data Structures: The Science of Computing suggest specific models appropriate to those chapters.
As with play-acting, models are not necessarily self-explanatory. Instructors should take care to point out the computing concepts a model embodies, and to explain how the model represents those concepts.
Assigning students sections of the text to read, and holding them responsible for doing so, is another way to engage students with course material. Readings should complement, but not duplicate, the material presented in lectures (if lectures and readings repeat substantially the same material, students will quickly realize that they need only attend to one). Ideally, students should be assigned a reading for each lecture.
One way to ensure that students do assigned readings is to randomly choose one student each day to summarize that day’s reading. These summaries can be very short — a good rule of thumb is that they should consist of approximately five sentences, describing the most important ideas in the reading or asking the central questions that need to be answered in order to understand the reading. The option of either summarizing the reading or asking questions about it is important, because it permits all students who seriously attempt the reading to participate, even if they are honestly unable to understand all of it. The brevity of the summaries is also important, because it forces students to think about what the truly key ideas or important questions are. Randomly choosing a student to present the summary encourages students to keep do every reading. Summaries should be graded, but lightly, and should only count for a small part of a student’s course grade — such grading lets students know that the readings are taken seriously, without imposing big grading burdens on instructors, without unduly penalizing students who occasionally miss a class in which their name is selected or who perform poorly when suddenly put on the spot, etc.
Use lecture time after a reading summary to answer questions asked in the summary, or to do in-class exercises that delve deeper into the reading’s ideas than the summary could. This strategy helps ensure that lectures truly complement readings, because the lectures either focus on the things that weren’t clear in the reading (things students asked questions about during the reading summary), or they use the exercises and ensuing discussion to dig deeper into the ideas than the reading did. It is, of course, entirely possible that in-class exercises will reveal that students do not fully understand the reading, but that is simply another way to find out what students don’t understand, and thus what lecture time can profitably be spent explaining.
Short exercises based on readings can serve similar purposes to reading summaries. These exercises should be very short and informal — they can be assigned orally during one class, and solutions reported orally by a randomly selected student at the beginning of the next class. The intent is to engage students more actively than a reading assignment by itself would, yet not to burden students (or instructors) with enough work to distract from more substantial homework assignments, laboratory exercises, etc. The authors call such exercises “mini-assignments.” Good sources for mini-asssignments include single exercises from the book, questions that students frequently ask, or the conclusions to examples begun but not finished in class. A well-developed question about a mini-assignment should be accepted from students in lieu of a complete solution — as with reading summaries, such questions help instructors recognize areas on which they can productively use lecture time.
If actively applying new knowledge is the best way to learn it, demonstrating ability to apply knowledge is the best way to prove that it has been learned. The authors thus strongly prefer test questions that ask students to solve problems by using what they have learned, rather than questions that ask students to paraphrase ideas from a book, remember facts from it, etc. The problems these questions pose should be ones that are in some way new to students, although they can be quite similar to problems seen previously.
Open-book tests are generally desirable. Knowing that the text (and notes) will be available reassures students, and may encourage them to focus their studying on understanding and applying ideas rather than memorizing superficialities. Given problem-solving questions such as described above, an open-book test is unlikely to significantly improve a truly unprepared student’s performance.
For more information on some of the teaching tactics discussed here, see the following:
S. Andrianoff and D. Levine, “Role Playing in an Object-Oriented World.” Thirty-Third SIGCSE Technical Symposium on Computer Science Education, Feb. 2002. pp. 121 - 125.
O. Astrachan, “Concrete Teaching: Hooks and Props as Instructional Technology.” Sixth Annual Conference on Teaching of Computing and Third Annual Conference on Integrating Technology into Computer Science Education — ITiCSE ’98 (SIGCSE Bulletin, Sep. 1998). pp. 21 - 23.
P. Bucci et al., “Toys Are Us: Presenting Mathematical Concepts in CS1/CS2.” Thirtieth ASEE/IEEE Frontiers in Education Conference, Oct. 2000. pp. F4B-1 - F4B-6.
S. Grissom and M. J. Van Gorp, “A Practical Approach to Integrating Active and Collaborative Learning into the Introductory Computer Science Curriculum.” Consortium for Computing in Small Colleges Midwestern Conference, Nov. 2000 (Journal of Computing in Small Colleges, Nov. 2000). pp 97 - 102.
J. McConnell, “Active Learning and its Use in Computer Science.” Conference on Integrating Technology into Computer Science Education, June 1996 (SIGCSE Bulletin, Special Issue, 1996). pp. 52 - 54.
B. Millis and P. Cottell, Cooperative Learning for Higher Education Faculty. Oryx Press, 1998.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin