Lecture 1
Lecture 1ΒΆ
You might have already noticed that a given problem can be solved in many different ways: programs that calculate the same thing can be very different! It is important to understand that different ways of solving a problem can have dramatic consequences for how usable your program is. We present two problems, different ways of solving them and we try to understand in what way a given solution can be considered better than another one.
In this first lecture we present our first example: calculating prime numbers smaller than or equal to an upper bound. We present you with two very different solutions and in both cases we delve into some details that improve the performance of the programs.
We present one more example: multiplication of natural numbers. Again you get to see two very different algorithms and delve into details that improve the performance of our programs.
We hope to illustrate that the question Can we do better? (the motto in the book Algorithms Illuminated) is important and has consequences for the programs we write. Finally, we want to convey that programming is not just about knowing how to use the constructs of a given programming language, but that there are well known methods to come up with better programs (one of the purposes of the course).
The programs in this lecture use integer
numbers, lists, for-loops and if-statements. We include a section
reviewing for loops,
but if you need to review other programming components we use we recommend that you check
A concise presentation of Python
where there are chapters for statements (commands) formed
with for and if as well as chapters for expressions using
lists and integer numbers. The lecture also makes use of recursion and
we include a section explaining recursion. We use list and array
as synonymous in Python.
Note
A piece of advice.
If you look at the top right of this page you will see a download icon. If you hover over the icon you will see that it suggests two choices: .md and .pdf. This means that you can download the source in Markdown or a printable in pdf.
If you do the same in the next section (Understanding for loops)
you will instead get the options: .ipynb and .pdf. This means you can
download the source as a Jupyter notebook or a printable in pdf. I
really recommend you to download the Jupyter notebook so that you can
run all of the code and advance your understanding by making changes and tinkering
with the code. Whenever you wonder something, test it! If you run into
problems, ask your teacher!