Programming in Python

1 Semester Module 6 ECTS

What other names are used for the von Neumann architecture?

Von Neumann model or Princeton architecture

Which three components are drawn inside the CPU in the von Neumann model?

Control Unit, Memory, Arithmetic-Logic-Unit (ALU)

What is the role of the Control Unit?

It orchestrates the program execution

What is the role of the Arithmetic-Logic-Unit (ALU)?

The "brain": it performs the arithmetic and logic operations

What is the role of the memory in the von Neumann model?

It stores the data and the program, i.e. the state of our computation

Name examples of input devices.

External drive, sensors, mouse, keyboard

Name examples of output devices.

Screen, external drive, printer

What is external memory in the von Neumann model (examples)?

Memory outside the CPU, e.g. hard disk and RAM

Which network technologies are named as connecting the computer to a network?

Wifi, Ethernet, 3G/4G/5G/6G

Describe the von Neumann architecture diagram: how are the components connected?

Input devices feed the CPU (control unit, memory, ALU); the CPU sends results to output devices; external memory (hard disk, RAM) is attached to the CPU; a network connection links the computer to other systems

How is an algorithm defined?

Any well-defined computational procedure that takes some value or set of values as input and produces some value or set of values as output

What is a program?

A series of instructions

Which typical operations/instructions do programs contain?

Manipulating data (read/store in memory); arithmetic (+, *, /, -, …); control flow of execution (e.g. if … else)

How are programs stored, and what is that called?

As data in memory; software

How are programs related to algorithms?

A program is the language-specific representation of an algorithm

What is the general structure of an algorithm?

input → instructions → output

Which steps lead from an algorithm to program execution?

Algorithm → (programming) → program/code in a programming language → (translation) → executable program in machine language → (interpretation by CPU) → program execution

What is the difference between code and an executable program?

Code is written in a programming language (e.g. Python); the executable program is in machine language

Why does a computer need a compiler or interpreter?

To understand our algorithm: they translate the readable source code into something the computer can execute

How does a compiler work (example language)?

It scans the entire program first, translates it completely and then executes the translated program, e.g. C/C++

Which stages does compilation go through?

Source language (readable source code) → optional intermediate language → target language (often machine language)

How does an interpreter work (example language)?

It scans and translates one statement at a time and directly executes each translated statement, e.g. Python

Compiler vs. interpreter: key difference?

Compiler translates the whole program before execution; interpreter translates and executes statement by statement

What does a computer system consist of?

Hardware, system programs, application programs

How is an operating system an "extended machine"?

It is an abstraction that hides the messy details of access to the hardware (hardware drivers)

How is an operating system a "resource manager"?

It virtualizes resources and assigns each program time with the hardware, e.g. multi-tasking

Python data type int

Integers: whole numbers, e.g. 3, 300, 200

Python data type float

Floating point: numbers with a decimal point, e.g. 2.3, 4.6, 100.0

Python data type str

Strings: ordered sequence of characters, e.g. "hello", 'Sammy', "2000"

Python data type list

Lists: ordered sequence of objects, e.g. [10, "hello", 200.3]

Python data type dict

Dictionaries: unordered key:value pairs, e.g. {"mykey": "value", "name": "Frankie"}

Python data type tuple (abbreviated "tup" on the slide)

Ordered immutable sequence of objects, e.g. (10, "hello", 200.3)

Python data type set

Unordered collection of unique objects, e.g. {"a", "b"}

Python data type bool

Booleans: logical value True or False

Which of list, tuple, dict and set are ordered, and which are not?

Ordered: list and tuple; unordered: dict and set

What is the difference between a list and a tuple?

Both are ordered sequences of objects, but a tuple is immutable

What does the data type determine, besides usage rules?

The amount of memory

x = 2, y = 5: what are x + y, x - y and x * y?

7, -3 and 10

x = 2, y = 5: what is x / y?

0.4

x = 2, y = 5: what is x % y (modulo)?

2 (modulo gives the remainder of the division)

x = 2, y = 5: what is x ** y (exponentiation)?

32 (2 to the power of 5)

x = 2, y = 5: what is x // y (floor division)?

0 (the division result rounded down to a whole number)

What is the shortcut for x = x + 1, and for which operators does it work?

x += 1; it works for all arithmetic operators (e.g. y -= 1)

x = 3, y = 2: what are x and y after x += 1 and y -= 1?

x = 4, y = 1

Which relational operators exist, and what type of result do they give?

==, !=,

i = 5, j = 7: what are i < j and i >= j?

True and False

Which logical operators exist?

and, or, not

b1 = True, b2 = False: what are b1 and b2, b1 or b2, b1 and not b2?

False, True, True

a = 5, then c = a: what is c?

5 (value assignment copies the value of a to c)

a = 'abc', b = "def": what is a + b (string concatenation)?

'abcdef'

a = 'abc': what is 3 * a (string repetition)?

'abcabcabc'

How do you convert the number 123 to a string?

str(123) gives '123'

a = 'abc', b = "def": what is a[1] + b[2] (extract a char)?

'bf' (indexing starts at 0)

What is the syntax for extracting a substring, and what is a[0::2] for a = 'abc'?

[start:end:step]; a[0::2] gives 'ac'

b = "def": what is b[::-1]?

'fed' (step -1 reverses the string)

Which three control structures are shown for Python?

Conditions (if … else), for loops, while loops

How does the flow of if … else work?

The condition is evaluated; if true, statement1 runs, if false, statement2 runs; then the next statement follows

How does the flow of a for loop work?

