Video transcripts
Welcome to this first lesson, in which we will talk about how to deal with a computational problem, and the necessary steps that 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? I don’t think so.
So, each time you’re faced with a computational problem, there are three consecutive steps which should be followed:
- formalize;
- specify;
- code.
Formalize
To formalize means « to express a problem using adapted terminology and concepts ».
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.
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.
Concluding words
This concludes today’s lesson. You’ve learnt today that, when developing, it is best not to start coding right away, but to first think a bit about how the problem is formalized, and how a solution is specified.
In the next video, you’ll learn about graph theory. See you soon!
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.
