# Elementary Algorithmic Programming in Python

Programming means telling a computer how to do something. It is not
fundamentally different from telling a *person* how to do the same
thing. In essence, you write step-by-step instructions. Think about
the way you would write a recipe, or directions to go to some place.
Those are effectively “programs”. With a person, you might write
those programs in English (or whatever natural language that person
understands). Here we deal with computer programs, and for our
purposes we use a language called Python.

Our goal, however, is not to learn much about Python, but rather to learn enough of Python to be able to write relatively short programs that solve algorithmic or combinatorial problems. In fact, not only the programs will be short—never more than 50 lines, and most often less than 20 lines of code—but we will also intentionally limit ourselves to some very basic features of the Python language.

This is a *read-do* document. You must read the text slowly, a
paragraph or even a sentence at a time. Don’t rush through it or just
skim it. And as soon as you have at least a basic idea of the
concepts described in the text, you immediately put them into practice
with the many examples and exercises listed in the text. You should
also practice with other examples that you create and experiment with
out of your own curiosity. This is the best way to learn programming
anyway—or anything else, really.

## Preliminaries

I assume you have Python installed on your computer. Specifically, I assume you have 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.

### Running Python as an Interactive Command Shell

Run Python as an interactive shell by opening a command shell
(typically through a terminal application) and by running the command
`python3`

. You should see something like this:

> python3 Python 3.8.5 (default, Jul 28 2020, 12:59:40) [GCC 9.3.0] on linux Type "help", "copyright", "credits" or "license" for more information. >>>

You might get something slightly different. But if you get something completely different, then you probably don’t have Python-3 installed on your computer, or in any case your shell can’t find it. If that is the case then you should ask your friendly teacher (yours truly) or a fellow student to help you out.

Notice that there are *two* shells here. The first one is what I call
a *command* shell, which is sometimes also called terminal shell
because it is what you typically run when you open a terminal
application. Unfortunately, these names can be confusing.
Essentially all shells are “command” shells, since their job is to
read commands from a user interface (the terminal), execute those
commands, and then write the resulting output on the same or another
interface.

Anyway, I will distinguish the *command* shell from the *Python*
shell. This first shell is the one taking commands like `ls`

,
`mkdir`

, and `cd`

, and also applications like `python3`

, which is what
we run here. The prompt of this command shell is a single `>`

character (greater than). You may see a different prompt depending on
your configuration and preferences. However, in these examples, I
will use the single `>`

character to identify the prompt of the
command shell.

Then, from that command shell we run `python3`

and obtain the prompt
`>>>`

of the *Python* shell, which consists of three `>`

characters
one after the other. This means that the command shell runs
`python3`

, which is the Python shell, that takes over the input and
output and now starts prompting you to input commands.

At this point, you can type *Python* commands, and the Python shell
will execute them. For example:

>>> print('Ciao!') Ciao! >>>

### Running a Python Program

First of all, you should create a directory within which to experiment with the following examples. I suggest you do that using a command shell, since the next steps will require you to run commands from a command shell anyway:

> mkdir programming > cd programming >

Now you are in your new `programming`

directory, so go ahead and create
a file called `ciao.py`

containing the following text:

print('Ciao!') print('This is your first Python program.')

Seriously, do it! Don’t just read through this document. This is a
*read-do* document. You read an example, and then you try it yourself
right away.

So again: create and edit a file called `ciao.py`

. To do that, you
should use a good text editor. My favorite one is Emacs, but you
should use whatever works well for you. Be warned though, that some
editors will mess things up, because they don’t write files in plain
text format. So, make sure that the file you just edited and saved
contains exactly those two lines of plain text. You can do that from
the terminal shell with the `cat`

command:

> ls ciao.py ciao.py > cat ciao.py print('Ciao!') print('This is your first Python program.')

If this is what you see, then you are now ready to *run* your Python
program. From the same command shell:

> python3 ciao.py Ciao! This is your first Python program.

### Reading a Python Program and Then Using Python Interactively

In many examples below, you will want to write a program—or more
specifically write an algorithm in the form of a Python
*function*—and then run that program (function) interactively,
perhaps to test it with different arguments. Let’s see how you can
do that.

In a source file called `greetings.py`

write a function called
`ciao(name)`

as follows.

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

