```
from IPython.core.display import HTML
HTML(open("custom.html", "r").read())
```

Programming is about writing programs. A program instructs your computer to solve a given problem. The problem might be a very basic problem or very complex.

Some examples for problems we can solve with a computer:

- compute the sum of the first 10 natural numbers
- decide if a given year is a leap year
- compute the molecular weight of a given amino acid sequence
- count the number of sequences in a FASTA file
- align two gene sequences
- count cells in a given digital image from a microscope
- predict the weather in Zurich for the next two days

An algorithm is an informal specification of "basic" computation steps to solve a given problem.

The following algorithm computes the greatest common divisor (gcd) of two numbers `a`

and `b`

:

- if
`a`

is equal to`b`

:`a`

is the gcd. We stop. - if
`a`

is greater than`b`

: replace`a`

by`a - b`

- else replace
`b`

by`b - a`

- continue with step 1

Execute this algorithm with pen and paper to compute the greatest common divisor of $66$ and $78$. Start with a table with two colums for the actual value of `a`

and `b`

and add a line with updated values for every step.

- An
**algorithm**is a step-by-step list of simple instructions for solving a computational problem. - A
**program**is a formal specification of an algorithm in terms of instructions the computer can understand. - So
**programming**includes two steps:- Developing an algorithm for the specific problem
- Formulating the algorithm in a programming language (called
**implementing an algorithm**)

- to learn how to solve a problem by decomposing it into very basic steps (this is named
**algorithmic thinking**). - to learn how to instruct the computer to execute this solution (
**speaking a programming language**)

Before we start to introduce a real programming language we start to play with so called pseudo code notation and will gain some insights how a computer works.

Programs use "Variables". You can imagine that data (as numbers) is stored in memory cells having a name. So we visualize the state of the memory using a table with two columns as you can see below.

The first minimal command is the **assignment instruction**. This instruction looks like

```
a ← 1.23
```

which places the number `1.23`

in a cell named `a`

. So after execution of this simple statement by the computer the memory looks like this:

name | value |
---|---|

a | 1.23 |

If you chain the two instructions they are executed in the listed order, so after executing the minimal two line program

```
a ← 1.23
a ← 3.45
```

the value `1.23`

is overwritten and the final state of the memory is

name | value |
---|---|

a | 3.45 |

You can create a new variable by computations based on known variables. So the assignment

```
b ← a + 1
```

results in

name | value |
---|---|

a | 3.45 |

b | 4.45 |

So a variable may appear on both sides of `←`

:

**if the variable is on the left side this means we write data into the corresponding memory cell****if the variable is on the right side this means we fetch data from the named cell**

To compute the average of two values the statement (`/`

is division)

```
mean ← (a + b) / 2
```

will complete the memory to

name | value |
---|---|

a | 1.2 |

b | 2.2 |

mean | 1.7 |

As you can see above a variable name may contain more than one character. In most programming languages (including Python) you may use a mixture of alphabetic characters `a`

to `z`

, `A`

to `Z`

as well as numbers `0`

to `9`

and the so called "under score" `_`

. We learn more details about variable names later.

Variables are not only used for the input data and the final result but can keep intermediate values. So our computation above can be written as

```
sum ← a + b
mean ← sum / 2
```

This can be used to shorten expressions and sometimes is needed as we see in the following exercise:

Assume your computers memory has two cells `a`

and `b`

containing different numbers. Can your write a sequence of three instructions to exchange the contents of both cells ? (Starting with `a ← b`

or `b ← a`

will not work !)

**A program is a sequence of instructions which are executed by the computer sequentially**. This flow of execution may **branch** based on specified conditions.

To give an example the following program computes the salary of an worker which worked for `hours`

hours for a salary `salary_per_hour`

. If he works more than 40 hours the over-hours are paid twice:

```
IF hours ≤ 40 THEN DO {
salary ← hours * salary_per_hour
}
ELSE DO {
salary_first_40 ← 40 * salary_per_hour
over_hours ← hours - 40
over_hour_salary ← 2 * over_hours * salary_per_hour
salary ← salary_first_40 + over_hour_salary
}
```

We use the *curly braces* to indicate which part of the code should be executed if the given condition is true and *capitalized words* for writing instructions and lower case words for variables aka memory cells.

Here the computer will execute the computations in the first block delimited by curly braces if `hours`

is 40 or less. Else the second block will be executed.

Given you have values

`39`

and`12`

in cells`hours`

and`salary_per_hour`

in your computers memory. Reproduce execution of the instructions above on a piece of paper !Do the same for values

`45`

and`15`

.

For this we start with the setting

```
i ← 0
acc ← 0
```

(I use `acc`

as an abbreviation for `accumulator`

, you may choose other names).

Then we execute the following two instructions

```
i ← i + 1
acc ← acc + i
```

