Non-Programming Resources for an Introduction to CS

Well constructed non-programming resources have proven invaluable in aiding students master introductory CS topics. Unfortunately, such resources are hard to identify and/or develop. A working group was convened concurrent with the ITiCSE 2000 conference to examine this issue. This paper, and an accompanying Web page (http://csis.pace.edu/~bergin/iticse2000) have therefore been developed to foster the development and distribution of resources that educators can use to introduce important introductory computer science topics without programming.

This paper is one result of a working group held at ITiCSE 2000 in Helsinki Finland, July 10 to 14, 2000. The purpose of the working group is to foster the development and distribution of resources that educators can use to introduce important computer science topics without programming. Such resources can be used in courses that also have an important programming component as well as those that do not. Our primary, but not exclusive, focus has been introducing topics that naturally lead to programming in object-oriented languages, such as C++ and Java. Even an OO course has many elements which are not specifically object-oriented, such as problems solving and algorithms. Some of the resources here are applicable to OO as well as to non OO courses, though they may be used in different ways and at different times within the course.

The working group is also developing a website that will serve as a permanent repository of collected resources. It will serve as a focus through which other educators can contribute additional resources. The URL of this site is http://csis.pace.edu/~bergin/iticse2000.

The phrase "Non-Programming Resources" denotes a wide variety of techniques and tools. These include examples, exercises, tools, techniques, games, toys, pedagogical patterns, and many other things. Important metaphors can be resources if they lead students to powerful and accurate thinking about computer science topics. The defining characteristic is that these resources do not involve computer programming. They may involve other formalisms and may lead to programming at a later point.

In most introductory computer science courses students are burdened with the task of learning a new language with somewhat arbitrary syntax and a seemingly unnatural (for humans) semantics. Coding a well-understood, well-designed solution can often be a challenge. But frequently we give students a real-world-like problem and expect them to design and code a solution. For many students the complexity of understanding the problem and communicating a design to peers in their speaking language is difficult. When students try to design and code at the same time, they frequently make the situation more complex than it would be if they first designed a solution in natural language and then subsequently faced the issue of coding.

In his classic essay No Silver Bullet, Frederick Brooks [BRO] distinguished between the notions of accident and essence in software engineering. The essence of a software system is the conceptual, almost inspirational, core of logic and design that forms the underpinnings of the system. The accidental aspects of the system are the factors such as secondary design, coding, and testing that "naturally" follow from the essence. Brooks argues that, because the role of the accidental factors is limited and since technology can help developers only with the accidental factors, no developments in technology can affect an order of magnitude increase in the productivity of software developers.

We might draw an analogy between Brooks's argument as applied to software engineering and how it could be applied to computer science educational practices. Especially in introductory courses, we often tend to focus on teaching techniques that are specific to programming, in particular, the coding of programs. We might call these techniques the accidental aspects that we want our students to learn in an introductory course. However, the essential aspects of what our students should learn, such as general problem-solving, analysis, design, and algorithmics, are much more difficult to convey through conventional teaching techniques. These essential aspects are much more valuable in the long run than the accidental aspects. Often they can only be mastered through highly active participation on the part of the student, not by rote learning a highly organized set of rules. As teachers, all of us need ways to help our students discover these essential aspects of the discipline. It may well be that these essential aspects can only be learned through self-discovery, so our task as educators becomes one of providing the means for that discovery.

In the 1980’s John Carroll and his collaborators carried out a series of experiments in technical training at MIT which concluded that a systems approach to education fails and that minimalist instruction succeeds. The systems approach, called the Objectivist approach, has the instructor logically partition and sequence the topics to be learned and puts all students through the same sequence. Minimalist approaches, on the other hand, provide no such path through the material, but put the learners to a task meaningful to themselves and provide simple aids for avoiding and getting out of difficulties. One reason, perhaps, that the minimalist approach works is that it makes the learners more active. Objectivist approaches treat the learner as a blank slate into which knowledge can be poured. It also assumes that logical progression is the best learning methodology. It does not fundamentally depend on keeping the students active. Minimalism, on the other hand, does depend on active learners integrating new skills into what they already know. In this regard minimalism is closely related to Constructivist educational theory, which holds that knowledge is constructed by the learner as part of the learning process rather than being something that exists independently and must be actively integrated into what is known by the individual. Constructivist approaches emphasize the importance of the learner’s intention, while Objectivist theory stresses the structure of the information itself. A good introduction can be found in Elizabeth Murphy's sites [MUR1, MUR2]. See also the work of Thomas Reeves [REE] and John Carroll [CAR1, CAR2].

The development of these resources is viewed by the members of the working group as a continuing process. Collaboration with others is actively desired and actually required if we are to be successful. Good resources (see, for example, the work of David Ginat [GIN]) are gems. Educators with ideas for resources as well as those with already developed resources are encouraged to contact one or more of the authors. We will be happy to work with others to develop ideas into resources and host the results on the project web site or link to those hosted by others. There is already a larger group of individuals interested in these topics who communicate frequently. Others are encouraged to join this group. All contributions will, of course, be acknowledged. The site is http://csis.pace.edu/~bergin/iticse2000.

The remainder of this paper is organized as follows. Section provides a description of how our resources are presented. Section 3 contains the paper’s collection of resources for presenting object-oriented concepts. Section 4 and 5 contain our resources for general problem-solving and algorithmic think respectively.

There is some correspondence between the four elements of the template and those used to define pedagogical patterns [BER1]. On the other hand, the resource template is simpler and relies on the elements Examples of Classroom Use and Commentary to cover the multitude of details.

We provide in this section a number of Non-Programming resources. The website associated with this project should be consulted, as the authors intend to encourage contributions to the site over the coming years.

A number of educators have become dissatisfied with available pedagogy for teaching computer science now that we have moved to using object-oriented languages as the primary means of expressing algorithms. If object-oriented programming is indeed a new paradigm, then all of the old techniques, appropriate for other paradigms, need to be re-examined and possibly replaced by new techniques. This includes pedagogical techniques no less than it includes programming techniques. A paradigm shift truly puts the world into a new state in which old techniques, assumptions, and beliefs become obsolete. Therefore, it may well be that the pedagogy that is correctly used to teach one paradigm (e.g., procedural programming) is not adequate for the teaching of a different paradigm. In the current situation, many current textbooks for the introductory courses seem to use pedagogy that was very useful for teaching procedural programming using Pascal. Examples in many of these books seem to add syntactic complexity (class wrappers) to what are fundamentally procedural rather than object abstractions. To correctly introduce a new paradigm, educators may need to throw away many of their current resources or at least use them in a very different way.

There is a fairly common belief among educators that when we are asked to do new things that we must as a consequence teach all of the old material in the old way and then add the new material on the top. We constantly hear "what should be dropped" when someone is asked to incorporate new material. An alternative approach to dropping and adding material is to radically rethink the pedagogy we use in teaching computer science. This can, perhaps, avoid the above trap.

When we ask students to do and learn complex things we need to take account of the complexity load we burden them with. Some see object-orientation as complex in itself. While this claim may be true or false, it is nevertheless important that we develop pedagogical techniques that "spend the complexity budget" in ways that have high leverage for learning and that limit the complexity of ancillary topics while we focus on any topic that has some inherent complexity. On the other hand, it may be that appropriate pedagogy can present object-orientation in a way in which the complexity seen by some does not appear at all. In particular, if students learn object-orientation from the beginning they will not have to go through the dreaded paradigm shift that stops so many skilled programmers from learning OO for the first time.

One aspect of a new pedagogy for teaching involves the selection of examples shown to students and exercises worked on by them. A minimal object-oriented system always has more than one class, the various objects interact with one another, and most classes are multiply instantiated. If we give students early examples that do not have these characteristics, then they will not get a valid picture of an OO system. If we additionally reinforce an incorrect picture by having them program systems which do not have these characteristics, then we will be building bad habits that must be eventually unlearned. If we want the educational process to be efficient from the standpoint of the learners, then we must choose only techniques that reinforce positive elements. Thus, the first example shown to students must necessarily be more complex than is typically true of procedural programming.

If we are to do this and still control cognitive complexity, then we must show systems through designs while avoiding syntactic complexity altogether. Therefore, prior to programming, it can be very useful to give students a picture of a minimal OO system as well as giving them guidance in finding the communicating objects that are required in a solution of a particular problem. Along the way we can give them metaphors that help them think about characteristics of OO systems and heuristics that help them design objects.

One of the main goals of this exercise is to provide an example that will give students a valid and complete picture of an OO program and yet be as simple as possible. It attempts to control complexity seen by the students. In those places in which it has some complexity, the complexity is essential and leads to good lessons for the students. In other words, it gives a framework that provides high leverage in student learning.

The following characteristics are all desirable for a first introduction to OO systems.

1. Problem domain is known to the students
2. Admits a variety of natural OO solutions
3. Simplicity (three to six classes)
4. Interaction (objects have natural interactions)
5. Non-triviality (at least one class is naturally instantiated more than once in a good solution)
6. Admits polymorphic solutions–but does not require them (hierarchies, interfaces, …)

Each method defines a simple service and has a simple implementation (no private methods required).

The exercise is to design a Coffee Machine [COC]. This exercise follows a discussion of a day or so on objects, CRC cards, and simple UML style class diagrams. The initial statement of the problem is as follows:

A good solution to this exercise has about five classes. Additionally, an abstract class might be used to define common characteristics of the various dispensers. A truly sophisticated design will use one kind of object as parameters to the services (methods) of the other objects.

This resource can be used in the very beginning of a first course, prior to any programming, to introduce object oriented concepts and simple elements of OO design. It is flexible in that it may be used in a variety of other ways also. It can be used as a student in-class exercise, an example discussed by the instructor, as a take-home exercise for students, or even as a (take-home) mid-term examination.

A recommended form of usage follows the pedagogical pattern Student Design Sprint [BER2], in which the design exercises goes through several phases with changing requirements in each phase and a merging of small teams into increasingly larger teams in each phase. The exercise is carried out in class and requires at least 8 students.

Teams are initially two students. The teams are given the above problem and asked for a design. After about 30 minutes of effort, CRC cards and a class diagram are required. If the class diagrams are written on overhead transparencies, the instructor can show each one briefly and comment on its good features and those that might be improved by the teams. At this time pairs of teams are merged to give teams of four, and an additional requirement is added (for example: Tea can also be dispensed for $.35 US). This can continue for as long as necessary with merging of teams and changing of requirements. The CRC cards of one or more of the iterations may be used for walk-throughs ("Objects Walking Around" pedagogical pattern) of use cases to determine if requirements are met and if communication paths are clean and clear.

One feature of this exercise is that the students see several designs and are required to merge their own ideas with those of classmates. Good designs require five or six classes and may involve specialization (inheritance) or not.

Another example of about the same complexity (perhaps a bit larger) is an elevator or a bank of elevators coordinated by a single controller.

When the students begin this exercise they have little concept of class and type. It also enforces these ideas, as the dispensers are all similar, but not identical. On the other hand the ChangeBox is quite different from a Dispenser. Students know about different "kinds" of things and this information can lead them to the notion of type.

The multiple instantiation of some class also helps them distinguish the ideas of class and object. The instructor should be prepared to emphasize this and make the distinction explicit.

Identify objects and object interactions in a chosen problem space.

This is a verbal game that can be played with two or more players. The rules are simple and the instructor can select a problem space, choose the range of statement forms to focus on particular OO concepts and determine the depth of the activity.

Players can be grouped to accommodate large numbers of participants. The instructor or one of the players can start by saying aloud a statement in a particular format. From then on, each contribution is a connecting statement, something like a word association game.

Possible statement forms include:

Logical sequence is not required, merely that one of the same nouns or verbs is used in the next statement. This allows for a wide variety of possible connections:

Example transcript, in the banking problem space:

The game could be a useful preparation for introduction of more formal techniques such as use cases.

The instructor can determine the depth of the activity. To familiarize students with the problem space and the game, start with a brief, fast-pace exercise with unrestricted statement forms. To capture responsibilities on paper, play it again; when each new noun is first brought into the game, assign a person to capture its responsibilities on a CRC card.

The main goals of problem-solving resources are to aid the thinking process and exercise inventive faculties. Secondary goals are to help students learn to manage complexity and introduce them to the challenges and joys of success in problem solving. The skills, knowledge, and ability developed here should transfer to many other situations. Students will acquire a ‘can do’ attitude and learn that problem solving is a creative art.

A problem arises when one has accepted a goal but has no immediate means of reaching the goal. Good examples for problem solving practice will yield to techniques that will generalize to other problems (high-leverage techniques). Many modern computing problems can be approached by asking: how can I view the given situation as a community of interacting entities? How should the entities communicate? Once appropriate entities have been selected and tasks identified, the following problem solving stages from "How to Solve It" by G. Polya are worth considering. Polya’s 1945 book was directed toward mathematicians but the general techniques propounded apply equally well to other domains including computer science. The stages are Polya’s. We have taken liberties with the explication of the stages to make them more germane to CS problems. Polya’s stages are:

First. Understand the problem.

What is the goal? What are you given? Do you understand the raw data? Draw a picture of the situation. Describe the problem in your own words. Can you find objects that should communicate with each other?

Second. Devise a plan.

Find a connection between the raw data and the goal. Consider auxiliary problems if an immediate connection cannot be found. Have you seen a problem like this before? Do you know of a related problem whose code might be adapted to this problem or a part of this problem? Can you solve a more specialized problem? Can you solve a more general problem? If you cannot solve the given problem, design a similar, simpler problem that you can solve. Seek insights from the solution of the simpler problem. Given the goal, g, can you find a situation, s1, closer to the starting point, from which you can get to g? Can you find a situation, s2, closer to your starting point from which you can get to s1? Keep repeating. In computer science, algorithm design is only part of the problem. But, well-known algorithm design techniques may apply. These include: brute force, greedy, divide and conquer, and dynamic programming. If all else fails, work hard on the problem for a few hours, then put it aside overnight and let your subconscious work for you. Many students are unaware that their subconscious can work for them. The subconscious will not help without some initial hard conscious work. However almost any professional knows that after an initial period of hard conscious work, fruitful ideas come from the subconscious at unexpected times.

Third. Carry out the plan.

Work in small increments. Add scaffolding so that you can know that each step is correct. Can you see clearly that each step is correct? Can you prove that each step is correct?

Fourth. Look back.

Check the result. Can you solve the problem differently? Can you use this solution for any other problems?

To aid student understanding of backward reasoning, problem decomposition, and (optionally) programming implementation.

A well selected problem whose solution is most appropriately arrived at via backward reasoning.

The exercise is to count how many ways to climb an n rung ladder. The stipulation is that the climber can take the rungs either one or two rungs at a time. [GIN1]

Assign the problem as an in-class exercise. Students can work individually or in pairs. After 10-15 minutes review student solutions. Finally, present an appropriate solution derived via backward reasoning.

Similarly, this problem can also be assigned as an overnight assignment.

There are three interesting aspects about this problem. The first is that it is a classical case where backward reasoning is the most appropriate problem solving approach. (Count the number of ways to climb to the penultimate rungs plus the number of ways to count to the contra-penultimate rung plus two.) Furthermore, this leads to a recursive problem decomposition. Finally, since the solution is to compute the nth Fibonacci number, students can see an illustration that the method used to solve a given problem does not immediately translate into an efficient algorithm.

To aid student understanding of enumeration as a problem solving paradigm.

A well selected problem whose solution is most appropriately arrived at via an enumeration argument.

The exercise is to consider how many ways one can tile a path of length n, using tiles of two different sizes A and B. The path must be perfectly covered by the tiles; the tiles may not fall short, or extend beyond the path. [GIN2]

Assign the problem as an in-class exercise. Students can work individually or in pairs. After 10-15 minutes review student solutions. Finally, present an appropriate solution derived via tile enumeration. Similarly, this problem can also be assigned as an overnight assignment.

Students often attack this problem with a brute force approach. While this will work, it is computationally very inefficient. A more natural solution is to use an enumeration argument. First consider one A tile, then consider two A tiles, etc. This has the advantage of dramatically reducing the problem space when an incompatible combination is found.

To aid student understanding of backward reasoning as a problem solving paradigm.

A well selected problem whose solution is most appropriately arrived at via backward reasoning.

The exercise involves designing a strategy of how to win the following two person game. The game, which is derived from NIM, is played on an n-space path. At one end is the start, while the other end is the goal. At the start is a pawn which players alternate moving from 1-6 spaces forward. The player who makes the final move of the pawn to the end space wins. [GIN3]

Break the class into pairs of students and have them play the game a number of times. Afterwards give the student pairs about 15 minutes to see if they can develop an algorithm for a winning strategy. After the strategies have been developed, have each team play another team to test strategies. One can run this to its logical conclusion as a tournament with each aggregation getting some time to further refine the winning strategy prior to the next round.

After the tournament has concluded, if a correct solution has not emerged, present an appropriate solution derived via the explicit use of backward reasoning.

Introductory students often have a difficult time applying backward reasoning. This problem can only be successfully solved via backward reasoning. While students may discover the solution, formally deriving a winning solution by working backwards helps students visualize the utility of backward reasoning.

To aid students in applying Polya’s recommended methodology for discovering a solution to a problem.

A seemingly simple problem for which no initial solution suggests itself.

The exercise is as follows: A bear starts at some point P. She walks due south for one mile. She turns left and walks due east for one mile then turns left and walks due north for one mile returning to point P. What color is the bear?

This problem can be given at any point in a course. Have students work in groups of 2-3. Assure them that the problem is legitimate and there is a way to apply reason to reach a solution. Teams that have a solution can report it to the instructor. Teams that want a hint can obtain one from the instructor. As some early teams find a solution (most likely P is north pole and the bear is white), ask them to consider if there are any other points on the globe that would allow a traversal following the same rules and arriving back at the starting point. After some reasonable amount of time, let some students report initial solution and others report about the infinite number of other possible points P. If no group has discovered other possible points, give hints until the class has them.

Problems for which there are no immediately apparent solution, or methodology are sometimes, for students, the most difficult to solve. This exercise provides a practical framework for students to gain experience in applying well-known problem solving techniques to overcome this initial block.

To aid students in applying Polya’s recommended methodology for discovering a solution to a problem.

An easily understood problem whose solutions involve a non-trivial number of intermediary (and possibly complex) steps.

The first exercise assumes that the students are given a file of ordinary prose or poetry (say a play by Shakespeare). The students are to design an approach to the problem that if coded would output a list of the words used with a count of each word’s occurrence in decreasing order of frequency of usage.

Other possible instances include the design of a hand-held reverse polish notation calculator (suggested by Kim Bruce of Williams College), and the design of a robot control system with two front sensors and two rear drive motors that prevents the robot from hitting any obstacle in its path (suggested by Lynn Stein in an invited lecture at ITiCSE 2000).

This problem can be given after searching and sorting have been discussed. One can assign it as a homework assignment for teams of 2-3 students. The designs to be handed in should be detailed enough that any student in the class could code a solution from the design document with ease. Ask students to consider how the running time of their solution might depend on the length of the text and the possible density and distribution of frequently used words.

After solutions are handed in, discuss the various attributes of different student designs. After discussing meritorious student designs, introduce any of the following that have not been covered by the students.

1. Words initially entered in an unordered array with associated frequency counts so far. Each time a word is read from the file a linear search is used to find the word. Associated count is increased if word has already occurred. Word is appended with count of one if first occurrence. After text has been completely read, sort array in descending order by count.
2. Similar to above but keep initial array in alphabetical order. This allows binary search for each new word but requires moving array elements (or references) to make room for new words.
3. If linked lists have been discussed, consider keeping most recently found words first (similar to MRU) and then sorting by frequency after all words read in. Another possibility is to keep most frequent words first avoiding a latter sort.
4. Introduce the idea of a hash table.
5. Discuss binary search trees.
6. Discuss tries. (In Bentley’s column, Knuth submitted a solution using hash tries.)
7. The following solution can be made a one-line shell script in Unix (submitted to Bentley’s column by McIlroy). Translate all letters to lower case. Translate all white space to newlines and eliminate repeated newlines. We now have a file with all the words consisting of one word per line. Use system sort to sort this file alphabetically. Make a linear pass over this sorted file, eliminating duplicate words while accumulating counts of occurrences. Now we have a file consisting of all words (each once) followed on the same line by the count of occurrences. Now use system sort to sort file in decreasing order by number.

Students can be asked to code some solutions. The complete texts of Shakespeare’s plays can be found on-line so students can be asked to run their final product on a particular play.

Introductory CS students sometimes feel overwhelmed by all that they believe they are asked to undertake in the introductory courses. In addition to mastering the syntax of a formal language, learning successful design techniques, mastering the use of a development environment, students also need to discover solutions to the various problems assigned.

Most of the typical problems assigned in the introductory courses can be solved using one of the following problem solving paradigms; brute force, greedy, divide and conquer, and sometimes dynamic programming. (Unfortunately, many CS curricula, as reflected by the current crop of textbooks, delay the formal coverage of these important problem solving paradigms until the second or third year.) Furthermore, students often have familiarity with these techniques, though they have not approached the technique from a formal perspective.

The goal of this resources, therefore, is to aid students in early understanding of these problem solving techniques from a more formal perspective and that a very large domain of problems can be solved by applying one, or more, of these techniques.

For each problem solving method use a "real-world" problem, drawn from the lives of students, for which the given method is the most natural method for formulating a solution.

Give students a list (5-6) of locations in the local environment that all must be visited in an afternoon of "running chores." Indicate that the chore runner is walking to avoid the optimization of avoiding left turns on busy streets.

Ask the students to independently provide a plan for accomplishing all the chores. It is an interesting classroom exercise to observe (hopefully) that the solutions are all identical. This can be followed up by the use of another non-programming example. Finally, a pseudo-code template of the algorithm paradigm should be developed on the board or passed out as a handout or Webpage.

Provide student pairs with a long (~20) list of moderate sized integers to sum up. Many, though possibly not all, teams will utilize a divide and conquer approach.

Similarly one can have the student pairs sort a deck of playing cards.

Students are excited to learn that they already know some powerful algorithmic techniques. The greedy method, if presented as the first (or an early) problem-solving technique, can serve to build student confidence in their problem-solving abilities.

The divide and conquer method is appropriate to introduce concurrently with or immediately after recursion is introduced. This allows students to see recursion, in addition to its other benefits, as an important technique for implementing a divide and conquer solution.

It is unclear whether the brute force paradigm needs formalization beyond a discussion of the method. Furthermore, given its association with procedural top-down design it may be useful to delay the formalization of this methodology until after the students have developed an appropriate object-oriented mindset.

To aid students in gaining an understanding of

• what is a computing agent
• the limitations of a computing agent
• what is an algorithm (unambiguous sequence of effectively computable steps).

A problem, well known to the students, for which multiple algorithms are known. One of these algorithms should be known by all the students, while one other should not be known to any of the students. Furthermore, the two identified algorithms should contain a small number of variables, selection and iteration statements.

Multiplication of positive integers (e.g. four digits in length). The two algorithms might be the traditional long multiplication algorithm taught in grade schools (the known algorithm) and multiplication ala Russe (a.k.a. the Russian peasant algorithm and Egyptian multiplication) for the unknown algorithm.

Sorting a set of items for which radix sort is applicable. (e.g. A deck of cards, or a set of positive integers.)

In-class exercise; have one student at the blackboard act as a computing agent. (Decide what steps are computable, and have the computing agent perform only these steps when asked to.) Have the other members of the class provide the computing agent instructions/algorithm to compute the result for a given problem instance. (e.g. Pick two 4-digit long random integers for multiplication.)

Upon conclusion, success or failure, chose another student to act as the computing agent at the board. Using the same problem instance, the instructor provides the computing agent the instructions/algorithm to compute the result using the universally unknown algorithm. After the exercise, the instructor can provide a handout or webpage containing a formal description of the unknown algorithm.

Optionally, prior to this exercise pick a computing agent and a task that will certainly fail. An example is to have the computing agent retie their previously untied shoes.

There are many subtle lessons to be distilled from this exercise. These include the observation that more than one algorithmic solution may exist for a given problem. (It is probably not appropriate to discuss the relative merits between the two algorithms at this point.) All algorithms are formed from a small set of simple primitives that comprise the set of effectively computable steps for modern electronic computing agents. Students should also come away with the notion that algorithmics, even when a solution is already known, is not trivial.

To aid students in performing asymptotic analyses of algorithms

Two songs, one linear, and one where each verse gets progressively longer since each verse also contains some element of each verse sung prior to it. (i.e. quadratic) Children's songs often have this property.

"Old Macdonald" is one such quadratic song. "Ninety nine bottles of beer on the wall" is an example of a linear song. The size of the input set is the number of verses sung.

The exercise is to express the number of syllables sung in the complete song as a function of the number of verses sung.

After students have performed an exact analysis, one can then show the generalization from the exact analysis to asymptotic analysis. [CHA]

Optionally, one can lead the class in song for a direct illustration of how the relative growth rates are reflected in the songs' respective singing length.

Even simple algorithms are difficult to perform an exact analysis. This implies that students learn asymptotic analysis first and exact analysis sometime later in the curriculum, instead of learning asymptotic analysis as a generalization of exact analysis. Analyzing simple well known songs exactly, on the other hand can be done. The generalization from songs syllables to algorithm steps is straightforward.

When algorithms are first introduced students have an unclear idea about the nature of an algorithm and almost no idea of efficiency. This resource is an attempt to improve student understanding of both topics. Average running time complexity may be especially elusive for many students, depending on their mathematical background.

A problem is posed to students that admits various algorithmic solutions of differing complexity and/or efficiency.

Suppose you have introduced sorting of linear structures, perhaps with some programming or not. Usually instructors move from less efficient algorithms to more efficient ones. Instead, ask the students for ideas for the most inefficient algorithm they can think of.

One inefficient algorithm that the students will probably recognize as an algorithm is as follows: pick two random elements and if they are out of order swap, check that the structure is in order and then repeat if not. One that is even less efficient is to swap them without the check. This may not be recognized as an algorithm by many students, as it depends on the law of large numbers of probability. This may give you an opportunity to discuss the law of large numbers and the nature of the finiteness requirement of algorithms.

Another possibility is a game "Mine is worse," with students trying to outdo each other and find the worst possible algorithm (that is still an algorithm). This might also be called "Rube Goldberg" after the American cartoonist who devised terrifically complex machinery for doing the simplest of tasks. The instructor helps weed out those suggestions that are not algorithmic and may need to provide hints on relative efficiency.

To help students understand the essential components of a recursive definition:

• Base case (that is, termination condition)
• Self-referential case (that is, the inductive case)
• Realization that, in the self-referential case, we must invoke a "simpler" version of the definition, that is, one closer to the base case

The following characteristics are desirable for an introduction to recursive definitions:

• The notion defined should be one intuitively familiar to students but it should also be one that is difficult to define in a non-recursive fashion. This will ensure that students see the need for recursion in defining the notion.
• The recursion should be linear, that is, it should not involve two or more self-referential cases

Consider the problem of defining a human. For the self-referential case, one could say: "A human is something whose mother is a human." Identify what's incomplete about this definition and discuss (avoiding heated religious debates) what is needed to complete the definition.

The "Russian dolls" that contain smaller clones of themselves within themselves provide an interesting discussion vehicle.

Consider the problem of defining an integer. For the self-referential case, one could say: "An integer is a digit followed by an integer." Identify what's incomplete about this definition and discuss (no religious debates here) what is needed to complete the definition.

In class ask students for a definition of a human. If they are not thinking recursively, they will probably feel that an unambiguous definition of this notion is "impossible". Then propose the self-referential definition described in the instantiation above, that is, "A human is something whose mother is a human."

Students may remark that they always been told by those who teach writing and composition skills that a term should never be defined in terms of itself. Pick out a student and ask the class how we could possibly verify that student's humanness using this definition. This should ultimately lead the class to a realization of the need for a base case to terminate the recursion. At this stage, proceed carefully since you must be sure to not offend anyone's belief system. You could say something like "Let's assume for the sake of argument that 'Adam & Eve' is true. Under that assumption, how could we resolve the dilemma of our self-referential definition?"

The important aspects of this exercise are (1) that students discover that self-reference need not be irresolvable if a base case can be identified and (2) that students realize why the self-reference moves them closer to this base case.

To help emphasize the importance of developing a base case and moving closer to it in self-reference, showing students a collection of Russian dolls works well. You could even ask students to use self-reference to formally define the notion of a Russian doll or a collection of Russian dolls. These definitions will no doubt lead to some interesting discussions of what the base case should be.

The ideal instantiation for the goals of this resource would avoid the religious overtones of the human definition described above. At the same time, it should not offer students a simple non-recursive alternative. This drawback arises in the instantiation that employs a self-referential definition of an integer. Students may argue, "I can define an integer as a non-empty string of digits, so why do we need this self-reference stuff?" We have not yet found the ideal instantiation -- contributions are welcome.

Their first exposure of students to non-linear recursion (that is, recursive algorithms that involve more than one recursive invocation at each level) should help convince them that, for the algorithm developer, recursion leads to easy and natural solutions to tough problems. However, despite the power of recursive techniques, students need to understand that recursion is not "magic". Their having an understanding of how it is implemented with the system stack will allow them to gain confidence in its use. This understanding will also make them aware of the potential cost in time and space of recursive solutions to problems

The problem chosen for discussion should involve an elegant recursive formulation and yet be very hard for students to solve without recursion. It should also allow a detailed trace of its execution pattern. Ideally this trace can be carried out in fashion that allows students to play various roles such as the system stack keeper, the output device for the recursive algorithm, the scribe who must keep track of the current state of the algorithm, and so forth.

One problem suitable problem for this resource is the classic Towers of Hanoi problem. An appropriate solution to the problem is a listing of each move that must be made to carry out the entire transfer of disks from one pillar to the other.

A second problem to use is the production of a fractal using a pattern such as the Koch triad. At its base level (that is, level 1) the Koch triad appears as:

Fractal generation may be parameterized in terms of (1) a LOGO-like drawing turtle, (2) the number of levels to which the fractal is to be produced, and (3) the length of an individual line in the fractal. The level 2 and level 3 Koch fractals appear as:

With the Towers of Hanoi problem, use a physical representation of the problem, so that students can play out their proposed solutions. Try developing the solution from the base case upward. That is, ask students what the solution would be if there were only 1 disk. Then, ask for the moves to solve the 2-disk instance of the problem. Have a designated student carry out the proposed list of moves with the physical props. When you ask for the list of moves for the 3-disk instance of the problem, during the course of carrying out its solution students should observe that it involves two instances of the 2-disk problem with subtle changes in the roles of the pillars. (If students don't notice this themselves, be sure to pause to make the observation for them.) Having observed that the 3-disk problem involves two instances of the 2-disk problem, get your students to generalize to a pseudocode solution to the n-disk version of the problem:

1. move n - 1 disks from source to intermediate,
1. then move one disk from source to destination,
1. then move n - 1 disks from intermediate to destination

Once you have a pseudocode version of the algorithm, illustrate how the actual execution of the algorithm would progress using a stack to keep track of parameters at each level of recursion. Paper plates work well as a prop to use for a representation of the stack. One student can write the necessary parameter information on them while other student takes care of pushing and popping them as the algorithm progresses.

You need to be careful when getting students into role-playing a detailed execution trace of a non-trivial recursive algorithm. Choose the parameters for such an exercise in a fashion that guarantees you can finish in a reasonable amount of time. You must also emphasize, that although such a detailed trace is useful to gain insight into why recursion works, students should not rely on it as a debugging technique when they actually develop programs that employ recursive techniques. They will be much better off if they carefully develop a recursive solution to the problem and then use induction to prove it is correct. Then, by definition, their program cannot contain a bug!