How to teach algorithms: implementation or application?

Question

One unit of CS50 AP's curriculum focuses on three main sorting algorithms: bubble sort, selection sort, and insertion sort. There is also discussion of something more efficient like merge sort. One programming assignment has students write the code in C to each of the three "simpler" sorting algorithms. Students get clear pseudocode of how each works, but they are left to work out the code on their own.

In contrast I just started working through Princeton's excellent Algorithms course on Coursera (Algorithms, Part I). The first unit there focused on quick find, quick union, and weighted quick union. The algorithms -- both in pseudocode and in Java -- were given by the instructor; the programming assignment (Percolation) involved the correct use of weighted quick union. Rather than implement it, I just had to apply it with the provided class WeightedQuickUnionUF.

Similar to the Princeton course, the AP CS A curriculum teaches sorting algorithms but only use thereof, not direct implementation (e.g. students are not expected on the exam to write insertion sort from memory). Instead, students have to understand it and be able to trace through steps in the sorting process.

So there seem to be two approaches here (not limited to just sorting algorithms): teaching the challenge of coding an algorithm from scratch (via implementation) vs. giving students the algorithm to apply to a particular problem (via application).

Is there a significant benefit in having students attempt to implement an algorithm from scratch? If so, is this the more effective approach for teaching?

Answer 1

The answer here, as it seems to be so often, is "it depends." The courses you've compared are comparing apples to oranges. Which are you trying to make, apple juice, or orange juice? You have to select to version implementation or application, which best moves the lessons, and the students, toward the objectives and goals set for the course.

The Apples

---

Coursera (AP CS A): The students are provided the finished algorithms and expected to apply them properly to solve some larger problem. The emphasis is on solving the problem with the given tools, not creation of the tools. All the coding, by the student and supplied to the student, is done in Java.

• Target

  • Java
  • Object-oriented methodology
  • Problem solving

• Pros

  • The students have a firm foundation in Java and are ready for 2nd semester college courses employing Java
  • The students can understand, and use, the object-oriented programming paradigm common in most newer development models.

• Cons

  • While students will have more to learn in Java before using it professionally, they will need to return to the beginning to switch to a different language.
  • The students will have a good grasp of using existing implementations of common algorithms, yet not have the skills to develop new algorithms to solve problems they don't know about yet.

The Oranges

CS50 AP (AP CSP): The discussion leads from comparing the algorithms to see how they do what they do, and probably the costs of doing it each way, to creating the code that will actually do that sort. The clear pseudo-code that they are given the programming assignment was presumably developed during the discussions of the algorithms, and is merely repeated in a concise format for them to convert to C code. They are learning how to conceptualize the objective, work through creating the algorithm and carry that into live code.

• Target

  • Computational thinking

• Pros

  • The student have a firm foundation for implementing new algorithms, as well as an understanding of how to apply current, and new, algorithms
  • The students are equipped with an understanding of how to apply computational thinking to solve new and unique problems not yet reduced to algorithms

• Cons

  • The students may have used a language which is not used in later courses, so they will have learn a new language to continue with programming courses -The students may not have been exposed to, or practiced much with, the object-oriented approach.

Answer 2

At one time there was no such option. Working programmers had to implement and re-implement algorithms as part of daily work. That wasn't so long ago, actually. Then the idea of Templates came along and also the development of large standardized template libraries such as the Standard Template Library (STL) of C++ and the java.util library. Today, then, working programmers do different things, for the most part, while utilizing standard solutions.

So, the answer, today, is that learning to build every common algorithm (and data structure) is less important than it once was.

However

The library will eventually fail you. Either times change and new algorithms need to be used for new problems, or you start work in a language with a less well developed set of libraries, or ...

If you have never built a complex and intricate thing that provides a seemingly simple service, you will be lost. The STL is as intricate and beautiful as a fine Swiss watch. You learn a tremendous amount just from reading (and trying to understand) parts of it. But even more from trying to build a moderately faithful clone.

So, a combination approach is probably best. A good algorithms course can now focus more on principles than implementations. It can also, possibly, spend more time on applications than implementations. But implementations should not be entirely neglected. There are several reasons. Sometimes you need a specialized version of some sort of map, say, for optimization purposes. The building of algorithms and data structures is also just good programming practice in general, such as programming to a given interface and building things that interoperate smoothly with other things.

Personally, I would now list Principles, Implementations, and Applications in that order of importance, raising the importance of Principles from what was taught in the past, but with more emphasis on Implementations than Applications. Others might switch the last two and justify it.

People don't much build hot-rods anymore as they did when I was young. Cars today are more complicated than can be built by amateurs. A hot-rod built today is much less sophisticated than the Toyota I drive. But someone who builds a 1950s street-rod from parts, and customizes, it learns a lot of things about engineering that others will not.

Algorithms are, in general, extremely interesting and building them teaches a certain way to think about programming. It is a good place, maybe the best, to talk about pre and post-conditions and invariants. It is a good place to talk about the elements of computability and its effect on efficiency. These are lessons that are not especially likely to be learned if students don't implement. Some relatively obscure algorithms are interesting in their own right, say Dutch National Flag, and Dijkstra's Longest Upsequence algorithm. The solutions can be somewhat non-intuitive, but enlightening when explored.

Besides, it is fun.

Answer 3

Expecting someone to implement a particular sorting algorithm from scratch, is an impossible ask. You are asking them to invent a sorting algorithm, and be lucky that it is the correct one. (Or to already know it.)

I took in some cards, and asked groups or volunteers to sort them. I then asked them to have one person to do the sort, and a 2nd to document what they did. To then write them as instructions (this is pseudo-code). Test and revise them, and then get another group to follow the instructions, to sort some card. After feedback from the other group, to revise and test once more.

I then looked to see how they did it (What sorting algorithms had they discovered), and give them the names of the algorithms.

Latter I would get them to implement some of them in code, using the pseudo-code as a guide.