8
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Regarding your first paragraph, I wouldn't be asking for them to invent it per se. Rather, I'd teach it (as I do) with some demos of each of the three sorting algorithms, so students "see" the process in action. I'd also give them the pseudocode logic. This sounds much like what you have them do in your second paragraph. My question though is whether I should then have them write bubble sort based on what they've just seen or just give them the code and have them start applying and analyzing it. $\endgroup$ – Peter Jul 27 '17 at 20:45
  • $\begingroup$ I like the idea of bottom-up and top-down. Therefore for this have them write it. But in other lessons give them bigger programs to edit. $\endgroup$ – ctrl-alt-delor Jul 27 '17 at 21:16
  • $\begingroup$ Regarding the first sentence, if it's such an impossible task, how come it's been done so many times by so many people before, many times as coursework? $\endgroup$ – Gypsy Spellweaver Jul 29 '17 at 15:47
  • $\begingroup$ @GypsySpellweaver “I want you to discover and implement insertion sort. It is a sorting algorithm. I can not tell you any more about it, as you must do it from scratch. If you hand in a solution for merge/selection/quick/bubble/any-other sort, then you will fail the unit.” (It probably depends on what you mean by scratch) $\endgroup$ – ctrl-alt-delor Jul 29 '17 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.