from IPython.core.display import HTML

HTML(open("custom.html", "r").read())

About programming

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

Algorithms (no Python yet)

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

Example

The following algorithm computes the greatest common divisor (gcd) of two numbers a and b:

  1. if a is equal to b: a is the gcd. We stop.
  2. if a is greater than b: replace a by a - b
  3. else replace b by b - a
  4. continue with step 1

Exercise 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.

Some terms

  • 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:
    1. Developing an algorithm for the specific problem
    2. Formulating the algorithm in a programming language (called implementing an algorithm)

This means also that "learning to program" has two aspects:

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

Some basic concepts

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.

Variables

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 :

  1. if the variable is on the left side this means we write data into the corresponding memory cell
  2. 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

Comment:

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.

Temporary variables

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:

Exercise 2

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 !)

Conditional execution

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.

Exercise 3

  • 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.

Now we will learn how we can compute the sum of the first $n$ numbers !

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

Exercise 4

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

Observation:

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

Repetitions (iterations) of instructions

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.

This is now a formal algorithm to compute the sum of the first $n$ natural numbers.

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 !

Exercise 5

  1. 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 !

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

  3. 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 
}

Now we combine the learned concepts

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


Exercise 6

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

Our first Python program

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:

  1. The is written as =
  2. The REPEAT n TIMES is written as for x in range(n):
  3. 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)
---------------------------------------------------------------------------
StdinNotImplementedError                  Traceback (most recent call last)
<ipython-input-2-a824b0f958a3> in <module>()
----> 1 n = int(input("please enter n: "))
      2 
      3 i = 0
      4 acc = 0
      5 for x in range(n):

/Users/uweschmitt/Projects/python3-course/venv/lib/python3.6/site-packages/ipykernel/kernelbase.py in raw_input(self, prompt)
    687         if not self._allow_stdin:
    688             raise StdinNotImplementedError(
--> 689                 "raw_input was called, but this frontend does not support input requests."
    690             )
    691         return self._input_request(str(prompt),

StdinNotImplementedError: raw_input was called, but this frontend does not support input requests.

For the moment accept the first and last line as they are, we will learn the details during the following script.

How to read the course script

  • 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".

Exercise 7

  • 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.

A few definitions

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 (IDEs). 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.