We’re getting ahead of ourselves defining “functions” here, but that’s
okay. Just make sure the spacing is correct though. The spaces
before the two `print`

commands are important, as we will see in
detail later. For now just make sure those two lines have the same
number of initial spaces (indentation).

Now we could run this `greetings.py`

program the same way we did with
`ciao.py`

in the example above. However, that is really not what we
want. In fact, if we run it as a program, we don’t see any output.
Try it yourself:

> python3 greetings.py >

And this is correct. The `greetings.py`

program defines a function
`ciao(name)`

but does not use it. Instead, what we want is to use that
function with some arguments. For example, we might want to call the
`ciao`

function as follows, from a Python shell:

>>> ciao("Antonio") Ciao Antonio Have fun with Emacs! >>>

In other words, we want to run a Python shell that reads the
definition of the `ciao`

function from `greetings.py`

, and then
processes the Python command `ciao("Antonio")`

. The way to do that is
to run python with the `-i`

option, which makes it run in
“interactive” mode:

> python3 -i greetings.py >>> ciao("antonio") Ciao antonio Have fun with Emacs! >>> ciao("mamma") Ciao mamma Have fun with Emacs!

Notice that we invoke Python from the command shell, which starts the
Python shell from which we can invoke the function defined in
`greetings.py`

. To exit the python shell and therefore return to the
command shell, you can invoke the `exit()`

function.

>>> ciao("mamma") Ciao mamma Have fun with Emacs! >>> exit() >

## Basic Arithmetic Expressions

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 its two operands, as you would
imagine, and always returns a floating point number. However,
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: `a // b`

gives
you the *quotient* of \(a\) over \(b\), meaning the 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 whole numbers, also known as *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

## Variables

Python can memorize values for you, so that you can use them again later. 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 weird or that
it would cause some kind of circular dependency. But that’s perfectly
okay. The value initially stored in \(x\) is 20 (from the examples
above), so `x + 1`

is 21, which is what is stored in \(x\) after the
assignment command. 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. 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 prints an error message, as in this example:

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

### Exercise

What is the content of Python’s memory after the following commands?

>>> x = 2 >>> y = 1 >>> y = x >>> x = y

### Exercise

What is the content of Python’s memory after the following commands?

>>> x = 1 >>> y = 1 >>> y = x - y >>> x = y - x

### Exercise

Write commands to swap the values of \(x\) and \(y\), for example after the example above.

## Conditional Instructions

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
```

. Once again, pay attention to the spacing. Make
sure the indentation is consistent as in the code above. 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 <= 30 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*.

## Code Blocks

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 give that sequence the name `ciao`

and a parameter named `name`

, so
that later we can *invoke* that sequence of instructions with
something like `ciao('Antonio')`

.

That sequence of instructions 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.

### Exercise

Write a function `rectangle_area(x1,y1,x2,y2)`

that, given the
coordinates \((x_1,y_1)\) and \((x_2,y_2)\) of two opposite vertices of an
axis-aligned rectangle, prints the area of the rectangle. An
axis-aligned rectangle is such that its sides are parallel to the \(X\)
or \(Y\) axis. You must not use any function or language features other
than the ones we have seen so far.

## Loops

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 the print command. 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 we think
of the execution as a path through the program instructions, and in
this case the execution path 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`

instruction works if you know exactly how many
times you need to print. 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 now know how to loop over the elements of 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
when you loop back to the `while`

instruction and the condition turns
out to be 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 the code loop forever? I bet you can’t. But if you find one of those numbers, let me know!

Two more points about loops. What if we need to break out of a loop?
As I said, the loop condition in the *while* instruction is evaluated
when the execution goes back to that instruction. 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)

Did I say this is a read-do document? Do it. Try this code yourself!

## Arrays

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 have a collection of elements \(a_1, a_2, \ldots, a_n\) and you
refer to each element \(a_i\) by its numeric index \(i\). In Python, you
can do the same with an *array.* In fact, we have already seen an
example of an array before, remember? You don’t? Okay, no problem.
It’s a good exercise: go back through the text and see if you spot the
array. *Do it!* Anyway, here’s another one (in a Python shell):

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

\(A\) is an array. An array represents a *sequence.* 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. The nice thing about arrays is that you can access every
element 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\) is this:

for a in A: print(a)

### Adding or Removing an Element at the End of an Array

