Contents of the page


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.

Formalize

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.

Specify

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. 

Code

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;
  • etc.

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 function extensively in order to examine the state of your variables upon execution of the program. In particular, print(dir(my_variable)) gives information on the functions and attributes of my_variable. Additionally, print(type(my_variable)) will show the type of my_variable.

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.

RTFM

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.


To go further

  • Unit testing: A systematic method for debugging a program, by checking your new modifications do not impact what worked before.
  • A small presentation of Coq: A few words on solutions that exist to prove computer programs, as one would prove a mathematical theorem.

Quiz

The three consecutive steps that should be followed when faced with a computational problem are...
To formalize means...
To specify means...