Fun way to teach algorithms

Question

I will teach algorithms for 4 days for some students. It will be their first course in computer science before learning coding with Java.

My fear is to bore them as I was bored at the university :(

Is there a fun way to teach algorithms ?

Answer 1

I think this is hard to do in four days. You can barely touch the surface. I think that the most you can likely do is give them an appreciation for why the study of algorithms is useful and important.

There is one general sort of algorithm that is "easy" to carry out before students learn to program: Linear Recursion. There are many such problems. The basic idea is that one student "plays" the base case in the recursion and others "play" the recursive case. A simple example is counting the length of a list. The base case, when asked "how many" replies "one". The others, when asked "how many" pass the same message to the student in line to their left and if told, say, five, by that student, replies six. The professor lines up the student and asks the first student "how many". If it happens to go to the base case, the prof gets "one", but otherwise the message gets passed down and reflected by the "base case" and (after a lot of noise" gets back the length of the list.

A similar thing can be done. I've held "choir practice" with a bunch of students where each student has a script. The overall script is to recite "There was an old lady who swallowed a fly", which you can find on the net.

I've also had success with Matryoshka. How do you "paint" a Matryoshka? You can "apply color" to a given figure before the recursion or after. You can even "apply" color to the bottom on the winding phase and to the top on the unwind. The recursion is either (winding phase) "apply color, pass paint" or (unwinding phase) "pass paint, apply color". The base case just applies color and returns. This is an important lesson for students, that you can "do work" in a recursion on both the winding and unwinding phase. Some students miss this essential idea.

---

Another general area that can be explored prior to learning programming is the idea of sorting and what is required to do it. There are a lot of subtleties that are usually glossed over but that can be explored before you even start to program. For example "How do you sort the numbers 1 through 10 numerically". Answer, you don't. They are already sorted.

You can ask "Why do we want to sort?". Connecting it to the search problem and a real-world scenario and maybe even binary search.

Another subtle issue is the distinction between the size of the multiset (bag) that you are sorted and the size of the set of values from which they are drawn. For example, sorting a list of int or long values can always be done in linear time (linear in the size of the bag, length of the list). This is because the collection of expressible long values is finite. See Radix Sort for example. In general, sorting (mathematical) integer values is harder, since the set of integers is infinite even when the bag to be sorted is finite. Radix sort can be carried out by a group of student "actors", if you either discuss binary representations, OR, adapt the algorithm of a mechanical sorting machine to use human actors.

Another fun thing to do with sorting is to try to have a competition for the least efficient sorting algorithm anyone can come up with. I can think of some doozies that are either extremely inefficient in space or in time. I have a completely infeasible sorting algorithm that is linear in time but requires too much space. Other inefficient (in time) algorithms are possible. For example, randomize the list and then check. Repeat until sorted. If you have a truly random number generator this is guaranteed to halt (law of large numbers in probability). There are a lot of possibilities.

---

In my first reading of the question here, I somehow completely missed the fact that the students didn't know anything about programming (oh my). If they do, then the following might be appropriate, but they would be hard to do otherwise.

One "interesting" algorithm is just Huffman Encoding. How do you minimize the number of bits sent to encode a message using an alphabet with a given frequency of use. There are several things that need to be discussed here, including the economics of data transmission. "Less is More". Then there is the question of the alphabet and its characteristics in use. See Poe's The Gold Bug for a discussion that is actually incorrect, but interesting and has the right idea if the wrong numbers. Don't be naive and try to use the distribution of the message itself as the source of statistics on the alphabet. It can't work.

Next you need to discuss tree structures, etc, and the bit encoding of the message, including the need to be able to separate the message into discrete characters, since the encoding doesn't use the same number of bits for each character (the essence of the problem, actually).

Note also that even a naive but accurate distribution provides some improvement. Huffman is optimal for a given distribution. So, discuss optimization, as opposed to satisfaction.

Now you need to discuss and maybe implement both the encoding and the decoding algorithms.

Then you can discuss space time tradeoffs. We trade time (for encoding/decoding) for space (bits sent).

An "overnight" thought experiment for the students: Why can't you use the message itself to determine the distribution? It takes a bit of thought and may be obvious or not. But a long discussion here previously showed why it can't work.

You could even spend a bit of time on the difference between linear scanning of a set of data and searching through a tree that has been previously constructed. This could get you close to something like binary search to put a "future work" idea in their minds.

There are other similar examples. The key is a problem in which the naive solution (same number of bits per character) can be improved (fewer bits for common characters), then showing how to develop the algorithm to do the improvement.

One problem I find magical is the Dutch National Flag as discussed at the link and the book by Gries. A linear time sorting algorithm for a restricted kind of data. Since DNF only involves an array and a few index variables, it can be done with students as "actors" representing the Red, White, and Blue values. A few other actors (index values) point at the corresponding "slot" in the array to keep track of the algorithm as it progresses.

I think other algorithms that use an array or list can be handled similarly, but it is probably necessary to stick to linear running time algorithms. That is just because time is limiting and little insight can be gained if the thing is too complex or takes so much time that the details obscure the main points.

Answer 2

A loaf of bread, a knife, a jar of peanut butter and a jar of jelly. Write an algorithm to build a PB&J. Have one of the kids follow the literal direction written by a different kid. This project have been a favorite starter for algorithms for 30 years.

Answer 3

A crowd favorite of the Beauty and Joy of Computing (BJC) course from Dan Garcia and many other creative leaders:

Each group of 4 students gets a deck of shuffled playing cards. Groups race the clock to deliver the deck in sorted order, ace to king within suits, suits alphabetically. BJC uses that activity first.

I had interesting results one year using that activity later in the semster, and modifying it: each group gets two distinguishable decks shuffled together, one of them missing a card. Race the clock to identify the card I retained from your group.

Either way, athe key is the post-race discussion. What algorithm did your group follow? What is the best algorithm? Does the answer to the previous question depend on how well the deck is shuffled? Does it depend on which card is missing? Nice tie ins available to complexity and worst case time efficiency.

Answer 4

Do I understand correctly that you're teaching kids already that have not yet learned any programming? And that you are trying to teach them algorithms?

I would not focus on a programming language at all; they are not ready to implement algorithms yet in actual code. Instead, I would focus on Computational Thinking. Let them act out various approaches to solving a problem and turn them into recipes.

I would look at ice-breaker games and at resources for Computational thinking for nice, active learning ideas to get at algorithms without all of the cumbersome programming at the start.