and we have

name | value |
---|---|

i | 1 |

acc | 1 |

Running the same two statements again:

```
i ← i + 1
acc ← acc + i
```

results in the following memory image

name | value |
---|---|

i | 2 |

acc | 3 |

Use a piece of paper and repeat the instructions above. What is the state of your memory after three extra repetitions ?

If we start with

```
i ← 0
acc ← 0
```

And repeat the block

```
i ← i + 1
acc ← acc + i
```

$n$ times the final memory will contain

name | value |
---|---|

i | n |

acc | 1 + 2 + ··· + n |

We can summarize the instructions from the last section in pseudo code as follows:

```
i ← 0
acc ← 0
REPEAT n TIMES {
i ← i + 1
acc ← acc + i
}
```

Here we use curly braces to indicate which part of the code should be repeated and again capitalized words for writing instructions and lower case words for variables aka memory cells.

**Using REPEAT is not only a shorter notation: for an arbitrary value in a cell named n, running the same code will always compute the sum 1 + ··· + n** !

Modify the last pseudo code above to compute the sum of the first $n$ square numbers (use multiplication for computing squares). Test your code with pen and paper !

Develop some pseudo code which computes the product of the first $n$ numbers. Test your code with pen and paper !

What does the following pseudo code compute ? (We use

`*`

for multiplication). Use pen and paper to follow the execution of the single statements assuming different values of`n`

:

```
i ← 0
x ← 1
REPEAT n TIMES {
i ← i + 1
x ← 2 * x
}
```

To demonstrate conditional execution in combination with repeated execution we modify the previous pseudo code to compute the sum of the even numbers in the range $1$ to $n$:

```
i ← 0
acc ← 0
REPEAT n TIMES {
i ← i + 1
IF i IS EVEN THEN {
acc ← acc + i
}
}
```

Trace the execution of the previous program with pen and paper for $n=5$ !

Without explaining Python details, our pseudo code algorithm for computing the sum of the first $n$ natural numbers can be transformed into a Python program only by replacing some notations:

- The
`←`

is written as`=`

- The
`REPEAT n TIMES`

is written as`for x in range(n):`

- We have no curly braces, the indentation by four spaces indicates which instructions should be repeated $n$ times.

Comment: Take the `for ..`

statement as given, we come introduce details later.

**Note that = in a Python program expresses ←**. So

`=`

- does not ask Python to determine if two values are equal
- does not ask Python to solve an equation
- does not determine a value of a variable "for now and forever"

** Always read = as "write to a memory cell" and nothing else **

- Pseudo code is informal
- what matters is that pseudo code can be "executed" and understood by a human and that it is detailed enough to be translated to a program one by one
- In contrast
**if you write a computer program almost every character matters**, small deviations from the correct syntax result either in error messages or programs computing wrong results. - The algorithm/idea how to compute the sum of the first
`n`

numbers is independent of the programming language used. Just the notation will differ.

So this is the result of the described transformation:

```
i = 0
acc = 0
for x in range(n):
i = i + 1
acc = acc + i
```

To complete the Python program we extend it so it interacts with an user and displays a result. For this

- we start with an instruction which asks the user to provide a value for $n$ and waits until the user presses the "Return" key
- and end with an instruction to tell the user what the content of the memory cell
`acc`

is

And this is now our first usable Python program:

```
n = int(input("please enter n: "))
i = 0
acc = 0
for x in range(n):
i = i + 1
acc = acc + i
print("the sum is", acc)
```

- Python code is presented in the boxes with a light grey background.
- The lines with a yellow background show the interaction of the program with the user.
- If you read the examples in the script
**always try to match the shown interactions having yellow background with the Python instructions in the proceeding code box**!

**Sometimes we say "Python script" instead of "Python program"**.

- Type (no copy and paste !) the previous program at https://repl.it/languages/python3 and run it.
- Translate your pseudo code for computing the sum of the first $n$ square numbers to Python and run it.
- Translate your pseudo code for computing the product of the first $n$ natural numbers to Python an run it.

If we talk about Python you should distinguish:

- The
`Python interpreter`

is the program which executes`Python`

code. There are different`Python interpreters`

for different operating systems and for different versions of the`Python programming language`

. - The
`Python programming language`

is given by an formal specification how syntactically correct`Python`

programs are spelled and how the`Python interpreter`

executes (interprets) them. The language only varies depending of the version of the language (here we use 3.5 or newer). - Soon we learn about
`PyCharm`

which is one of many so called`integrated development environments`

(`IDE`

s). This is a program on top of the`Python interpreter`

which assists writing and running code but which is not mandatory to run a Python program. - In
`PyCharm`

we have a text editor to write text which is conformant to the specificaton of the Python programming language, and we also have a button to start the Python interpreter to execute this text.

```
```