The topic of this lecture is problem-solving. You might say, “What a vast topic.” True. It’s such a general term that we certainly can’t associate it only with computer science. Certainly, mathematicians and physicists have been using this term for decades. There is a very famous book, “How to Solve It” by George Pólya, which describes a series of methods for solving mathematical problems. Take a look at the Wikipedia page dedicated to the book.
n the field of computer science, when we refer to problem-solving, we often refer to the concept of stepwise refinement, which was promoted by Wirth in a famous article:
- Niklaus Wirth. Program Development by Stepwise Refinement. Communications of the ACM 14(4):221–227 (1971)
It’s such a classic that you can’t help but know it. Unfortunately, this article is older than me (by three months) and it shows, in terms of style. Therefore, I ask you to at least take a look at the introduction. If you want, you can tackle it more calmly later on. Alternatively, explore the web looking for “stepwise refinement” to try to understand how this technique is described.
Following Wirth’s article, most textbooks dealing with programming talk about this technique, perhaps referring to it as a “top-down approach”, often proposing examples of its application. Elliot Soloway, however, makes a very accurate criticism of this inductive approach, then promoting his vision based on programming plans that we have seen talking about the role of variables and programming patterns.
- Elliot Soloway. Learning to Program = Learning to Construct Mechanisms and Explanations. Commun. ACM 29(9): 850–858 (1986)
Leggete la parte evidenziata in giallo (critica) e la parte evidenziata in rosa (proposta). Se poi volete, affrontate con calma l’intero articolo per rivedere i concetti della lezione su PRIMM.
Read the part highlighted in yellow (criticism) and the part highlighted in pink (proposal). If you want, calmly tackle the entire article to review the concepts of the lesson on PRIMM.
Some have tried to “jot down” some rules, similar to those of Polya, to tackle problem-solving in the computer field:
- Jorge Vasconcelos. Basic Strategy for Algorithmic Problem Solving.
At this point, I ask you to reflect on your process of solving programming problems. I’m not talking about complex programs (the size of our course projects), but simple tasks that can be proposed to students.
As an example, I propose a series of problems found in textbooks for Scientific High Schools — Applied Sciences:
- Choose one
“Slow down for a moment” and try to solve it not all at once, but by trying to use stepwise refinement techniques; compare with Vasconcelos’ questions. - Try to reflect on how you would present the problem to students
Here’s the list of problems:
- Write an algorithm to print n rows of Pascal’s triangle
- Write an algorithm to determine if a number n is perfect (it is equal to the sum of its divisors)
- Write an algorithm that converts a decimal number n into its equivalent in binary, hexadecimal, octal
- Write an algorithm that prints all the numbers that appear more than once in an input vector
From our mathematics/physics students, I would be interested in having a discussion on how the topic of problem-solving is approached in their fields.
Additional reading
In addition to the material presented, an article that addresses problem-solving from a more general point of view is the following
- D. Jonassen. Toward a Design Theory of Problem Solving. Educational Technology Research and Development, 48(4):63–85 (2000).
Materiale lezione
- Slide presentate durante la lezione [Link]