For our purposes, there are only two ways we modify the length of an array. We can either add an element at the end, or we can remove the last element. For example, this is how we can read a sequence of numbers from the input:

A = [] while True: line = input() if line == '': break for x in line.split(): A.append(int(x))

Here `A.append()`

adds an element at the end of \(A\), thereby
increasing \(A\)’s length by one. If instead we want to delete the
element at the end of \(A\), we write `del A[-1]`

or `A.pop()`

.
`A.pop()`

also returns the last element that is deleted.

The Python language provides many other ways to cut or modify sequences. However, we intentionally do not consider them, since they often incur hidden complexities.

### Exercise

Write a Python function called `print_reverse(A)`

that prints a given
sequence \(A\) in reverse order. For example

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

### Exercise

Write a Python function called `print_maximum(A)`

that prints the
maximal value in the given sequence \(A\). For example

>>> A = [ 7, 21, 15, 1, 18, 31, 17 ] >>> print_maximum(A) 31

What would you do if you are given an empty sequence?

## Function Definitions

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 the execution “returns” 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.*

So, what’s the difference between `prog1(n)`

and `prog2(A)`

when \(n\)
is a number and \(A\) is an array? Well, 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 arbitrarily 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\). 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.

## More Exercises

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

### Minimum

Write a function `minimum(A)`

that returns the minimum value in \(A\).
You may assume that the sequence contains at least one element.

#### Examples

>>> minimum([1,2,3]) 1 >>> minimum([3,2,1]) 1 >>> minimum([100,2,55,4,3,2,67,3]) 2 >>> minimum([7]) 7

### Position in Sequence

Write a function `position_in_sequence(A,x)`

that returns the first
position in which value \(x\) appears in \(A\). Positions start from \(0\).
Return \(-1\) if \(x\) does not appear in \(A\).

#### Examples

>>> position_in_sequence([6, 7, 10, -2, 3], 7) 1 >>> position_in_sequence([3, 2, 1, 1, 3, 2, 2, 3, 1], 1) 2 >>> position_in_sequence([], 1) -1 >>> position_in_sequence([2, 3, 4, 5], 1) -1 >>> position_in_sequence([2, 3, 4, 5], 2) 0

### Count Lower

Write a function `count_lower(A,x)`

that returns the number of
elements in \(A\) whose value is less than \(x\).

#### Examples

>>> count_lower([0,7,10,-2,3], 7) 3 >>> count_lower([3, 2, 1, 1, 3, 2, 2, 3, 1], 2) 3 >>> count_lower([3, 2, 1, 1, 3, 2, 2, 3, 1], 10) 9 >>> count_lower([], 1000000000000000) 0 >>> count_lower([2, 3, 4, 5], 1) 0

### Check Sorted

Write a function `check_sorted(A)`

that returns `True`

if the given
sequence \(A\) is sorted in non-decreasing order, or `False`

otherwise.

#### Examples

>>> check_sorted([1,2,3]) True >>> check_sorted([1,3,2]) False >>> check_sorted([]) True >>> check_sorted([7]) True >>> check_sorted([50,50,50]) True >>> check_sorted([43,51,51]) True >>> check_sorted([43,51,50,51,70]) False

### Log Base Two

Write a function `log_base_two(n)`

that, given a positive integer \(n\),
returns the integer logarithm base-two of \(n\), that is, the maximal
integer \(k\) such that \(2^k\le n\).

#### Examples

>>> log_base_two(1) 0 >>> log_base_two(2) 1 >>> log_base_two(5) 2 >>> log_base_two(1000) 9

### Maximal Difference

Write a function `maximal_difference(A)`

that returns the
maximal difference between any two elements of the given sequence \(A\).

#### Examples

>>> maximal_difference([2, 1, 5, 9, 4, 10, 8]) 9 >>> maximal_difference([1]) 0 >>> maximal_difference([1, 1, 1]) 0 >>> maximal_difference([10,-3, 4, 11, 0, 9]) 14

### Minimal Sum

Write a function `minimal_sum(A, x)`

that returns `True`

if there are
some elements in \(A\) whose sum is greater or equal to \(x\), or `False`

otherwise.

#### Examples

