Elementary Algorithmic Programming in Python

I assume you have Python installed on your computer. Specifically, I assume Python-3. I also assume that you have some basic experience in using a command shell and a text editor. You may also choose to use an integrated development environment (with an integrated editor), but that is not at all necessary.

In essence, you should be able to run Python as an interactive shell, edit a Python program (as a text file), and run a Python program as a standalone program or within an interactive Python shell. Let’s review these preliminary skills by example.

Python supports numbers and basic arithmetic. Try it yourself using the interactive Python shell:

>>> 1 + 1
2
>>> 34 - 11
23
>>> 3 * 7
21

Easy. Makes sense. But did you try it yourself? Seriously, do it! As I said before, this is a read-do document. You should try every single example yourself. In fact, once you get the gist of it, you should invent and try more and more examples.

So, now you know that Python can read numbers, and can add, subtract, and multiply numbers. What’s next? Division. There are in fact three fundamental division operations we need to know about:

>>> 5 / 2
2.5
>>> 6 / 3
2.0

The division operator ’/’ divides the two numbers and always returns a floating point number. Sometimes, especially in programming algorithms that work on discrete structures, we want an integer division:

>>> 13 // 5
2
>>> 13 % 5
3

The integer division operator ’//’ does exactly that. So a // b gives you the quotient of a over b, meaning the whole number of times that b fits entirely in a. Correspondingly, a % b is the remainder of the integer division of a over b. So, both the quotient and the remainder are integers.

We won’t need any more numeric operations in the Algorithms course, really. Although of course you can combine those operators in long expressions, possibly grouping sub-expressions using parentheses. For example:

>>> 10 - (3 + 1)
6
>>> 27 % (2*(7 - 2))
7

Python can memorize values for you, so that you can later use them. For example, you can memorize the result of an arithmetic expression:

>>> x = 10 + 2*5
>>> 

The command x = 10 + 2*5 is an assignment. It looks like a mathematical equation, but that’s not what it is. What the equal sign really says is: first, compute the value of the expression on the right-hand side of the =, and then store that value in a memory cell called x. So, the command x = 10 + 2*5 does not itself produce an output or a result, but it does change the memory of the computer. In fact, now you can read the value of x:

>>> x = 10 + 2*5
>>> x
20

Notice that x is now a valid command that simply returns (reads) the value 20 stored in the memory cell named x. The Python shell reads and prints that value.

To reemphasize the idea of an assignment, as opposed to a mathematical equation, try now the following command

>>> x = x + 1
>>> 

Once again, the command x = x + 1 is not an equation—for which there would be no solution anyway—but rather an assignment, which says: compute x + 1, and then store the resulting value into a memory location called x. Now, x + 1 is an expression that reads a value from x, and the assignment then stores the value of the whole expression into x. You might think that that is weirf, but that’s perfectly okay. The value initially stored in x is 20 (from the examples above), so x + 1 is 21, so the value of x after the assignment command is 21. In fact, try these commands now:

>>> x
>>> 21
>>> x + 5
26
>>> x
21
>>> x = x + 5
>>> x
26

You can of course have many variables, and you can use them however you like in expressions. Now you have x whose current value is 26. What happens if you then run the following command?

>>> y = x - 21

Simple, you now have two variables—two memory cells—one named x that contains value 26, and another one named y that contains value 5. So, now you can write something like this:

>>> y = x + y - 1

What is the effect of that command? We know that it’s an assignment that first computes the value of x + y - 1 and then stores that value into y. To compute x + y - 1, Python reads the value of the x memory cell, then reads the value of the y memory cell, adds the two values, and then subtracts 1. The result of that expression is 30, which Python then stores in the y memory cell.

If an expression refers to a variable name that was never assigned, Python fails with an error, as in this example:

>>> y = z + x
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'z' is not defined

So far we have seen individual commands and sequences of commands in Python. Python executes a sequence of commands by executing each command, one after the other, in the given order.

If this is all we had, we wouldn’t be able to do much “programming”, really. A program is most often supposed to behave differently in different situations. For example, say we have an accounting program where a positive balance must be printed as a “gain” while a negative number must be printed as a “loss”, and a zero balance must be printed as “zero”. In Python we would write a program like this:

