How to effectively teach pseudocode

Question

I'm helping with an algorithms course next term. I've taught intro programming courses and seminars, but never intro algorithms. I've spoken with previous TAs and instructors, and one of the biggest problems they face is student assignments -- both on the writing and grading side.

The course is more or less abstract (no concrete implementation assignments). While you can argue whether or not this is ideal, it's the hand I'm dealt. This means that pseudocode is heavily important -- in fact, it goes into linear programming quite a bit and handwaves a large number of details on things like "actually efficiently finding a feasible point/local optimum" for simplex and such.

This leads to two major problems: students don't deal with a suitable level of abstraction. They tend to refuse to consider "black boxes" even if they're used in class. While wanting to know details isn't wrong, and if you want to use the algorithms in real work it can be a big deal, it can lead to actually doing the assignments being intractable. Especially when the efficient algorithms they should be black boxing for certain purposes are either complex, open problems, or something they shouldn't need to reroll (sorting algorithms after the sorting section is covered).

On my end, it also leads to grading hazards. I've seen past assignments, and they tend to be very dense, boilerplate ridden, implementation detail-considering chunks of copy+pasted Java or C++ code. Some of this is simply poor coding practice, and would be an issue even with pseudocode, but it's absolutely clear that pseudocode solutions would be shorter (often by several pages) and easier to read and understand.

However, attempts to teach pseudocode tend to leave students confused. They (perhaps understandably) shy away from black boxes, think their Java code is self evident, or think "real code" is inherently better because it can be run. They don't embrace the terseness and magic-of-convenience of things like "sort x ascending by length" and instead rely on verbose comparator implementations. How can I effectively communicate the benefits of pseudocode in abstract algorithms and data structures contexts for both my and their sanity?

(Quick disclaimer: while this is a real question, this is also partially to test how the community feels about erring on the side of inclusiveness on computer science and programming as mentioned in this meta discussion)

Answer 1

Here are a few ideas, which may or may not fit into your course.

1. To start with, would it be possible to build an explicit pseudo-library of black box pseudo-functions and pseudo-operators that they should feel comfortable using? After they have used this library for a few assignments, they may feel more comfortable creating their own black-boxes. I remember feeling lost when concurrently taking maths courses from different year levels, and it was hard to know what theorems were allowed to be used in proofs, so I proved too much using only basic theorems. It would have helped to have an explicit "library" of theorems from each year that I could use in my work.

2. If they think Java or C++ code is in any way self-evident, they have a lot of unlearning to do. Maybe they should be forced to write in a scripting language for the first 1-2 weeks of the course. You could have appropriate high level libraries available for the required tasks, so they are forced to write in abstractions. Pseudo-code would be the next step of abstraction that they move to.

3. For the first assignment, you could present pseudo-code as part of a rapid algorithm development process, enabling the rapid communication and evaluation of algorithms. They could have a project that actually enforces a pseudo-agile development process, with several iterations of algorithms and maybe also enforcing pair or group work - emphasising the communication aspect of pseudo-code.

4. After their pseudo-code rapid algorithm development process, they could even create a real program from the pseudo-code. This would help them see that pseudo-code is a valid part of real computer science, not just mathematics. (Not using mathematic pejoratively, but the reason many do programming rather than mathematics is that they like to make things and see things work). This would only be one program for the first assignment, just to "sell" pseudo-code as a useful language that leads to real results.

Anyway, I hope one of these is useful.

Answer 2

While I have never actually taught pseudocode, my experience as a math teacher and a computer science student might provide some insight.

On the exam for an object oriented programming courses the prof asked us to write a piece of pseudocode, and was chagrined that most students (including myself) chose to write out the full C++ code, since he, like you, had been using pseudocode in class. Challenge lay in that he had used pseudocode, but he had never explicitly taught it. This is similar to the way that most college math classes use proof, but do not explicitly teach students how to write a proof. This reflects the tension between content (object oriented programming, real analysis) and skills (pseudocode, proof).

It might be helpful to discuss different representations of code (specification, pseudodcode, code) and ask students to "translate" between representations. To do this you might give students an example of pseudocode and ask them to translate it into a specification or actual code or you might give them code or a specification and translate it into pseudocode.

As a more general comment, students learn all sorts of bad habits when the correct answer is valued more the process. This is endemic in computer science courses where high value is placed on having functioning code rather than well written code. Just because you can't run tests on code that does not compile, but that does not mean that the code is worthless in terms of the ideas it represents. If the classes don't value the process part of code writing, then the students certainly won't.

Answer 3

This leads to two major problems: students don't deal with a suitable level of abstraction.

Finding the right level of abstraction for a problem is a major challenge. It takes enough knowledge of the subject not to get bogged down in details, and a lot of experience generally. You can't expect students to easily navigate between levels of abstraction. They can't know which details are actually important and which ones it's safe to skip over. Even professional mathematicians sometimes get it wrong, which is why some complex proofs take a while to review and to build confidence in.

Actual programming languages with formal rules provide a concrete anchor: if it isn't in the language, it needs to be defined. Mathematical language is also defined formally enough to express proofs, but for algorithms it has the same ambiguity as pseudocode: it doesn't distinguish between what is algorithmically trivial and what is easy mathematically but not constructively.

You need to give very solid guidance as to what can be treated as a black box and what needs to be spelled out. Choosing a programming language has the advantage that it provides a formalism for black boxes: it's a function that students don't need to write by themselves.

it can lead to actually doing the assignments being intractable. Especially when the efficient algorithms they should be black boxing for certain purposes are either complex, open problems, or something they shouldn't need to reroll (sorting algorithms after the sorting section is covered).

You need to make it clear to students what they may assume and what they have to write! If you want them to skip over some difficult problem, that absolutely needs to be made explicit. In the assignment, list out what students may assume. If you don't want students to reroll a sort algorithm, specify something like “assume that all classes have a compare method and all arrays can be sorted by calling their sort method”.

If your students aren't mature enough for pseudocode, I don't think you should try to force them into it. Do keep insisting on readable descriptions of algorithms, and do tell them that you don't care about all the punctuation as long as what they write is comprehensible to humans. Tell them to stick to basic language features and not care about code reusability, so no need to wrap code in classes, no templates, no need to catch exceptions, etc.

Some languages work better than others: Python can often work pretty well as pseudocode, Java or C++ markedly less so. But if the students are only comfortable with writing Java, an algorithms course isn't the place to teach them something else. Provide experience in figuring out the right level of abstraction, but don't make it a course requirement. Of course, do give them the option to use English, tell them that they're more likely to succeed if they don't get bogged down in programming micromanagement. But some students will have a hard time deviating from the programming language they know, and that's ok.