>>> minimal_sum([], 1) False >>> minimal_sum([1], 1) True >>> minimal_sum([3, 2], 4) True >>> minimal_sum([3, -2], 4) False >>> minimal_sum([2, 1, 5, -3, 9, 4], 20) True >>> minimal_sum([32,-3,10,7,-4,18,25], 50) True >>> minimal_sum([32,-3,10,7,-4,18,25], 94) False

### Isolated Elements

Write a function `isolated_elements(A)`

that prints, in order, all the
elements that are different from all their adjacent elements, that is,
each element that is different from the previous element (if that
exists) and the next element (if that exists).

#### Examples

>>> isolated_elements([]) >>> isolated_elements([1]) 1 >>> isolated_elements([7,3]) 7 3 >>> isolated_elements([2, 2]) >>> isolated_elements([2, 2, 3, 2, 3]) 3 2 3 >>> isolated_elements([-2, 2, 2, 2, -2]) -2 -2 >>> isolated_elements([1,2,1,2,1,2,1,2]) 1 2 1 2 1 2 1 2

### Repeated Elements

Write a function `repeated_adjacent_elements(A)`

that prints, in
order, all the elements that are repeated in sub-sequences of two or
more elements. For every maximal subsequence of identical values,
`repeated_adjacent_elements(A)`

must print that value *only once.*

#### Examples

>>> repeated_adjacent_elements([]) >>> repeated_adjacent_elements([1]) >>> repeated_adjacent_elements([1, 2]) >>> repeated_adjacent_elements([3, 3]) 3 >>> repeated_adjacent_elements([1,-1,7,7,-1,7,1,7,7,7,7,2,2]) 7 7 2

### Compression

Write a function `compress_sequence(A)`

that prints a “compressed”
version of the given sequence \(A\). Compression is obtained by
printing three or more consecutive elements with equal values with a
line containing \(x\) `*`

\(k\), where \(x\) is the value of those elements
and \(k\) is the number of consecutive equal elements.

#### Examples

>>> compress_sequence([-1,1,1,1,7,7,7,7,5,5,1,1,4,1]) -1 1 * 3 7 * 4 5 5 1 1 4 1

### Maximal Increasing Subsequence

Write a function `maximal_increasing_subsequence(A)`

that returns the
maximal length of any strictly increasing sequence of contiguous
elements of \(A\). For \(A=-1,1,7,5,-2,1,2,7,7,5,0,1,3,4,1\), the result
is \(4\), since there is at least one increasing subsequence of length 4
(e.g., \(-2,1,2,7\)) but there is no increasing subsequence of length 5.

#### Examples

>>> maximal_increasing_subsequence([-1,1,7,5,-2,1,2,7,7,5,5,1,1,4,1]) 4

### Partition Even/Odd

Write a function `partition_even_odd(A)`

that takes an array of
integers \(A\) and sorts the elements of \(A\) so that all the even
elements precede all the odd elements. The function must sort \(A\)
*in-place.* This means that it must operate directly on \(A\) just by
swapping elements, without using an additional array.

#### Examples

>>> A = [-1,1,7,5,-2,1,2,7,7,5,5,1,1,4,1] >>> partition_even_odd(A) >>> print(A) [-2,2,4,-1,1,7,5,1,7,7,5,5,1,1,1]

Notice that in general the solution is not unique. For example, the following result would be equally correct:

>>> A = [-1,1,7,5,-2,1,2,7,7,5,5,1,1,4,1] >>> partition_even_odd(A) >>> print(A) [2,4,-2,5,1,5,1,7,7,7,-1,1,1,5,1]

### Like or dislike

Write a function `like_or_dislike(A)`

that takes a sequence of ratings
expressed with the strings `'like'`

and `'dislike'`

. The function
must print `'like'`

if the most prevalent rating is `'like'`

, or
`'dislike'`

if the most prevalent rating is `'dislike'`

, or
`'undecided'`

otherwise.

#### Examples

>>> like_or_dislike(['like']) like >>> like_or_dislike(['dislike','like','dislike']) dislike >>> like_or_dislike(['like','dislike']) undecided >>> like_or_dislike([]) undecided

### Stops and Inversions

A car moves along a road. For simplicity you may assume that the road
is perfectly linear and that the position of the car is given as the
distance from a certain reference point on the road. Write a function
`stops_and_inversions(P)`