def print_balance(b):
    if b > 0:
	print('gain:', b)
    elif b < 0:
	print('loss:', -b)
    else:
	print('zero')

Write this program in a source file called print_balance.py and try it with the interactive shell by running python3 -i print_balance.py. You can now try it with various arguments:

>>> print_balance(200)
gain: 200
>>> print_balance(-75)
loss: 75
>>> print_balance(10.5)
gain: 10.5
>>> print_balance(0.0)
zero
>>> 

In Python you can write the conditions of the if command (and elif) in the intuitive way, meaning very much like you’d write conditions in English. For example, in English you might say, if it rains or it’s cloudy, we’ll play chess. And in Python, you’d say pretty much the same:

if weather == 'rain' or weather == 'cloud':
    play_chess()

Or you might say, if the temperature is greater or equal to 5 and less than or equal to 30, and if it’s sunny, we’ll play basketball. In Python:

if temperature >= 5 and temperature <= 5 and weather == 'sun':
    play_basketball()

Or you might say, if the temperature is less than 5 and it’s not snowing, we’ll go skiing:

if temperature < 5 and weather != 'snow':
    go_skiing()

Thus == means equal to, != means not equal to.

By now you must have figured out that Python groups commands together by level of indentation. Incidentally, we used the term “command” here because we have worked primarily within an interactive Python shell, where those commands are executed immediately by the shell. However, those can just as well be part of a program. In that case we also call them “instructions” or “statements”. Anyway, back to indentation and code blocks.

In programming, it is essential to group instructions together. A program is in fact a group of instructions. More specifically, a function is a group of instructions that has a name and some parameters. In our very first example, we define a function called ciao that takes an argument that the code of the function can refer to as name.

def ciao(name):
    print('Ciao', name)
    print('Have fun with Emacs!')

In other words, the instructions print('Ciao', name) and print('Have fun with Emacs!') are grouped together in sequence, and we call that sequence ciao with parameter name, so that later we can invoke that sequence of instructions with something like ciao('Antonio').

That sequence of instruction is introduced by a semicolon (:) at the end of the def command, and consists of all the instructions indented by four spaces (or more) with respect to the def command.

Similarly, we have seen that an if statement introduces a code block, and so does a corresponding else statement, also with a semicolon at the end of the if and else commands. For example, you can write:

if n % 2 == 0:
    print(n, 'is even')
    print('so, I can split it in half.')
    print('half of',n,'is',n//2)
else:
    print(n, 'is odd')
    print('so, I can split in half',n,'+ 1')
    print('half of',n,'+ 1 is',(n+1)//2)

At a high-level, this code says: if \(n\) is an even number—that is, the remainder of the integer division by 2 is zero—then do something, otherwise do something else. The something part is defined by the code block after the if statement. The something else is the code block after then else statement.

We have seen sequences of instructions and conditional instructions. This is still not enough. We need to somehow instruct the computer to do something repeatedly. For example, say you want a program to print the word 'ciao' a number of times. If you want to print 'ciao' three times, you could write a sequence of instructions:

print('ciao')
print('ciao')
print('ciao')

But what if you want to print 'ciao' twenty times? You wouldn’t want to write the same instruction twenty times in your program, would you? Of course not. And in some cases you don’t even know ahead of time how many times you need to repeat. So, instead, you’d want to give the computer one print instruction and then tell it to repeat that instruction twenty times, or any given number of times. We call these repetitions loops, because the computer loops back to the same instructions a number of times. A simple way to write one such loop in Python is this:

for i in range(20):
    print('ciao')

This tells the computer to repeat the block of instructions that follows the for instruction (indented) 20 times. In that block of instructions you also have the variable i. In fact, you might want to try and see what happens if you also print the value of that variable:

for i in range(20):
    print('ciao', i)

Anyway, this for instructions works if you know exactly how many times you need to repeat some instructions. In fact, it is even more generic than that. It works with any sequence that you can iterate on. So, in general you write for x in sequence :, and that repeats the block of instructions that follows for every value x in the given sequence. For example:

for i in ['vanilla', 'chocolate', 'strawberry']:
    print('I love', i, 'ice cream!')

So, we know how to loop over a given sequence. Very good. But this isn’t enough either! What if you don’t know ahead of time how many times you need to repeat some instructions? What if you need to run the instructions in the loop a number of times before you can decide to stop the loop? For example, you might want to repeat some action until you find something, or until you get to a certain target after some calculations. You can do this by writing a while-loop:

i = 0
while i < 20:
    print('ciao', i)
    i = i + 1

Well, you might say that this is really nothing new, since it’s exactly what we were doing before with for i in range(20). You’d be right, it’s exactly the same thing. But it shows how while-loops work: you test the condition of the while instruction, and if it’s true then you execute the block of instructions that follow the while instruction. At the end of that block of instructions, you loop back to the while instruction, again test its condition, and if it’s true again, you repeat the loop again and again. You stop the loop as soon as the while condition is false.

The above example is intentionally simple. In fact, we wrote it to mimic the previous for-loop. However, while-loops are a very general programming mechanism, more general than for-loops, or at least the type of for-loops that we see in this course.

Would you like to see a more interesting example? Here, run this program:

n = int(input('choose an integer n > 0: '))
while n != 1:
    print(n)
    if n % 2 == 0:
	n = n // 2
    else:
	n = 3*n + 1

Did you run it? Seriously. I told you, this is a read-do document. Plus this example is a really good one. Trust me! In fact, try 27. Go ahead. Pretty weird eh? Can you input a number that makes that an infinite loop?

Two more points about loops. What if we need to break out of a loop? You can write a while-loop with the exit condition right in the condition of the loop. But sometimes it’s just more convenient to check some condition and break from inside the loop. In Python you can do that with the break instruction. For example:

n = int(input('choose an integer n > 1: '))
for i in range(2,n):
    if n % i == 0:
	print('composite')
	break

Similarly, sometimes it’s useful to short-cut the body of a loop and go back immediately for the next iteration. For example:

n = int(input('choose an integer n > 2: '))
C = [False]*(n)
for i in range(2,n):
    if C[i]:
	continue
    for j in range(i*i,n,i):
	C[j] = True
    print(i)

Computers are useful to process many values, not just one or two. So, how do you memorize many values? If you know you have three values, you can put the first one in a variable called x, the second one in another variable y, and the third one in z. But you can immediately see that that doesn’t work for many values. In fact, it doesn’t even work for a few values if you don’t know how many you have.

What you want is what you often see in mathematical expressions where you refer to a sequence of numbers \(A = a_1, a_2, \ldots, a_i, \ldots, a_n\). In Python, you can do that with an array. In fact, we have already seen an example of an array before, remember? Anyway, here’s another one (in a Python shell):

>>> A = [ 2, 3, 5, 7, 11, 13, 17 ]

So, now A is an array that represents a sequence of values. I should say, those are actually called “lists” in Python jargon. But they are really arrays—trust me, they are arrays!—so that’s what I’ll call them. Anyway, the nice thing about arrays is that you can access every element (value) of the sequence by its position, as you do in those nice mathematical expressions—except that for mathematicians the first element is in position 1, whereas in Python the first position is 0. So, this is how you access the first element:

>>> A = [ 2, 3, 5, 7, 11, 13, 17 ]
>>> A[0]
2

Notice that A[0] is really like the name of a variable (a memory cell) that stores the value in position 0 (the first one). And you can of course use another variable, say i, as the position in A. For example:

>>> i = 2
>>> A[i]
5

In fact, this is how you could print all the elements in A:

i = 0
while i < 7:
    print(A[i])
    i = i + 1

Here we loop from position 0 to position 6 (not to 7) because we know that we have seven elements. But what if we don’t know the length of an array ahead of time? In Python, we can use the predefined function len(A). Try it yourself:

>>> A = ['chocolate', 'vanilla', 'strawberry']
>>> len(A)
3
>>> A = []
>>> len(A)
0

In fact, this is a more generic way to print the elements of an array A:

for i in range(len(A)):
    print(A[i])

or better yet, remember that a for-loop iterates through the elements of a sequence. And an array is definitely a sequence, so my preferred way to print the values in an array A:

for a in A:
    print(a)

Once you have a program, you’ll most likely want to run that program multiple times, possibly with many input values. You’ll want to give that program a name and some arguments, to then invoke that program by name. In Python, you can do that by defining a function. In fact, we have done that already, for example with the print_balance(b) function:

def print_balance(b):
    if b > 0:
	print('gain:', b)
    elif b < 0:
	print('loss:', -b)
    else:
	print('zero')

This notion of a “function” is rather different from the notion of a function in mathematics. One notable difference in the example above is that the print_balance(b) function takes an argument (b) but, unlike a mathematical function, does not have a value.

For our purposes, a function is a program—or call it an algorithm, or a method, or a subroutine—that we can invoke by name. Such a function (program) may or may not take input arguments, and may or may not return a value. For example, the following function takes no arguments and returns a value.

def the_answer():
    x = 40
    y = 2
    return x + y

The return value of the function is determined by the execution of the return instruction, which also terminates the execution of the function and therefore “returns” the execution to the code that invoked the function. As an example, try the following code:

def is_prime(n):
    for i in range(2,n):
	if n % i == 0:
	    return False
    return True

for i in range(2,100):
    if (is_prime(i)):
	print(i,'is prime')
    else:
	print(i,'is composite')

Notice that the code of the is_prime function in the example above uses a variable called i, as does the code below the definition that also invokes the is_prime function. This is perfectly okay, in the sense that the behavior is the intuitive and more conservative one: those are two separate variables, even if they have the same name, and so there is no conflict.

More specifically, the i variable, like all variables assigned within the is_prime function, is stored in a private memory area for each invocation of the function. That is, every time you invoke a function—even recursively—that invocation sets aside a private memory area for the execution of the code of the function. So, when the code assigns a variable, that variable does not refer to other variables with the same name elsewhere. Notice that the parameters of a function, such as the variable n in the function is_prime(n), are treated exactly like ay other private variable in the function.

One last but important point about function definitions. Despite the fact that local variables are private and do not conflict with variables assigned elsewhere with the same name, a function may still have side-effects. That is, a function may change the value of variables defined outside the code of the function. A classic example is a function that takes an array as an argument. Try this code:

def reset_to_zero(A):
    for i in range(len(A)):
	A[i] = 0

B = [1, 2, 3]
reset_to_zero(B)
print(B)

So, think about it, a function prog1(n) that takes a number n as a parameter can change the value of the variable n, but since that n is a private variable, that does not change the value of anything outside the function. However, a function prog2(A) that takes an array A can still change the content of the array outside the function. Why? What’s the difference? This is a tricky question, but it’s also an important one. So, I don’t want to dismiss it. I will try to be concise, which means that I can’t be very precise. But I still want to describe things as they are in essence.

Here’s the deal. There is no difference! That is, Python treats the two functions and the two variables (parameters) in exactly the same way. The difference is in the nature of those variables. In fact, this is the nature of all variables in Python.

As we said initially, a variable is a space in memory that has a name—meaning that we can refer to by a certain name within some instructions in the program—and that can contain a value. This is true for both a variable n = 7 containing the integer value 7, an array A = [1, 2, 3]. However, the difference is that some “values” aren’t values per-se, but rather references to other areas in memory that in turn contain other variables that can take values including references to yet-other areas in memory. That is the case for an array. So, A per-se is a variable just like n. But A’s value isn’t the whole array. That is, A does not in itself contain the sequence [1,2,3]—and this shouldn’t be surprising, since the sequence can be arbitrary long. Instead, the sequence is stored somewhere else in memory, and A contains the address of that memory location.

So, let’s see what happens when we invoke a function that takes an array as a parameter. The instruction B = [1, 2, 3] in the example above reserves some memory for the array itself, meaning a block of three variables (memory cells) containing the numeric values 1, 2, and 3, respectively, plus a variable called B that contains the address of that block of variables. So then we could write the expression B[0] that would refer to the first variable in the block of variables referenced by B.

When we then invoke the function reset_to_zero(B), that executes the code in the function definition with parameter A initialized with—meaning, assigned to—the value of B. So, think about what happens here: B is a variable whose value is the address of the block of variables holding the elements of the array; that value, meaning that address, is then assigned to the private parameter variable A in the execution of the reset_to_zero function. So, now reset_to_zero has a variable A that is distinct from B, but that contains a reference to the same block of variables as B. So, the expression A[0] within the code of the reset_to_zero function refers to exactly the same variable as B[0] would in the context of the invocation of the function. This is why the effect of the function, from the perspective of the caller code, is to change the value of the B array.

There are three ways to learn computer programming: practicing, practicing, and practicing. So, get on with it!