Problem solving vs. career training
Two perspectives on CS education from the 1970s
In my previous post, I described the three purposes of college given in Andrew Delbanco’s book College, and I explored what each of them suggests we should teach in a computer science curriculum.
Let’s continue to explore this question — what should we teach? — by looking at the following two papers on introductory programming from SIGCSE, the primary venue for research in CS education:
David Gries (1974): “What should we teach in an introductory programming course?”
G. Michael Schneider (1978): “The introductory programming course in computer science: ten principles”
Both papers received the ACM SIGCSE Top Ten Symposium Papers of All Time Award.1 Among the ten winners, these two are easily the oldest (the third oldest was published in 1997). In this post, I’ll summarize each paper and end with some thoughts.
1. David Gries (1974): “What should we teach in an introductory programming course?”
The paper opens directly:
An introductory course (and its successor) in programming should be concerned with three aspects of programming:
How to solve problems,
How to describe an algorithmic solution to a problem,
How to verify that an algorithm is correct.
It focuses on the first two items, because “if the first two are carried out in a systematic fashion, the third is much easier than commonly supposed.”
Problem solving
A programming course is unique because “it is the only course taken by a large percentage of all students, which tries to teach general problem solving methods.” Even a math course only covers solutions to certain classes of problems, not general methods. In contrast, a programming course teaches knowledge that can be applied to other courses, such as math, physics, and even English.
Unfortunately, despite its importance, we (CS1 instructors) don’t teach problem solving. Instead, we show the tools (e.g., loops, conditionals) and give examples, then we tell the students to write programs. That’s like if an instructor of a cabinet making course showed the tools (e.g., saw, hammer) and a finished cabinet, then told students to design and build their own cabinet in the next few weeks. Without proper instructions, guidance, and feedback, students would flounder.
Fortunately, people like Descartes and Pólya have developed valuable ideas, even if they might seem like “wise old sayings and clichés without any value.” For example, Descartes recommends that we “divide each of the difficulties into as many parts as possible,” and Pólya thinks of problem-solving as a four-step process: understand the problem, devise a plan, carry out the plan, look back. We should teach problem-solving concepts like these; we shouldn’t leave them in the dark.
Describing algorithms
Gries claims, “Algorithms written in programming languages are usually difficult to program, read, and understand.” There are several reasons; one is that when we write in a programming language, we need to specify a bunch of details that we’d usually omit in regular speech. So what can we do to make algorithms more understandable?
Restricting ourselves to a simple set of statements would be a good start. The paper describes and advocates for a dialect of pseudocode (without using the word “pseudocode”). It then comments on the three major programming languages at that time: Fortran, BASIC, and PL/I. He’s harsh on the first (“completely out of date”), harsher on the second (“should never have come into existence”), and relatively generous toward the third (“if we stick to its simpler features, the language is usable”).
Gries is not a fan of flowcharts; he prefers organizing code in a top-down fashion using indented blocks (similar to Python) that iteratively refine each large step into smaller steps:
He then observes that “[o]ne of the hardest tasks for an instructor is to grade students' programs” since it’s important to provide detailed comments not only on correctness, but also structure. Not surprisingly, he’s sure that teaching 15 students (rather than 150) would produce better programmers due to the increased individual attention. Unfortunately, he doesn’t elaborate on potential solutions. In fact, he’s pretty pessimistic at the end of the paper. He claims we need to “educate programmers in a different manner, and to re-educate the old programmers,” but adds, “I am not at all sure that any drastic change will take place in the Universities within the next few years, although I hope I'm wrong.”
2. G. Michael Schneider (1978): “The introductory programming course in computer science: ten principles”
“Students should immediately be taught that a clear, concise problem statement is always the first step in programming.” Real problems aren’t as well defined as problems that students get in school, and to address this gap, “some programming assignments should intentionally be left incomplete.”
“The single most important concept in a programming course is the concept of an algorithm.” Thus, the beginning of an introductory course should be about algorithms: sorting, searching, merging, etc. It’s fine — perhaps more than fine — to start writing code after 30-40% of the way into the course. After all, coding is just a “mechanical translation” process. Schneider, like Gries, prefers simple, indented blocks to flowcharts.
“It is important to introduce the duality of data structures and algorithms in the programming process.” Data structures are just as important as algorithms, and they should also be taught in a top-down fashion.
“Choose a programming language that enhances the learning process.” The language should be both rich and simple; Schneider’s preferred language is Pascal.
“The presentation of a computer language should concentrate on semantics and program characteristics not syntax.” Things like organization, readability, and efficiency should be the focus of class time.
“The presentation of a computer language must include concerns for programming style from the very beginning.” Again, Schneider agrees with Gries: instructors shouldn’t only care about correctness; programs should also be “well written.”
“The subject of debugging should be formally presented.” Students should learn about syntax, run-time, and logic errors, as well as tools (e.g., reference manuals, print statements, dumps). They should not develop bad habits such as adding code without thoroughly thinking through the problem. Ideally, they’d be careful enough to avoid bugs in the first place.
“The subject of program testing and verification should be formally presented.” Schneider thinks it’s “inappropriate” to discuss proofs of correctness in an introductory course. Instead, he prefers to thoroughly test on a set of inputs and detect errors later. This leads to the topic of program maintenance, “a term frequently omitted from introductory courses but which is a fundamental concept in programming.” Again, for students to gain “practical experience” (see Principle 1), instructors often shouldn’t give test cases with the assignments.
“The subject of documentation should be formally presented.” Documentation should have guidelines depending on the audience, and it should be written during program development, not afterwards.
“A student should be introduced to realistic programming applications and realistic programming environments.” Ideally, an assignment should be challenging, insightful, and realistic. And the environment should be realistic too: students should work with “a large, existing program that is totally unfamiliar to the student.” At least one assignment should be a team project, done in a group of 3-5.
3. Thoughts
Gries and Schneider both
think algorithms are fundamental to introductory programming,
prefer indented blocks to flowcharts,
believe the choice of programming language is critical, but advise against getting caught up in syntax and such at an early stage,
value code quality, not just correctness.
It’s 2023, and I agree with these points. In algorithms courses, we often take some of these ideas even further by avoiding (machine-interpretable) code altogether. Students can write in pseudocode or even just plain English, which allows them to focus on the logic of the algorithm and safely ignore implementation details. It also forces them to present the algorithm clearly. Since they’re assessed by a human reader rather than a set of test cases, presentation matters.
But at a higher level, Gries and Schneider seem to have different philosophies about the purpose of an introductory programming course. Gries seems to think of programming as essentially a branch of applied mathematics. He thinks CS1 should focus on solving problems that have “an algorithmic solution” such as “sorting, solving linear equations, drawing a graph on the line printer, ‘translating’ English words into French, approximating π by a series, making a concordance, and so on.” It seems that for Gries, the main purpose of writing programs is to solve real instances, but programming education should not necessarily focus on real instances. Algorithmic problem solving is a skill worth teaching, perhaps even if computers didn’t exist.
On the other hand, Schneider places a greater emphasis on the direct impact of CS education on students’ future careers as programmers. He wants students to develop good habits regarding style, debugging, testing, and documentation, because that would “lead to high-quality software.” For the same reason, he thinks instructors should provide realistic situations in their classrooms. He even gives the following anecdote: “(One of our colleagues suggested, not completely in jest, that to truly provide a realistic environment at least one assignment should be cancelled entirely after 2/3 of the work has been completed!)”
I think it’d be fair to say that Gries’s vision of an introductory programming class mostly falls in the “liberal arts” perspective mentioned in my previous post, while Schneider’s vision seems more aligned with the “economics” perspective. Fortunately, most college CS programs are big enough to encompass both visions: some courses teach theoretical topics while others teach applied topics. In fact, many topics (e.g., data science, cryptography, optimization) straddle theory and practice, so it’s up to computer science departments to find an appropriate balance.
The name of the award could be misleading, since the SIGCSE symposium has continued to take place annually.