that, given an array \(P\) of time-ordered
positions of the car, prints the number of times the car stopped and
the the number of times that the car inverted the direction of motion.
\(P=p_1,p_2,p_3,\ldots\) is time ordered in the sense that the car is at
position \(p_1\) *before* it is at position \(p_2\), it is at \(p_2\) before
it is at \(p_3\), and so on.

#### Examples

>>> stops_and_inversions([]) stops: 0 inversions: 0 >>> stops_and_inversions([5,5,5]) stops: 0 inversions: 0 >>> stops_and_inversions([5,5,5,6,7,8]) stops: 0 inversions: 0 >>> stops_and_inversions([5,5,5,6,7,8,8]) stops: 1 inversions: 0 >>> stops_and_inversions([1,5,10,12,12,12,15,20,24]) stops: 1 inversions: 0 >>> stops_and_inversions([1,5,10,12,12,11,8,7]) stops: 1 inversions: 1 >>> stops_and_inversions([1,5,10,12,12,11,8,7,9,11,20,30]) stops: 1 inversions: 2 >>> stops_and_inversions([1,5,10,12,12,11,8,7,9,11,20,30,30,30,30,35,35]) stops: 3 inversions: 2

### Minimal Bounding Rectangle

Consider a sequence of \(n\) points \(p_1,p_2,\ldots,p_n\) in a plane
identified by their Cartesian coordinates. The coordinates are given
in the form of two arrays \(X\) and \(Y\) both containing of \(n\) numbers,
such that point \(p_i\) has coordinates `X[i]`

and `Y[i]`

.

Write a function called `minimal_bounding_rectangle_area(X,Y)`

that,
given two arrays of coordinates \(X\) and \(Y\) representing \(n\) points,
returns the area of the smallest axis-aligned rectangle that covers
all the \(n\) points. An axis-aligned rectangle is such that its sides
are parallel to the \(X\) or \(Y\) axis.

#### Examples

>>> minimal_bounding_rectangle_area([3,2,10,4],[5,5,3,2]) 24 >>> minimal_bounding_rectangle_area([2],[89]) 0 minimal_bounding_rectangle_area([-8,8,9,-9,4,-4,4,-9,7],[10,1,-1,-5,7,-7,-2,0,3]) 306

### Distance Between Points

Write a function called `distance_between_points(X,Y,d)`

that, given
two arrays of coordinates \(X\) and \(Y\) representing \(n\) points, and a
number \(d\), return `True`

if and only if two of the given points are
at a distance \(d\) from each other, or `False`

otherwise.

#### Examples

>>> distance_between_points([3,2,1,10,5,4],[5,5,4,3,1,2],5) True >>> distance_between_points([3,2,1,10,5,4],[5,5,4,3,1,2],1) True >>> distance_between_points([3,2,1,10,5,4],[5,5,4,3,1,2],6) False >>> distance_between_points([3,2,1,10,5,4],[5,5,4,3,1,2],4) False

### Find a Square

Write a function called `find_a_square(X,Y)`

that, given two arrays of
coordinates \(X\) and \(Y\) representing \(n\) points, and a number \(d\),
return `True`

if and only if four of those points are the vertices of
a square, or `False`

otherwise.

#### Examples

>>> find_a_square([0,1,2,3],[3,1,4,2]) True >>> find_a_square([0,1,2,1],[3,1,3,5]) False

### Most Common Digit

Write a function called `most_common_digit(n)`

that takes an integer
\(n\), and returns the most common digit in the decimal representation
of \(n\). If there are two or more most common digits, the function
must return the smallest one.

#### Examples

>>> most_common_digit(1969) 9 >>> most_common_digit(44272) 2 >>> most_common_digit(36223771538825331723) 3 >>> most_common_digit(0) 0

### Sums of Squares

Write a function called `sums_of_squares(n)`

that prints all the pairs
of squares that sum to \(n\). That is, `sums_of_squares(n)`

prints a
line \(a^2\) `+`

\(b^2\) for all the distinct pairs \(a\le b\) such that
\(a^2+b^2=n\).

#### Examples

>>> sums_of_squares(25) 9 + 16 >>> sums_of_squares(21) >>> sums_of_squares(125) 4 + 121 25 + 100 >>> sums_of_squares(178) 9 + 169 >>> sums_of_squares(179) >>> sums_of_squares(17993241) 176400 + 17816841