By the end of this lesson, you will be able to describe the 3 key stages to solve a computational problem.
Welcome to this first lesson, in which we will talk about how to deal with a computational problem, and the necessary steps which you should follow to solve it.
The three steps
When faced with a challenging computational problem, it’s sometimes tempting to start programming right away.
While many students might feel like they’re not making progress if they’re not writing lines and lines of code, this just isn’t true. If you wanted to build a house, would you start stacking bricks right away?
So, each time you’re faced with a computational problem, there are three consecutive steps which should be followed: formalize, specify, and code.
To formalize means to express a problem using adapted terminology and concepts.
In this course, we’re going to program an AI to play a game in a maze. So the first step will be to understand how to represent and manipulate mazes.
To do so, we will refer to graph theory, which is a common mathematical framework that helps us to formalize numerous problems.
Programmers that overlook this formalization step are likely to encounter unexpected issues. In simple cases, this could simply delay their work. But in more severe cases it could mean that all the work produced so far is useless, and that they need to start again from scratch.
Once a problem has been correctly formalized, it’s time to specify a solution.
To specify means to identify algorithms or methods that are well suited to solve the formalized problem.
For example, in this course, the AI that you will implement will have to move around in the maze. Therefore, we will discuss methods to find a shortest path in a graph.
Specifying is of paramount importance, and allows us to make the right choices with consideration to the problem at hand. Specifying also reveals the global structure of the solution, which facilitates team working situations, in that all individuals are aware of exactly what they are expected to do.
Finally, once the problem is specified, it’s time to start coding.
Coding should always be the last step in solving a computational problem.
Coding should be quite straight-forward if the formalization and specification steps have been correctly completed, and should follow on smoothly from the specification step.
Debugging a program
In an ideal world, your program would do exactly what you want, i.e., realizing the algorithm it implements, hence solving your problem. However in practice, writing a program is a hard task.
There is a wide variety of ways to ensure a program works as intended (or at least try to). Here are some examples:
- Handmade debugging;
- Unit tests;
- Program provers;
Here, we give a small list of rules of thumb to help you debug your programs as you write them. More complex approaches will be presented in other courses you may follow later in your engineering studies.
Do not wait to finish to run your program
Writing a non-trivial program takes (at least) some dozens of lines of code. A good way to ensure you are writing something that will be functional is to execute your program everytime you finish writing a few lines.
At the very least, this will help you check that all your variables are well written, since the Python interpreter will crash if you use a variable
my-variable after defining
my_variable (note the difference between – and _).
Don’t hesitate to use the
print(dir(my_variable)) gives information on the functions and attributes of
print(type(my_variable)) will show the type of
Test on controlled examples
You are writing a program for computing the number of elements in a list? Do not trust your function until you have run a couple of times on handwritten lists for which you know the answer, especially on extreme cases (an empty list for instance).
Go*gle your problem
Python provides error messages that are in general quite clear. However, if you do not understand the cause of the error, you can simply copy-paste the error message in your favorite search engine. There is a very high chance somebody has already encountered the same problem, and a nice person on StackOverflow already explained it.
Sometimes, you want to write something complex (say, replacing all letters A in a text with a *), and start doing everything from scratch (here, iterating over all letters to check characters individually and build a new string), taking you several hours of hard work. However a function to do what you want is already available in the official Python documentation and could have taken you 5 minutes to find.