Tricky exercises
Module 1 — Algorithmic Patterns
How to break down a problem into steps.
What does “low level” mean?
In this module you implement functions that have long been ready in the standard library (max(), sort(), collections.Counter). That's intentional: Anyone who has sorted things themselves or searched for a maximum understands much better what happens when they simply call up the standard functions later.
Three recurring patterns
- Filters/Traces: walk over a list and sort values into one of several auxiliary lists depending on the condition.
- Reduce: walk over a list and derive a single value from it (sum, maximum, ...).
- Mapping: apply a function to each element and collect the results in a new list.
Each of these patterns appears at least once in the exercises.
NoteEntries in the exercises
In most exercises you read the values input() (known from the “Variables” module) — the check automatically feeds in the input and compares your output line by line. With the squares-exercise (mapping) However, you define the list yourself; The focus there is on writing the function and mapping it. The examples here use fixed values so you can run them directly.
Example 1.1 — Mapping: Apply function to each element
Loading Python…Tests
Module 2 — Find the maximum & separate into two lists
Two classic reduction and filter patterns.
Find maximum manually
The pattern: Place one Auxiliary variable to the first value, loop over all other values and replace the auxiliary variable if you see something larger.
groesste = zahlen[0]
for z in zahlen:
if z > groesste:
groesste = z
The same pattern works for the minimum — simple < the >.
Example 2.1 — Maximum without max()
Loading Python…Tests
Split a list into two lists
Leg before the loop returns two empty lists. Within the loop, one person decides if-Query which of the two lists the current element goes into.
Example 2.2 — separate even/odd
Loading Python…Tests
Module 3 — Count frequencies in a dictionary
The classic "Counter" pattern.
Identification
A dict is perfect for counting how often something occurs: key = the counted object, value = current counter. The first time it occurs, the key is included
1 created, then each time around 1 increased.
if x in ergebnis:
ergebnis[x] = ergebnis[x] + 1
else:
ergebnis[x] = 1
New here: x in ergebnis checks whether x already one
Key is in the dictionary (provides True/False). This is how you distinguish “first occurrence” from “already seen”.
Example 3.1 — Counting letters
Loading Python…Tests
TipAlso for dictionaries as input
If your input is already a list of dictionaries (e.g. several students), you simply follow along in the loop schueler["name"] to the value — as shown in the Dictionary lesson.
Module 4 — Sorting with comparison & iterative approximation
Two classic while algorithms.
Bubble sort: compare and swap
A very simple sorting: You run through the list again and again and compare two neighbors at a time. If the one on the left is bigger than the one on the right, swap them. After several iterations the list is sorted.
if a[j] > a[j + 1]:
temp = a[j]
a[j] = a[j + 1]
a[j + 1] = temp
In Python you can also swap in one line: a[j], a[j+1] = a[j+1], a[j].
Two new building blocks: Bubble sort needs one Loop within the loop
(the outer one repeats the runs, the inner one compares the neighbors) — that is the first
boxed loop in this row. And a = zahlen.copy() creates its
Copy the list so that the original list of the caller remains unchanged.
Example 4.1 — Bubble sort by hand
Loading Python…Tests
Iterative approximation with while
Very often you want to repeat an operation until a limit is reached — e.g. double until the value is at least 100. One while-Loop with a mutable variable and a step counter is just the right pattern.
Example 4.2 — Doubling to the limit
Loading Python…Tests
Sources & further literature
Where the knowledge imparted here is officially documented.
Official Python documentation
- Python tutorial — 4. More Control Flow Tools: docs.python.org/3/tutorial/controlflow.html
- Python tutorial — 4.7. Defining functions: docs.python.org/3/tutorial/controlflow.html#defining-functions
- Python tutorial — 5.1. More on Lists: docs.python.org/3/tutorial/datastructures.html#more-on-lists
- Python HOWTO — Sorting (Context for Python's built-in sorting — but here we implement it ourselves): docs.python.org/3/howto/sorting.html
- PEP 8 — Style Guide for Python Code: peps.python.org/pep-0008
Tutorials & Manuals
- Real Python — Conditional Statements in Python: realpython.com/python-conditional-statements
- Real Python — Defining Your Own Python Functions: realpython.com/defining-your-own-python-function
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms. 4. Edition, MIT Press, 2022 — Background on sorting and search algorithms.
- Theis, Thomas: Getting started with Python. 7. Edition, Rheinwerk Verlag, 2023 — Chapters on functions, lists and dictionaries.
- Klein, Bernd: Introduction to Python 3. 4. Edition, Hanser Verlag, 2021 — Sections on data structures and algorithms.