Evaluate the loop expression; if the loop condition is met, execute the loop body and change the loop counter, then check the condition again; if not met, continue the program

How does the flow of a while loop work?

Check whether the loop condition is met; if true, execute the loop body and check again; if false, continue the program

How does the for-loop version of factorial(number) work?

result = 1; for i in range(1, number + 1): result = result * i; return result

How does the while-loop version of factorial(number) work?

Start with result = 1 and i = 1; while i <= number: result = result * i and i = i + 1; then return result

Why does the factorial for loop use range(1, number + 1)?

range excludes its end value, so number + 1 is needed to include number itself

In which four ways can an algorithm be formulated?

Natural language, pseudocode, flowcharts, programming language (here: Python)

Natural language and pseudocode example for the sum of 1 to n?

Natural language: "Sum up all values from 1 to n"; pseudocode: sum(1..n) = 1 + (1+1) + (1+2) + … + (n-2) + (n-1) + n

How is the sum algorithm expressed as a Python function?

def sum(n): set sum = 0 and i = 1; for x in range(1, n+1): sum = sum + i and i = i + 1; return sum

Describe the flowchart of the sum example.

Start → sum = 0, i = 1 → decision "i == n": if no, sum = sum + i and i = i + 1, then back to the decision; otherwise return(sum)

Programming = ?

Translation of an algorithm into running software

Which steps lead from Problem to Algorithm and from Algorithm to Code?

Problem → Algorithm: analysis / modelling; Algorithm → Code: programming / coding

Which steps lead from Code to Executable Program and to "Problem solved?"

Code → Executable Program: translation / compilation; Executable Program → Problem solved?: execution / interpretation

Which guiding question belongs to each stage: Algorithm, Executable Program, Problem solved?

Algorithm: How to solve the problem? Executable Program: How does the executable code look like? Problem solved?: Does it solve the problem?

Describe the summary diagram of programming.

Problem → Algorithm → Code → Executable Program → "Problem solved?", with the transitions analysis/modelling, programming/coding, translation/compilation and execution/interpretation

What are the two parts of a for loop?

Loop head and loop body

What is the loop head of a for loop?

A control expression consisting of three parameters: initialization expression, loop test expression and iterator

What is the initialization expression of a for loop?

It defines the initial condition for the loop

What is the loop test expression of a for loop?

The expression that is tested for every execution of the loop body

What is the iterator of a for loop?

It is executed at the end of each loop iteration and changes the variable which is tested

What is the general form of a for loop in Python?

for x in range: statement(s), where the statement(s) form the loop body

Describe the flow chart of a for loop.

Evaluate loop expression → "loop condition met?"; if False: continue program; if True: execute loop body → change loop counter → back to the loop head

How does the iterative factorial function with a for loop work?

def factorial(number): result = 1; for i in range(1, number + 1): result = result * i; return result

Why does the factorial for loop use range(1, number + 1)?

range excludes its end value, so number + 1 is needed to include number itself

What does a while loop do?

It executes its body as long as the loop condition is met

When is the expression of a while loop tested, and what happens if it is False right at the start?

It is tested at the beginning of the loop; if it evaluates to False, the loop body is not executed

What happens once the loop condition of a while loop is violated?

Execution continues with the statement subsequent to the loop

What is the general form of a while loop in Python?

while expression: statement(s)

How does the iterative factorial function with a while loop work?

def factorial(number): start with result = 1 and i = 1; while i <= number: result = result * i and i = i + 1; return result

Transforming a for loop into a while loop (and vice versa): what are steps 1 and 2?

1. Check what the loop's functionality is; 2. Check how often the loop iterates

Transforming a for loop into a while loop (and vice versa): what are steps 3 and 4?

3. Write the loop head of the new loop; 4. Copy the loop body and adjust the loop counter's variable

How is the factorial for loop transformed into a while loop?

Initialize i = 1 before the loop; new loop head: while i <= number; copy the body result = result * i and add i = i + 1 as the loop counter adjustment

How do you write the for loop "for i in range(0, 10, 2): print(i)" as a while loop?

i = 0; while i < 10: print(i); i += 2 (range(0, 10, 2) yields 0, 2, 4, 6, 8)

What do the iterative and the recursive factorial function have in common?

The same signature (def factorial(number)), so the recursive version can be used just like the iterative one

When is an algorithm recursive?

If it calls itself

How is n! (factorial of n) computed?

n! = 1 * 2 * 3 * 4 * ... * n

What is the formal (recursive) definition of the factorial?

1! = 1; n! = n * (n-1)! for n > 1

How is the computation of n! reduced in the recursive definition?

n! is reduced to the computation of (n-1)!, which in turn is reduced to (n-2)!, and so on

Why does a recursive function require a termination condition?

Without it, the function would be an infinite loop

How does the recursive factorial function work?

def factorial(number): if number <= 1: return 1 (base case); else: return number * factorial(number - 1) (recursive call of the function itself)

What is the base case of the recursive factorial function?

number <= 1: the function returns 1

How does the recursive computation of factorial(5) unfold step by step?

factorial(5) → 5 * factorial(4) → 5 * 4 * factorial(3) → 5 * 4 * 3 * factorial(2) → 5 * 4 * 3 * 2 * factorial(1)

Which rule is applied in each expansion step of factorial(5), and what is checked before?

Before each step, number <= 1 evaluates to False (5, 4, 3, 2); then factorial(n) = n * factorial(n-1) is applied

How does the recursion of factorial(5) end?

1 <= 1 evaluates to True, so factorial(1) = 1; the result is 5 * 4 * 3 * 2 * 1 = 120 = factorial(5)