Computational Thinking

and
Introduction to Programming
CTIP152

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming CTIP152

 © STADIO
No part of this publication may be reproduced, stored in a retrieval system or transmitted in
any form or by any means – electronic, electrostatic, magnetic tape, mechanical,
photocopying, recording or otherwise.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming CTIP152

 Note

The content of the STADIO Study Guides and teaching documents is not intended
to be sold or used for commercial purposes. Such content is in essence part of
tuition and constitutes an integral part of the learning experience, regardless of
mode.

Links to websites and videos were active and functioning at the time of
publication. We apologise in advance if there are instances where the owners of
the sites or videos have terminated them. Please contact us in such cases.

A Glossary of terms is provided at the end of this study guide to clarify some
important terms.

Any reference to the masculine gender may also imply the feminine. Similarly,
singular may also refer to plural and vice versa.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming CTIP152

 Table of contents

Heading Page number

Contents
MODULE PURPOSE AND OUTCOMES 1
TOPIC 1 COMPUTATIONAL THINKING 2
1.1 Introduction 2
1.2 Defining computational thinking 4
1.3 Skills associated with computational thinking 4
1.4 Steps in solving a simple problem 7
1.5 Solving a more complex problem 9
Summary 13
Self-Assessment Questions 14
TOPIC 2 ALGORITHMS AND DATA STRUCTURES 16
2.1 Introduction 16
2.2 Algorithms 17
2.3 Representing algorithms 20
2.4 Revisiting the definition of algorithm 31
2.5 Basic constructs for creating algorithms 32
2.6 Basic data structures 39
Summary 41
Self-Assessment Questions 42
TOPIC 3 PYTHON PROGRAMMING LANGUAGE 44
3.1 Introduction 44
3.2 Program = Algorithm + Data structure 45
3.3 Introduction to Python 46
3.4 Your first Python program 50
3.5 Executing a Python program 54
3.6 Debugging your program 56
Summary 59
Self-Assessment Questions 59
TOPIC 4 BASIC PROGRAMMING CONSTRUCTS 62
4.1 Introduction 62
4.2 Using predefined Python modules and for loops 63
4.3 Functions 66
4.4 Conditional statements 73
4.5 Fruitful functions and code development 79

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming CTIP152

4.6 Iteration again 84
Summary 97
Self-Assessment Questions 97
TOPIC 5 COMPOUND DATA STRUCTURES, MODULES AND FILES 100
5.1 Introduction 100
5.2 String manipulation 101
5.3 Using tuples 111
5.4 Manipulating lists 114
5.5 Modules 128
5.6 Files 135
5.7 List algorithms 139
Summary 146
Self-Assessment Questions 147
TOPIC 6 RECURSION AND OTHER ADVANCED CONCEPTS 149
6.1 Introduction 149
6.2 Recursion 150
6.3 Exception handling 155
6.4 Dictionary data structures 161
Summary 165
Self-Assessment Questions 166
GLOSSARY OF TERMS 167
REFERENCES 173
Answers to Self-Assessment Questions 175
Topic 1 Self-assessment answers 175
Topic 2 Self-assessment answers 177
Topic 3 Self-assessment answers 179
Topic 4 Self-assessment answers 181
Topic 5 Self-assessment answers 184
Topic 6 Self-assessment answers 188

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming CTIP152

 Module purpose and outcomes

Module Purpose

Efficient and effective problem solving is a skill that is of benefit to all individuals
in their everyday life. In the field of computing, problem solving as well as
familiarity with computer programming concepts, development of computer
programs, and the syntax and semantics of programming languages are
fundamental to successful software development.

The main aim of this module is to first introduce computational thinking as a

systematic approach to problem solving with the solution expressed in such a
way that it can be carried out by a computer. Thereafter, all aspects of
programming, from designing an algorithm and coding this algorithm to develop
a program, to debugging and executing the program, are covered.

In keeping with this aim, the main focus of the module is on coding, where you
will be exposed to the Python programming language, from the basic
programming constructs (sequencing, decisions and looping) and data structures
(such as simple types and lists) to more advanced constructs (such as the use
of functions and recursion) and more complex data structures (such as
dictionaries).

Module Outcomes

Upon successful completion of this module, you will be able to:

1. Apply problem solving and programming skills to design solutions to non-
trivial problems.
2. Apply computational thinking in creating algorithms (represented as
pseudocode or flowcharts) to solve simple mathematical and logic
problems.
3. Show mastery of basic programming constructs in the context of the
Python programming language by converting hand-crafted algorithms
into Python code.
4. Design efficient Python solutions to simple mathematical and logic
problems.
5. Execute, debug and create simple test procedures for Python programs.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
1
 Topic 1
Computational thinking

1.1 INTRODUCTION

This topic relates to the following module outcomes:

1. Apply problem solving and programming skills to design solutions to non-

trivial problems.
2. Apply computational thinking in creating algorithms (represented as
pseudocode or flowcharts) to solve simple mathematical and logic
problems.

On completion of this topic on computational thinking, you will understand what

computational thinking is all about and how it relates to problem solving, which
underpins most other processes in computer programming.

To understand how computational thinking, problem solving, and computer

programming fit together, we need to look back in history. When the first
computers were developed, the only way of communicating with them was
through machine language, which consists of binary digits, i.e., zeroes and ones
only. Thus, in the early days, programming of computers remained in the hands
of a few highly trained scientists. It was not until high-level programming
languages were developed that access to computational devices became more
widespread.

However, before programmers actually write code in a particular programming

language to solve a given problem, they first need to understand exactly what
the problem entails and have some idea of how they will go about solving it. This
is where computational thinking fits in, as it provides the skills to achieve the
problem solving step. Once the programmer has a solution or solutions in mind,
possibly obtained by breaking the original program down into smaller problems,
then he can proceed to express these ideas in a more formal manner, by selecting
appropriate ways to store any data involved (i.e., choosing the data structures)
and representing the solution idea in a manner that can more easily be written
in programming language code (i.e., as an algorithm).

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
2
Note that the concepts of data structures and algorithms will be defined and
discussed fully in the next topic, on completion of which the first two module
outcomes will be fully satisfied.

In this topic, we focus purely on the skills that computational thinking provides
to facilitate problem solving, and how to apply these skills in various problem
scenarios. Note that what is covered in this topic, is equally applicable in
everyday life scenarios, and you are encouraged to practice these skills in
scenarios unrelated to computational problems as well.

In this topic, you will gain knowledge in the following areas:

1. A definition of computational thinking

2. Skills associated with computational thinking
3. Applying computational skills to solve a simple problem
4. Applying computational skills to solve a more complex problem

The following assessment criteria for sub-topics relate to module outcomes 1 and
2:
 Computational thinking skills: What are the necessary skills and how can
these be applied to facilitate problem solving.
 Computational problems: Suggest high-level solutions to solve simple
logic and mathematical word problems.

Note
Your lecturer will advise which of the activities and tasks going forward should
be handed in for assessment. It would be prudent, however, for your own
learning to complete and keep a record of all solutions to activities and self-
assessment questions as you progress through this module.

New key words or technical concepts are written in italics at first use – these are
also included in the Glossary at the end of this document. A different font
(courier new) is used for all actual computer code given in the text. Large
sections of code are also differentiated by being enclosed by a blue rectangle
without any heading.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
3
1.2 DEFINING COMPUTATIONAL THINKING

Prescribed reading
Read the viewpoint article published by Jeannette Wing in 2006 on Computational
Thinking.
Available at: [Link]

Although the term computational thinking had been used in some computing
circles, Jeannette Wing brought it to the fore in her PhD research in 2006. She
describes it as “the thought processes involved in formulating problems and their
solutions so that the solutions are represented in a form that can effectively be
carried out by an information-processing agent” (Wing, 2006). A more informal
definition of computation thinking is “the mental skill to apply concepts, methods,
problem solving techniques and logic reasoning … to solve problems in all areas ”
(Wang, 2016).

Since 2006, computational thinking has been adopted in school teaching at all
levels and in a variety of subjects, including mathematics, computing, life
sciences and physics.

1.3 SKILLS ASSOCIATED WITH COMPUTATIONAL THINKING

When applying computational thinking, some or all of the following skills are
employed: comprehension, analysis, evaluation and prioritisation of information,
decomposition, pattern recognition, generalisation/abstraction, algorithmic
thinking, and adaptive reasoning.

Conversely, in the application of computational thinking these same skills are

practiced and in so doing, improved over time.

1.3.1 Comprehension
Comprehension relates to understanding thoroughly the problem to be solved.
This normally relies on a certain level of language skills (as problems are typically
described in a natural language) and if the problem is mathematically related,
also numeracy skills.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
4
Misunderstanding or not understanding a problem may be the result of ambiguity
in the problem description. If this is the case, the problem description needs to
be clarified to remove all ambiguity.

Without fully understanding what the problem is all about, carrying on with the
problem-solving process may be futile.

1.3.2 Analysis, evaluation, prioritisation of information

Not all information given in a problem statement is equally important and thus,
analysing and prioritising the information that forms the crux of the problem
helps remove complexity and allows one to focus on that which is most relevant
to start with.

Note that we often return to the information that has been discarded in this step,
and extend our solution to take this into account so as to solve the initial problem
fully.

Having prioritised what information is important and discarded that which is not
needed for the first attempt at finding a solution, we synthesize this information
(that is, put it back together) to rephrase the problem statement in a simpler
form.

1.3.3 Decomposition
Decomposition refers to breaking down a problem or task into smaller parts or
less complex sub-problems, which can be more easily solved. Once a solution
process has been found for each of the sub-problems, combining these processes
in some order can contribute to finding a solution to the original problem.
However, care must be taken to ensure that the interactions between the
individual solution components is well understood, and that the method in which
the solutions are combined is correct.

1.3.4 Pattern recognition

Pattern recognition implies looking for a repeating pattern in a problem
description that may lead to simplifying the problem by representing it in new
and different ways, or finding repeating actions that may be used to solve a
problem more easily.

1.3.5 Abstraction and generalisation

Wing (2006) describes abstraction as the ability to handle complexity by thinking
in terms of conceptual ideas rather than the detail. This helps to reduce the
complexity of a problem as it helps the problem-solver decide what to emphasize

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
5
and what to filter out, thus representing the problem in a different way. By
ignoring unimportant information, we can get a clearer idea of what the problem
is and how it should be solved. This idea is also referred to as a model.

As an example, assume that we need to calculate the area of three different

kinds of shapes, namely rectangles, circles and triangles. We could first apply
decomposition to this problem and break up the problem into three distinct tasks,
namely finding the area of rectangles, finding the area of circles, and finding the
area of triangles.

Then, for each task we could apply abstraction and consider only the relevant
information of the shapes. For the rectangle, for example, we know that each
rectangle has a specific width, a specific height and an area calculated as width
x height. However, in order to solve the problem of calculating the area for a
rectangle, we do not need to concern ourselves about the actual widths and
heights of the different rectangle shapes. These specifics can be ignored, and we
merely need to consider the general case, namely that area of a rectangle =
height x width. Then when given specific height and width values, we can solve
each specific problem. Thus, by ignoring irrelevant information through
abstraction, we can more easily create a generalised solution.

A similar abstraction can be applied independently to the other two shapes as

well.

For a non-computing based example of abstraction we can consider what we

need to understand about the mechanics of a car in order to drive the car. For
example, we would need to know how to start and stop the car, change gears,
and also use the clutch, break and accelerator pedals. We would also need to
know how to steer the car together with a few other aspects of the car. However,
we would not need to know anything about how the engine of the car is
assembled and how the various components interact to make the car move.
Hence, the complex workings of the engine are abstracted away and we only
need to understand a simplified model of the car when learning how to drive a
car.

1.3.6 Algorithmic thinking

In the next topic, we discuss algorithms in great detail. For now, it will suffice to
define an algorithm as a blueprint (or recipe) for creating a computational
solution to a problem.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
6
Algorithmic thinking is therefore the skill that enables us to develop step-by-step
instructions that can be used in such a solution. These instructions can later be
converted into a format that a computer can understand and execute to solve
the given problem.

1.3.7 Adaptive reasoning

Adaptive reasoning, which is the connective skill in computational thinking,
represents the ability to think logically about concepts and situations and
specifically the relationships between them. This includes informal explanation
and justification of an approach, as well as inductive reasoning based on skills
like identifying patterns and abstraction. Inductive reasoning is the ability to take
solutions to very specific problems and induce a solution to a more general
problem.

For example, one could start by solving a simpler, more specific version of the
original problem, where this specific version has been identified through
analysing and prioritising the information given about the problem. Then over
several iterations, the solution to the more specific problem can be expanded
repeatedly until it eventually provides a solution to the more general original
problem specified.

This skill also allows one to adapt what has already been learned generally and
to apply this to a new problem – this is known as deductive reasoning. Deduction
is often needed when implementing a pattern-based approach to solving a
problem.

1.4 STEPS IN SOLVING A SIMPLE PROBLEM

In this section, we show how some of the skills described above can be used
when applying computational thinking to solve an example problem.

The problem statement is:

Find the greatest common divisor (or greatest common factor) of two or
more positive integers.

It is important to note that not all the computational thinking skills have to be
used explicitly when solving a problem. Moreover, the order that we apply these
skills is not necessarily as given below. For complex problems, we might also

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
7
need to apply some of the skills multiple times in order to develop a final solution
for the given problem.

Step 1: Understand the problem

For this problem, understanding what is meant by the term greatest common
divisor (GCD) is critical to understanding what might be involved in solving the
problem.

Wolfram MathWorld (2022) defines this term as: ”The greatest common divisor
of two positive integers a and b is the largest divisor common to a and b “.

Divisor may also need further clarification. According to Wolfram MathWorld

(2022) a divisor of a number n is a number d which divides (or goes into) n
(written as d |n). A divisor is also called a factor.

Thus, having clearly defined the mathematical terms used in this problem
statement, the initial understanding is that we need to find divisors of given
positive integers and then identify those divisors common to all the integers.

Step 2: Analyse, evaluate and prioritise information

The problem statement requires that we find the GCD of two or more integers.
To simplify this, we could limit our effort to finding the GCD of a fixed small
number of integers, in this case two. Later, we can extend the solution to any
number of integers.

We rewrite the initial problem to be:

Find the greatest common divisor of two positive integers.

Step 3: Decompose the problem

In this step, we attempt to break down the problem into a number of sub-
problems. For our example, these sub-problems might be:
a) Calculate all divisors for the first positive integer.
b) Calculate all divisors for the second positive integer.
c) Determine the divisors common to both integers.
d) Extract the largest divisor.

Step 4: Identify patterns

It is clear that in step 3(a) and (b) the same calculation is performed, but on
different numbers. This represents a pattern of tasks.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
8
It might also be obvious from mathematical principles, that finding common
values could be done by using some form of intersection of sets.

Step 5: Use abstraction

Given that this problem is a fairly simple one, it is difficult to apply abstraction.
However, one might argue that finding the divisors is the more complex part of
the problem, so one could abstract away any mention of divisors, and start with
two made up sets of positive integers, and first find the common integers in the
two sets, and then extract the maximum common value.

Once we have solved sub-problems defined as 3(c) and 3(d), we can deal with
solving sub-problems 3(a) and 3(b). In other words, we are delaying dealing with
the complex part of the problem, that is, that the sets of numbers need to be
divisors of the respective numbers.

Step 6: Think algorithmically

On completion of step 5 above, we should be in a position to develop a set of
instructions for solving the simplified problem, namely, finding the GCD of two
positive integers.

Step 7: Apply adaptive reasoning

Once we have a working solution to the simplified problem, we can then extend
the instructions making up the solution to find the GCD of any number of positive
integers.

1.5 SOLVING A MORE COMPLEX PROBLEM

This problem is taken from Gouws (2013) and is stated as follows:

Suppose you are a rock climber, standing at the bottom of a rocky mountain.
The mountain consists of rocks coloured with four different colours: blue, green,
red and yellow, as shown in Figure 1.1.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
9
 Figure 1.1: Rock climber’s mountain (Gouws, 2013)

Your objective is to get to the top of the mountain, always moving from one rock
surface to another adjoining rock surface, but never jumping over a rock or a
crevice. As you climb to the top, your route must contain a consecutive series of
four colours repeating continuously. For example, yellow-green-blue-red, and
then again yellow-green-blue-red, and so on.

What route should you take to get to the top by climbing up or around the least
number of rocks?

Step 1: Understand the problem

For this problem, understanding what movement is allowed by the climber is the
first priority. Movements depicted by black arrows in the illustration below are
allowed, while those depicted by orange arrows are not.

Step 2: Decompose the problem

Next, we attempt to break down the problem into sub-problems or tasks. For our
example, these tasks might be:
a) Determine all possible colour sequences — there are 24 in total, calculated
as 4x3x2x1.
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
10
 b) Determine a route using each colour sequence.
c) Determine the shortest route.

Step 3: Analyse, evaluate and prioritise information

The problem statement requires that we find the shortest route, but initially we
should just focus on finding a single route to the top using one of the colour
sequences.

Further analysis of the 24 possible colour sequences shows that there are in fact,
duplicate sequences. When used repeatedly, combinations like blue-red- yellow-
green and yellow-green-blue-red represent the same basic pattern, just with a
different starting colour.

Step 4: Identify patterns

This problem is all about following a pattern repeatedly to find a route to the top.

However, by considering what options are available to reach the topmost rock,
we can reduce the number of colour patterns further. To get to the red surface
at the very top we can only step from a yellow or green surface. Thus, valid
colour sequences must include yellow-red or green-red if we are climbing from
the bottom of the mountain.

The number of colour sequence possibilities (taking into account the cyclical
nature of the pattern as discussed in step 3) can thus be reduced to only four
combinations:

1. yellow → blue → green → red

2. green → blue → yellow → red
3. blue → yellow → green → red
4. blue → green → yellow → red

Step 5: Think algorithmically

Given that there are fewer path options near the top of the mountain, it might
be easier to find a path from the top downwards, following a chosen colour
pattern. As soon as we get to a point where the colour pattern cannot be adhered
to, we can discard that colour pattern and try the next one.

To set this in motion, we need to start at red in the first colour combination (as
given above), and follow the colour sequence in reverse (as we are moving down
the mountain), trying to find rocks in the order, red, green, blue, yellow, red,

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
11
green, blue, yellow, and so on. We see that this sequence cannot be adhered to
when we reach our second red rock, and thus this colour pattern is discarded.

Options 2 and 3 also fail. Finally, using option 4 in reverse (red, yellow, green,
blue) provides a route from the top to the bottom. See Figure 1.2 for the
successful path.

Step 6: Apply adaptive reasoning

To confirm whether the solution found above is the best (i.e., shortest solution),
we need to check any remaining colour combinations to see if they yield a valid
route. If not, our problem is solved – as is the case in this example. If there is
more than one possible route, we need to determine which of the routes found
is the shortest.

Figure 1.2: Valid route to the top of the mountain (Gouws, 2013)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
12
 Summary

This topic focused on developing an understanding of computational thinking and

how the skills involved in this process can be used to aid computational problem
solving. Since problem solving is fundamental to programming, anyone wishing
to become a competent programmer, must first become a competent problem
solver.

Topic 1 introduced some of the skills involved in computational thinking, namely

understanding the problem, analysis and prioritisation of problem information,
decomposition of the problem into smaller tasks or sub-problems, finding
patterns, thinking algorithmically, and applying adaptive reasoning.

These skills were later used to assist in solving simple example problems. Whilst
there is no single method to go about solving all problems, by applying various
of the skills introduced, problems can be simplified, making their solution easier.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
13
 Self-Assessment Questions

These questions all relate to logic or mathematical problems that you should be
able to solve if you apply some of the computational thinking skills discussed in
this topic.

1. If you write all the numbers from 1 to 100, how many individual digits have
you written?

2. A man walks a total of 200 km in 5 days, each day walking 10 km more than
the previous day. How many km did he walk on the first day?

3. A message can be sent as a string of digits using the standard alphanumeric

code where
A=1, B=2, C=3, etc. Thus, 121 could be ABA or LA or AU.
What common English word has the code 2 1 1 2 1 2?

4. What is the smallest decimal number consisting of only 1's and 0's that is
divisible by 15?

5. Z, Z, Y, Z, Y, X, Z, Y, X, W, Z, Y, X, W, ... Which letter comes next?

6. One of the following statements is true. Which one?

a) Only one of these statements is false.
b) Only two of these statements are false.
c) Only three of these statements are false.
d) Four of these statements are false.
e) All five of these statements are false

7. You are climbing a snowy mountain that is 190 m high. It takes you 5 mins
to run 40 m up the mountain, but then you need 15 min to recuperate. While
standing still and catching your breath, you slide 20 m down the mountain.
How many minutes will it take for you to reach the top of the mountain? (Your
answer should be rounded up to a multiple of 5 minutes.)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
14
8. You need to drive an ambulance to X, the scene of an accident, as quickly as
possible. Below is a map of the town, where A denotes the ambulance station,
and each intersection is marked with a letter B, C, D, etc. The numbers along
the road show how long it will take to drive that road. Find the quickest route
to get from the ambulance station to the accident and indicate this route
using the letters for the intersections: A, B, C, D, etc. Also include the total
time for the route.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
15
 Topic 2
Algorithms and data structures

2.1 INTRODUCTION

This topic relates to the following module outcomes:

1. Apply problem solving and programming skills to design solutions to non-

trivial problems.
2. Apply computational thinking in creating algorithms (represented as
pseudocode or flowcharts) to solve simple mathematical and logic
problems.

On completion of this topic on algorithms and data structures, you will

understand the basic components needed to design a computational solution to
a given problem. Before baking a cake, for example, we would need both the
ingredients for the cake, as well as instructions on how to combine and process
these ingredients. In a programming context, data structures are synonymous
with the ingredients used in baking, while algorithms can be likened to the
instructions or recipe provided for baking the cake. This topic therefore, provides
the foundation for understanding computer programming, which is introduced in
Topic 3.

In this topic, you will gain knowledge in the following areas:

1. Algorithms
2. Representation of algorithms
3. Basic data structures

The following assessment criteria for sub-topics relate to module outcomes 1 and
2:
 Algorithms: Discuss what properties an algorithm must satisfy and why.
 Flowcharts and pseudocode: Develop algorithms for simple everyday
tasks represented as a flowchart and/or in pseudocode.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
16
 Computational problems: Develop algorithms to solve simple logic and
mathematical word problems.
 Data structures: Explain the use of a data structure and give examples
of some basic types used in programming.

2.2 ALGORITHMS

Prescribed reading
Read the Notes on Algorithms written by the Ada Developers Academy (2016) to
help you understand what an algorithm is and what properties it needs to satisfy.

2.2.1 What is an algorithm?

In Section 2.1 we introduced the analogy of baking a cake. We also suggested

that the recipe, which gives the instructions on how to combine the ingredients
and other processes required to bake the cake, could be likened to the term
algorithm, when used in the context of computer programming.

Essentially an algorithm is just a set of instructions that if followed correctly (by

either a computer or a human), would lead to a solution for the given problem.
Knuth (1997) in his definitive computer programming guide, “The Art of
Computer Programming: Volume 1: Fundamental Algorithms” defines an
algorithm as: “Besides merely being a finite set of rules that gives a sequence of
operations for solving a specific type of problem, an algorithm has five important
features”, which he later explains as being finiteness, definiteness, input, output
and effectiveness.

For now, we define an algorithm informally as a list of instructions for performing

a specific task or solving a particular type of problem. Examples of such lists of
instructions for everyday tasks are:

 a pattern for knitting a jersey

 a recipe for cooking a meal
 instructions for making tea
 instructions for making a kite
 directions for travelling from one town to another
 instructions for filling a bath
 instructions for performing a mathematical calculation.
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
17
Let us now look at an algorithm for making tea. We could write this as:
1. boil water
2. put tea into pot and add water
3. wait
4. pour milk into cup
5. pour tea into cup
6. the tea is made

These instructions might be good enough for someone who knows how to
perform each of the individual instructions, but they might need to be more
precisely specified depending on who will be carrying out the instructions.
For example, step 1 above could be fleshed out as:
1.1 fill the kettle with water
1.2 switch on kettle
1.3 wait till water is bubbling
1.4 switch off kettle
1.5 the water has boiled

Similarly, step 2 could be expanded as:

2.1 take 1 teabag per person
2.2 put into teapot
2.3 take kettle
2.4 pour water into teapot

Again these steps could be made more precise until you are sure that the person
who will be executing the instructions (performing the task) will be able to do so
without making any mistakes.

Another example of an algorithm is a list of instructions to be followed to make

a kite.

Kite construction algorithm:

1. Construct kite's frame using 2 sticks
2. Mount fabric on the frame
3. Bow the shorter stick in the frame away from the fabric by tying
its ends together with a piece of string 3/4 the length of the stick
4. Make the kite's harness
5. If the kite will be flown in stronger wind, attach kite's tail to
bottom of frame
6. Attach tow line to kite
7. Kite is ready to fly
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
18
Once again we should be aware that this "algorithm" is dependent on who is
going to be making the kite. Someone who has never seen or flown a kite would
probably not be able to use it to construct a kite as these instructions are fairly
imprecise and ambiguous.

Activity
Select a process that you are familiar with (e.g., boiling an egg, setting a table,
washing the dog, etc.) and write down the steps that need to be followed to carry
out the process. Ask a friend who is not familiar with this task to carry out the
steps, and see whether the process can be done successfully.

CAVEAT: Do not choose a process that is dangerous or in which someone can

get hurt!

2.2.2 Why do we need algorithms?

To be able to develop a computerised solution to solve a particular problem, the

programmer needs to convert the problem description into a list of instructions
that a computer can process to produce the answer to the problem. This applies
whether the program is to add together a list of numbers, calculate a company
payroll or control the space shuttle. Deriving an algorithm is an important step
along the way.

This process for developing a computerised solution can be described as a series

of steps (some of which you will already have encountered in Topic 1, as
computational thinking is very much part of this development process):

1. Define the problem: the programmer must carefully study the problem
until he clearly understands what is required.

2. Outline the solution: the programmer must decide what tasks or

operations are required to solve the problem.

3. Develop the outline into an algorithm: the programmer must expand

the outline into a set of precise steps that describe exactly the task to
be performed and the order in which these steps are to be carried out.

4. Test the algorithm: the algorithm needs to be walked through line-by-

line (also called desk-checking) using test data to check that the
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
19
 algorithm will actually achieve what it was created to do. It is important
to realise that such desk-checking will not prove that the algorithm will
always work correctly for all data, but it can demonstrate the presence
of logic errors. Formally proving an algorithm (or program) is correct is
very difficult to do and is beyond the scope of most undergraduate
programming courses.

5. Code the algorithm using a specific programming language: at this

point the programmer can translate the algorithm into a high-level
programming language. It is advisable that this step is first carried out
on paper.

6. Run the solution code on a computer: the code is first typed into the
computer using an editor or development environment. The solution
code is then translated into lower level code that is understandable to
the computer. If any errors are found during this process, these will
need to be corrected. Finally, the solution code can be tested to make
sure it behaves as expected.

In some instances there may be more than one way to solve a particular problem.
In other words, we could derive more than one algorithm to solve the problem.
This means that we must have some way of choosing the "best" algorithm to do
the job. This is a topic of its own, known as “analysis of algorithms” and may be
discussed in more advanced modules.

2.3 REPRESENTING ALGORITHMS

2.3.1 A simple example

Recall that earlier we said that informally, an algorithm is a list of instructions for
performing a specific task or solving a particular type of problem. Let us now
consider one of the tasks mentioned previously. Assume that a robot will be
completing the task of filling your bath.

The instructions you give the robot could be:

Go into the bathroom and go to the bath. Put the plug in and then turn on both
taps. When there is enough water in the bath and the water is the right
temperature, turn off both taps.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
20
These instructions are, however, imprecise:
 What is enough water?
 What is the right temperature?

They are also ambiguous:

 Where is the plug inserted?

It is very important to consider to whom/what you are giving the instructions;

that is, you have to consider the agent or device that will be executing the
instructions. A very "intelligent" robot or a human might be able to interpret the
instructions you have given. However, to have the algorithm executed by a
computer or dumb robot, the instructions would have to be much more precise.

A more precise list of instructions to solve the problem given above could be:
1. Go to the bathroom
2. Go to the bath
3. Push the bath plug into the plug hole in the bath
4. Turn on both taps
5. Wait one minute
6. Check the depth of water in the bath. If this is less than 6 cm go
to step 5
7. Turn off both taps
8. Check the temperature of the water. If the temperature is less
than 30˚C, go to step 10. If the temperature is greater than
40˚C, go to step 14
9. Go to step 18
10. Turn on the hot tap
11. Wait one minute
12. Turn off the hot tap
13. Go to step 8
14. Turn on the cold tap
15. Wait one minute
16. Turn off the cold tap
17. Go to step 8
18. Stop (the bath is filled with water at the right temperature)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
21
 Activity
Consider whether the list of instructions given above will allow the robot to fill
the bath properly. Are there any ambiguities or imprecise instructions? If so, how
can you rewrite the poorly worded instruction to make it less ambiguous or less
imprecise?

2.3.2 Flowcharts

What we have seen above is one way to specify an algorithm by writing the steps
in some natural language, in this case English. There are other ways to specify
algorithms. One of these is by making use of a flowchart. Figure 2.1 gives the
meaning of some commonly used flowchart symbols, while a flowchart to solve
the bath filling problem is shown in Figure 2.2.

Figure 2.1: Basic flowchart symbols and their meanings

Flowcharts can be used to represent most algorithms but they can become
cumbersome; so a different representation has become more popular. We
discuss this in the next subsection.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
22
 Start

Go to bathroom

Go to the bath

Push bath plug into plug hole

Turn on taps

Wait 1 min

Check water depth

< 6 cm
Yes
No

Turn off hot tap Turn off taps

Wait 1 min Check temperature

Turn off cold tap

Turn on hot tap < 30 deg

Yes
Wait 1 min
No

> 40 deg Turn on cold tap

Yes

No

Stop

Figure 2.2: Flowchart to solve the bath filling problem

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
23
2.3.3 Pseudocode

Let us consider a simple numerical problem. Suppose we want to sort three

numbers (or integers) in some order. We should assume that each number is
written on a piece of paper and stored in its own box, and the boxes are placed
on a table in a row. Therefore, when we need to sort the numbers, what we
actually need to do is arrange the numbers in the boxes in such a way that the
box on the left contains the smallest number, the box in the middle contains the
next number, and the box on the right contains the largest number.

For example, assume we are given three boxes, each containing a piece of paper
with one of the numbers 1, 13, -4 written on it, and placed in a row from left to
right on a table. We have been asked to sort the numbers into ascending order.
It is easy to see that the answer is -4, 1, 13, but how do we actually do the
sorting?

One way to do the sorting is:

1. order the first pair
2. order the second pair
3. order the first pair again

By “order” we mean look at the values of the two numbers in their boxes and
rearrange the numbers in the two boxes so that the smaller number is in the box
on the left while the larger number is in the box immediately to its right. This
rearrangement might involved swapping the pieces of paper in the two boxes.

Let us see how this works.

Given the numbers: 1 13 -4

order first pair
Result: 1 13 -4
order second pair
Result: 1 -4 13
order first pair again
Result: -4 1 13

Let us try this again using different numbers:

Given the numbers: 17 6 11

order the first pair
Result: 6 17 11

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
24
 order the second pair
Result: 6 11 17
order the first pair again
6 11 17

For yet another example, suppose we start with these numbers:

11 6 17
Then to sort the three numbers we would:
order the first pair
Result: 6 11 17
order the second pair
Result: 6 11 17

In this case, ordering the second pair did not require doing anything with the
pieces of paper in the boxes as the smaller number was already in the box to the
left. So we now know that the second pair of numbers are in order and we know
from the first ordering that the first pair of numbers are also in order. This means
that we do not have to re-order the first pair (because we have not changed
anything). So we see that for certain inputs we can cut down the number of
comparisons we need to do.

Our approach to solving this problem can then be outlined as:

1. order the first pair
2. order the second pair
3. if necessary order the first pair again

Using the idea outlined above we can derive an algorithm to solve this problem
(in this example, we have given the boxes names to differentiate them).

Algorithm 2.1: Algorithm to sort three numbers

1. Place first number in box x

2. Place second number in box y
3. Place third number in box z
4. If number in box x < number in box y, go to step 6
5. Swap the numbers in boxes x and y
6. If number in box y < number in box z, go to step 10
7. Swap the numbers in boxes y and z
8. If number in box x < number in box y, go to step 10
9. Swap the numbers in boxes x and y
10. Halt (the numbers have been ordered)
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
25
Note: There are many more ways to solve such sorting problems, some of which
will be discussed in later topics.

Activity
Check that Algorithm 2.1 works for any three numbers given.

You may have noticed that Algorithm 2.1 does not actually explain how the
swapping of the values takes place. It assumes that the person or machine that
is implementing the algorithm knows how to swap the contents of the boxes (or
variables, which is the term used in computer programming). If the algorithm is
going to be executed on a computer then the programmer must explain exactly
how to do the swapping.

In order to demonstrate how this is done suppose that you are holding a coin in
each hand and you want to swap the coins over but can only hold one coin in a
hand at a time. The only way you could do this swapping would be to do
something like:

1. Put the coin in your left hand down on the table

2. Move the coin in your right hand to your left hand
3. Using your right hand pick up the coin that you put down

An important concept which is demonstrated here is the use of a temporary

storage space. In the coin example, we used a table as the temporary storage
space. In algorithms we need to use another storage box. Swapping the contents
of two boxes is then done as follows:

1. Put the contents of box x into box t

2. Put the contents of box y into box x
3. Put the contents of box t into box y

We could also write out this section of the algorithm in a more precise way by
making using of mathematical notation to express copying the contents of one
box to another box as shown below:
t=x
x=y
y=t

This allows us to rewrite Algorithm 2.1 more precisely as Algorithm 2.2.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
26
 Algorithm 2.2: More precise algorithm to sort three numbers

1. Place first number in box x

2. Place second number in box y
3. Place third number in box z
4. If number in box x < number in box y, go to step 6
5. t=x
x=y
y=t
6. If number in box y < number in box z, go to step 10
7. t=y
y=z
z=t
8. If number in box x < number in box y, go to step 10
9. t=x
x=y
y=t
10. Halt (the numbers have been ordered)

This algorithm can also be represented as a flowchart as shown in Figure 2.3.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
27
 Start

First number in x
Second number in y
Third number in z

t = x
No
x = y x < y?
y = t
Yes

No t = y
y < z? y = z
Yes z = t

Yes t = x
Halt x < y? x = y
No
y = t

Figure 2.3: Flowchart for sorting three numbers

We could also write out the algorithm as a list of instructions in a more natural
way as shown in the listing for Algorithm 2.3 below.

Note that in Algorithm 2.3 we have not used statement numbers, but have rather
applied indentation to show which statements are grouped together at the same
level. Indentation is often used when deriving algorithms and writing programs
as it makes the logic of the algorithm easier to follow.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
28
 Algorithm 2.3: Algorithm to sort three numbers written using indentation

Enter a value into box x

Enter a value into box y
Enter a value into box z
If the value of x is greater than the value of y then
Store the value of y in a box called temp
Store the value of x in box y
Place the value of temp in box x
If the value of y is greater than the value of z then
Store the value of z in a box called temp
Store the value of y in box z
Place the value of temp in box y
If the value of x is greater than the value of y then
Store the value of y in a box called temp
Store the value of x in box y
Place the value of temp in box x
Display the value in box x
Display the value in box y
Display the value in box z

Activity
Show that the specification of the sorting algorithm given as Algorithm 2.3 works
in the same way as the previous two algorithms for sorting any three numbers.

In this section we have discussed two representations of the algorithm written in

pseudocode (Algorithm 2.3) and a flowchart representation (Figure 2.3). The
term pseudocode comes from the fact that the representation is very close to the
way the instructions would be written in a high-level programming language like
those commonly used today (e.g., Java, Python, C++, and C#). In the next topic
we will look more closely at the constructs that are used in developing algorithms
and writing them in pseudocode. We will also be looking at how algorithms in
pseudocode are translated into Python programs.

A representation of the algorithm in which the pseudocode matches a

programming language even more closely is given as Algorithm 2.4.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
29
 Algorithm 2.4: Algorithm to sort three numbers written in programming-style pseudocode

Enter a value into box x

Enter a value into box y
Enter a value into box z
If x > y then
temp = y
y=x
x = temp
If y > z then
temp = z
z=y
y = temp
If x > y then
temp = y
y=x
x = temp

2.3.4 Some thoughts on the sorting algorithm

Let us now reconsider the algorithm which we derived above to sort the three
numbers. We saw that certain groups of numbers meant that we do not have to
attempt to reorder the first pair of numbers, so we can now ask the question: Do
the numbers that are used and the order in which they are placed in boxes have
any effect on the number of comparisons made and the number of times values
are swapped?

If the numbers 1, 13 and -4 are placed in boxes from left to right in that order,
then three comparisons must be made and numbers are swapped twice. First the
pair 13 and -4 and then the pair 1 and -4 to give the sorted list -4, 1, 13.

Activity
Make sure you understand how the results given above were obtained by
performing the same calculations on different orderings of the input numbers.

1. How many comparisons and swaps would occur if the numbers are placed in
boxes from left to right in the order 13, 1, -4?
2. How many comparisons and swaps would occur if the numbers are placed in
boxes from left to right in the order -4, 1, 13?

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
30
 Answers to Activity
1. Sorting 13, 1, -4 requires 3 comparisons and 3 swaps

2. Sorting -4, 1, 13 requires 2 comparisons and zero swaps

Note that the first case in the activity above is when the numbers are in the
reverse order and the second case is when they are already sorted. Thus the
least work is done when the numbers are already in order. In algorithm analysis,
this is called the best case for this algorithm. The worst case is when the numbers
are in reverse order.

Note also that the best and worst cases are not dependent on the actual numbers
used, but simply on the order that they are placed in the boxes from left to right.

We will see in a later module that the best and worst cases for sorting algorithms
are very dependent on the initial ordering of the numbers to be sorted. In this
algorithm we are only considering the sorting of three numbers. Later on our
analysis of worst and best cases will be shown to be dependent on n, where n is
the number of items to be sorted.

2.4 REVISITING THE DEFINITION OF ALGORITHM

Previously we stated that an algorithm is a list of instructions for performing a

task or solving a problem. We will now consider a more rigorous definition.

According to Knuth (1997), an algorithm has the following properties:

1. It is a list of instructions for performing a specific task.

2. It must terminate — Knuth refers to this as finiteness.
3. All the instructions must be precise and unambiguous — Knuth refers to
this as definiteness.
4. It must be possible to perform all of the instructions — Knuth refers to
this as effectiveness, but this property can also be defined as feasibility.
5. It must have zero or more inputs (i.e., boxes containing data) that are
given initially before the algorithm begins, and one or more outputs that
have a specific relation to the inputs.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
31
We have already seen examples of the first property, e.g., algorithms for filling
a bath and sorting three numbers.

Now consider the second property by examining the following list of instructions:
1. Place the number 1 into the box labelled x
2. Add 2 to the contents of box x
3. If a = 10 then HALT
4. Go to step 2

Box x takes the sequence of values given below:

1 3 5 7 8 11 13
It is never equal to 10 so the HALT instruction is never performed. This list of
instructions never terminates and so it would not normally be considered an
algorithm.

Now let us consider the third property, by looking at the following two example
instructions:
Divide x by y
Fill the bath with warm water

These are both imprecise instructions. What happens if y=0? What exactly is the
temperature of warm water?

Next, we illustrate the fourth property, by considering the instruction given

below:
If there is a fast general algorithm for playing an optimal game of chess,
go to step 5.

This is an instruction that cannot be executed. We do not know if such an

algorithm exists. It is also imprecise as we do not state what we mean by “fast”.

Finally, we consider the last property that refers to inputs and outputs. In the
sorting algorithm we discussed, the three unsorted numbers contained in the
boxes are considered the inputs, and the rearranged numbers, constituting a
sorted list of numbers, are considered the output.

2.5 BASIC CONSTRUCTS FOR CREATING ALGORITHMS

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
32
Whilst we have already created some basic algorithms, we need to formalise the
basic constructs available for specifying algorithms. These are sequence,
selections and repetition.

2.5.1 Sequence

An algorithm is a sequence of steps if it consists of simple steps that are to be

executed one after the other.

An algorithm to calculate the area of a rectangle can be written as:

1. Put the length of the rectangle into box L
2. Put the width of the rectangle into box W
3. Multiply the contents of box L by the contents of box W
4. Put the result into box A
5. Output the contents of box A

Sequence thus means that:

1. Steps are executed one at a time.
2. Each step is executed exactly once.
3. The order in which the steps are executed is the same as that in which they
are written down.
4. Termination of the last step implies termination of the algorithm.

Most algorithms can be written down as a list of instructions that are to be

followed from the first instruction to the last, but this is a very inflexible way of
describing algorithms. In the next two subsections, we will look at some
constructs that allow us to write more realistic and useful algorithms.

2.5.2 Selection

In some algorithms we might only want to execute an instruction in certain

circumstances or if a particular condition is satisfied and omit the step otherwise.
The selection construct gives us a way to do this.

Selection has the form:

IF Condition
THEN Step

As an example of how this construct is used, let us consider the case where two
numbers are entered into boxes a and b and we want to have the smaller number

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
33
in a and the larger number in b. This could be accomplished by executing the
following pseudocode:
IF a > b
THEN swap a and b

or more precisely
IF a > b
THEN
t = a
a = b
b = t

An extension of this selection construct is a form that determines which of two

alternative steps is to be executed.
IF Condition
THEN step 1
ELSE step 2

As an example of how this construct is used, let us consider the case where two
numbers are entered into the boxes x and y and we would like to copy the value
of the smallest of these two numbers into a box called smallest. This can be done
as follows:

IF x < y
THEN smallest = x
ELSE smallest = y

This form of the construct can also be used for determining which group of
statements are to be executed if the condition holds and which are to be executed
if it does not. As an example of this, suppose we want to find the larger and
smaller of two numbers. We could do so in this way:

IF x < y
THEN smaller = x
larger = y
ELSE smaller = y
larger = x

In this case, if x is smaller than y then smaller gets the value of x and larger
gets the value of y. If x is not less than y (i.e., greater than or equal to) then
smaller gets the value of y and larger gets the value of x.

We can also nest selection. For example if we wanted to find the largest of 3
numbers that have been entered into boxes x, y and z, our algorithm could be
written as:
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
34
 IF x > y
THEN IF x > z
THEN largest = x
ELSE largest = z
ELSE IF y > z
THEN largest = y
ELSE largest = z

Selection allows different paths to be followed through an algorithm depending

on the circumstances.

2.5.3 Repetition

Often when we are deriving algorithms we want to be able to repeat an action.

Consider the portion of the algorithm for filling the bath (as given in Section
2.3.1) to a depth of at least 6 cm.
4. Turn on both taps
5. Wait one minute
6. Check the depth of water in the bath. If this is less than 6 cm go
to step 5
7. Turn off both taps

Here we repeat steps 5 and 6 until the depth of water in the bath is greater than
or equal to 6 cm. We could rewrite this portion of the algorithm as:

Turn on both taps

WHILE depth < 6
Wait a minute
Check the depth of the water
END WHILE
Turn off both taps

The general form for repetition is thus:

WHILE condition is true
portion of algorithm to be repeated
END WHILE

Repetition is also often called looping and the instructions between the WHILE
and the END WHILE are called the loop body. The condition occurring at the start
determines whether the loop body should be executed or not.

There is an alternative form for repetition that is found in some programming

languages where the condition appears at the end (rather than at the beginning)
and determines whether the loop should be terminated.
REPEAT
portion of algorithm to be repeated
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
35
 UNTIL condition

For example:
Turn on both taps
REPEAT
Wait a minute
Check the depth of the water
UNTIL depth >= 6
Turn off both taps

Note: In a WHILE loop the condition is tested before the body of the loop is
executed. In a REPEAT loop the condition is tested after the body of the loop has
been executed. This means that in a REPEAT loop the body is always executed
at least once, whereas in a WHILE loop the body may not be executed at all.

Let us look at an example of where we would want to use a WHILE construct

rather than a REPEAT—UNTIL construct. Suppose we are asked to derive an
algorithm that reduces the value of a number (entered by a user) by 1 until it
has a value less than or equal to zero.

An algorithm to do this could be written as:

Enter x
REPEAT
x = x - 1
UNTIL x <= 0

This algorithm seems as though it will do what is required but what happens if
the number entered by the user is already less than 0?

In this case the body of the loop will be executed before the test and x will be
decremented more than is necessary. Obviously in this simple example this is
not a serious flaw but in other cases it could be much more important. We can
avoid this problem by developing the algorithm using a WHILE loop construct, as
shown below, rather than a REPEAT construct:

Enter x
WHILE x > 0
x = x – 1
END WHILE

Activity
Check that the WHILE loop algorithm actually performs the task it should
without any extra work. You should do this by using various numbers as input
values for x.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
36
 Activity
You may also have noticed that the condition tested in each of the two algorithms
differs. Why do you think this is the case?

In addition to the two constructs given above there is another useful looping
construct to be considered. This construct works well if we want to repeat an
operation (either a single statement or a group of statements) a known number
of times. Known as a for loop, this construct can take a variety of forms
depending on the programming language used.

FOR N times DO
body of loop
OR
FOR each integer i from start to end DO
body of loop
OR
FOR each integer i in some sequence DO
body of loop

An example of the use of this construct is an algorithm to calculate N! where N!

(or N factorial) is defined as being the product of all the numbers from 1 to N,
that is,
N! = 1 x 2 x 3 x 4 ... x (N-1) x N

Our algorithm would then be as shown below:

obtain value of N
set product to 1
FOR each integer i from 1 to N DO
multiply product by value of i and store result in product
write out product value

This could also be written using less verbose pseudocode as shown in Algorithm
2.5.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
37
 Algorithm 2.5: Factorial algorithm using pseudocode
enter N
product = 1
FOR each integer i from 1 to N DO
product = product * i
output product

It is important to notice that Algorithm 2.5 will work for all values of N, including
the case where N = 0 as 0! is defined as being equal to 1. Let us see why this
holds. The first line of the algorithm gets the value of N (in this case 0) and the
second line sets the value contained in the variable product to be 1. When the
for loop begins the instruction can be read as
FOR i from 1 to 0 DO

But the starting value of i is already greater than zero, which means (in our
interpretation of the construct) that the body of the loop will never be executed,
so the variable product will still contain the initial value 1. This value will be
output and is in fact the correct answer for 0!.

2.5.4 Why are these constructs important?

The constructs that we have considered above are important for two reasons.
First, any algorithm can be constructed by using the SEQUENCE, SELECTION and
REPETITION constructs as described in the previous three subsections. For
example we could rewrite our algorithm for filling the bath (with an extension to
ensure we have the correct temperature of the water) as:

Go to the bathroom
Go to the bath
Push the bathplug into the plughole
Turn on both taps
WHILE depth < 6
Wait one minute
Check the water depth
END WHILE
Turn off both taps
Check the temperature
WHILE temp < 30 or temp > 40
IF temp < 30
THEN Turn on hot tap
Wait one minute
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
38
 Turn off hot tap
ELSE Turn on cold tap
Wait one minute
Turn of cold tap
Check the temperature
END WHILE
HALT (the bath is now filled with water at the right temperature)

This is easier to understand than the original algorithm. Note that the numbering
of the instructions is no longer necessary as we have used indentation to show
instructions that belong together, i.e., instructions that form an instruction block.

The second reason that we study these constructs is that most of the well- known
imperative programming languages have constructs that are similar to these as
discussed above. This means that it is relatively easy to translate an algorithm
into a program. We will look at how Python implements these constructs in the
next topic.

2.6 BASIC DATA STRUCTURES

2.6.1 Variable and constant data

In the previous sections, we made use of the term boxes to hold the data that
was manipulated in our algorithms. For example in the sorting algorithm, we
used three boxes to store the three numbers being sorted.

In a computer programming context, the word variable is used instead of box. A

variable is defined simply as storage for a value that can be changed by the
instructions in an algorithm. Thus, in an algorithm, variables would be used to
“hold” any data that can change during the execution of the algorithm. Since
each variable has a name, using variables makes manipulating data in an
algorithm easier, since we can refer by name to the variable that holds the data.

Another form of data commonly used in algorithms is constant or fixed values.

Such values are referred to as constants, as these may not be changed during
the execution of the algorithm.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
39
2.6.2 Simple data types

Both variables and constants are defined to be of a certain data type, which
prescribes the form that values may take. Some examples of basic data types
are: integer, floating point, character (representing alpha numeric characters like
the letter of the alphabet or digits), string (representing a sequence of
characters), and Boolean (representing only true or false values) types.

Examples of each of these types are given below:

Integer: -4 600 99 -1234 0 156
Floating point: 5.66 -99.12 99.0 15.134 0.0 -2.0
Character: 'a' '0' '+' ';' 'A' '8'
String: "A string of characters" "Another string with digits 123"
Boolean: true false

Thus, the type of data we used as input in our sorting algorithm is integer
numbers, and consequently the variables used to hold this data had the type
integer.

All variables (and constants too, for that matter) must have a name, a value and
a type. For example, if we have a variable called temp, it might have as its value
the number 10, and therefore its type is integer.

Alternatively, if we have a variable called name, that has the value "Donald
Duck", then this variable would have string as its type.

2.6.3 Assignment

During the discussion on algorithms, we made use of the mathematical operator

equals (=) to represent copying the value of one box (i.e., variable) to another
box (or variable). In the context of computation, we refer to this process as
assignment. This is the usual way of giving a variable a value. We will see later
that we can also store values in variables directly through input (or read)
instructions.

Given below are examples of some assignment instructions:

num = 10.5
num2 = num
myname = "Donald Duck"
achar = 'g'

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
40
In the first assignment, we are giving the variable named num the value 10.5.
This variable has a type of floating point.

The second assignment gives the variable named num2 the same value as is
currently stored in the variable num. This variable also has the type floating point.

In the third assignment, we are giving the variable named myname the value of
the string "Donald Duck". Thus, this variable has a type string as it stores
strings.

Finally, the last assignment gives the variable named achar, the character value
'g'. This variable has a character type as it holds character values.

2.6.4 Compound data types

Often, we need to express a number of data elements of the same type, in which
case a variable of a simple type (like integer or floating point) will not suffice. In
this case we can resort to using one of the compound data types like lists, arrays
or dictionaries.

More information on these compound types will be given when dealing with actual
code for the Python programming language in later topics.

Summary

This topic first defined the development process of a computer solution to a given
problem as a series of steps: define the problem, outline a solution, develop the
outline into an algorithm, test the algorithm, convert the algorithm into a
program written in a specific programming language, and execute the program
on a computer. In this topic we discussed the stages up to and including the
development of the algorithm. (Note that the remaining steps are discussed in
the next topic.)

To develop useful algorithms we introduced the three building block constructs

of sequence, selection and repetition. For repetition, we showed three different
forms that can be used to repeat a series of instructions, namely, the while loop,
repeat loop and for loop.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
41
We provided a more rigorous definition of an algorithm in terms of the following
five properties: 1) it is a list of instructions for performing a specific task; 2) It
must terminate; 3) all the instructions must be precise and unambiguous; 4) it
must be possible to perform all the instructions; and 5) there must be zero or
more inputs to the algorithm and one or more outputs after executing the
algorithm.

Finally, we introduced the concept of variables as storage for data used in

algorithms, and described the three features of a variable, namely, a name, a
value and a type.

Self-Assessment Questions

1. What properties must algorithms satisfy?

2. Write down a list of instructions that will enable someone to get from your
home to the nearest supermarket. Ask a friend to test the instructions to
ensure that they are clear enough and unambiguous.

3. Write an algorithm to search for a number that the user inputs in a list of
numbers that are unsorted.

4. Explain what changes, if any, you might make to the algorithm created as a
solution to (3) above, if the list of numbers that you were searching through
were sorted in ascending order.

5. Rewrite Algorithm 2.5 using a WHILE loop instead of a FOR loop to calculate
N!.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
42
6. What would be the output when executing the following instructions:

a) FOR each integer j from 1 to 12 DO

output j

b) j=5
WHILE j >= 1
output j
j=j–1
END WHILE

c) j=0
WHILE j < 8
output j
j=j+1
END WHILE

d) j=0
WHILE j < 8
j=j+1
output j
END WHILE

e) j=0
WHILE j > 8
j=j+1
output j
END WHILE

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
43
 Topic 3
Python programming language

3.1 INTRODUCTION

This topic relates to the following module outcomes:

3. Show mastery of basic programming constructs in the context of the

Python programming language by converting hand-crafted algorithms
into Python code.
4. Design efficient Python solutions to simple mathematical and logic
problems.
5. Execute, debug and create simple test procedures for Python programs.

On completion of this topic you will understand how a computer program is

related to the algorithms we derived in the previous topic. We also introduce the
Python programming language and show how a given algorithm can be coded
using Python. Finally we show how this code can be executed on a computer that
has the required software installed.

In this topic, you will gain knowledge in the following areas:

1. Creating a computer program

2. Overview of the Python programming language
3. Converting algorithms into Python code
4. Installing the required software and executing a Python program
5. Simple debugging techniques

The following assessment criteria for sub-topics relate to module outcomes 3, 4

and 5:
 Algorithms: Discuss what properties an algorithm must satisfy and why.
 Flowcharts and pseudocode: Develop algorithms for simple everyday
tasks represented as a flowchart and/or in pseudocode.

 Debugging: Explain the terms and apply basic techniques to debug

simple Python programs.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
44
 Python programming: Explain the basic Python constructs and show how
they are used in programs to solve simple mathematical and logic
problems.

Prescribed reading
Read Chapter 1, “The way of the program” in the prescribed text by Wentworth
et al. (2012), How to Think Like a Computer Scientist, 3rd edition, Runestone
Academy. Available at:
[Link]

3.2 PROGRAM = ALGORITHM + DATA STRUCTURE

In 1967, Nicklaus Wirth, who is considered one of the pioneers of programming

languages, stated that
“Algorithms + Data Structures = Programs” (Wirth, 1967)

What he meant by this, is that if you can create an algorithm to solve a problem
and you can represent the data used in the algorithm using one or more data
structures provided by your programming language of choice, you can ultimately
code the algorithm as a computer program that can be executed on a computer.

Thus, we can define a computer program as a sequence of instructions that can

be executed on a computer; in other words, an algorithm that has been rewritten
using the language constructs provided by a particular programming language.

Having discussed both the creation of algorithms and simple data structures in
the previous topic, we are now in a position to see how we can go about creating
computer programs.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
45
3.3 INTRODUCTION TO PYTHON

3.3.1 Overview of the Python programming language

A programming language provides the means for programmers to write computer

code that can be executed on a computer. There are many programming
languages available, many of which provide similar functionality but using
different syntax for the constructs provided. Syntax refers to the structure of
these constructs to form statements. This is similar to what we have in spoken
languages, where syntax refers to the arrangement of words, phrases and other
symbols like punctuation to create well-formed sentences.

Python was developed by Guido van Rossum in the late 1980s to early 1990s. It
is used extensively for online games, web services, applications, scientific
programming, embedded systems and more. However, given that it was
developed with the aim of being easy to learn, read and maintain code, it is also
ideal as a beginner’s language.

Python is a high-level interpreted, interactive and object-oriented language. In

order for computer code written by the programmer to be understandable to the
computer, it must undergo a translation process, either compilation or
interpretation. High-level languages like C/C++, Java and C# use compilers to
translate the programmer code into a file containing lower level code (e.g.,
machine code) that a computer can understand. Python on the other hand, uses
an interpreter to interpret the code line-by-line, which is what makes running
Python programs interactive. Object-oriented programming is a style of
programming that makes use of objects, but this is not covered in this
introductory programming course.

In the following subsections we introduce the syntax for some basic constructs
provided in the Python language. Note that in this course we will be using Python
3 (and not Python 2) for all our Python code examples.

3.3.2 Python code format

Similar to how we set out the algorithms in the latter part of Topic 2 using
indentation to depict instructions that belong together, Python too relies on line
indentation to indicate blocks of code, function definitions and flow control. The
number of spaces used for the indentation is flexible, but all statements in a
block of code must follow the same indentation pattern.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
46
Large files of code benefit from the use of comments, which are lines of text that
are intended for human readers only, and help to give some explanation of what
the program code is trying to achieve. To add a comment into Python code we
use a # symbol, and then any text that appears after this token, up to the end
of the current line, is ignored by the interpreter.

Commenting your code is a good habit to foster, as it assists you and anyone
else reading the code to understand what is trying to be achieved.

3.3.3 Values and data types

Prescribed reading
Read Section 2.1, “Values and data types” in the prescribed text by Wentworth
et al. (2012), How to Think Like a Computer Scientist, 3rd edition, Runestone
Academy. Available at:
[Link]

Python supports the basic variable types as discussed previously, namely int
(integer), float (floating-point), and str (string). It also supports many others
as we will see later.

Examples of values for each of these are given below:

int 6 0 -33 -1567
float 4.3 -9.8 100.555 0.555
str "Hello!" 'Another string' """and even this"""

3.3.4 Variables and assignment

Prescribed reading
Read Sections 2.2 to 2.4 in the prescribed text by Wentworth et al. (2012), How
to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

Python supports the use of variables that do not have to be declared explicitly –
instead the type of the variable is implied by its use. Variables are normally given
a value by means of an assignment:
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
47
 message = "Please ring me"
myage = 45
pi = 3.14159

In these examples, message is assumed to be a string, and any future

assignments to message will need to involve string values, while myage is
assumed to be an integer. Finally, pi is considered a float due to the value that
is being assigned to it.

Variable names can be arbitrarily long, and can include both letters and digits,
but must begin with either a letter or an underscore characters ( _ ). There are
some combinations of letters (i.e., those that are keywords or reserved words in
the Python language) that you may not use as variable names. Python has over
30 keywords, examples of which are:
for if while True False else break with

3.3.5 Evaluating expressions

Prescribed reading
Read Sections 2.5 to the end of Chapter 2 in the prescribed text by Wentworth
et al. (2012), How to Think Like a Computer Scientist, 3rd edition, Runestone
Academy. Available at:
[Link]

The use of expressions in programming is similar to their use in a mathematical

context, in that expressions can consist of values, variables, operators and
function calls.

The Python interpreter evaluates any expressions that it comes across, producing
a value in the process. (Note that a variable or a value by itself is a simple
expression.) This value can either be displayed or used in some other way, such
as the value to be assigned to a variable as shown below:
pi = 22.0 / 7.0

Here, pi is set to the value obtained by dividing 22.0 by 7.0.

When multiple operators are used in an expression, the precedence rules follow
those used in mathematics (i.e., PEDMAS which stands for parentheses,
exponents, division, multiply, addition and subtraction), except that the
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
48
operators for multiply, divide and remainder all have equal precedence, while
those for addition and subtraction have equal precedence. Where multiple
operators have the same precedence, they are evaluated from left-to-right.
Note that the operator for calculating the remainder (called the modulus
operator) makes use of the % symbol, while integer division can be performed
by the // operator. The difference between the / and // operators is highlighted
below:
25 / 2 gives 12.5
whereas
25 // 2 gives 12

When creating expressions, we must be mindful of the types of variables or

values being used. For example, we cannot do addition between an integer and
a string for example. Valid and invalid code is shown below:

message = "Please ring me" # this is valid code

message2 = message + 1 # this is not valid code

Python does support type converters int(), float() and str(), that allow,
respectively, float types to be converted into integers, integer types or
syntactically correct strings (e.g., "123.44") to be converted into float types,
and any argument to be converted into a string. Note that the modulus operator
works only with integers and integer expressions.

When applied to string types only, the + operator denotes concatenation (i.e.,
joining of two strings), while the * operator (which normally represents
multiplication) denotes repetition of the string.
For example:
"fun" * 3 has the value 'funfunfun'
"fun" + "ny" has the value 'funny'

3.3.6 Input and Output

Included in the standard library provided with the Python system are functions
to perform input and output, namely the input() and print() functions. These
functions always return string values. If you want to read in an integer or float
number, then you need to use the type cast explained previously to convert the
string read in.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
49
Some examples are given below:

# read and write a string

name = input("Please type in your name: ")
print(name) # this prints name as a string

# reading numbers for use in calculations needs type casting

num = int(input("Please type in an integer number: "))

# now calculate num // 2 and print as an integer

print(num // 2)

Activity
Rewrite each of the following pairs of lines of Python code as a single line of code.
Task 1
q = 7 // 3
print(q)

Task 2
response = input("What is your radius? ")
r = float(response)

Task 3
area = 3.14159 * r ** 2
print ("Area is ", area)

Task 4
Rewrite the four lines of code given in Tasks 2 and 3 as a single line of code.

3.4 YOUR FIRST PYTHON PROGRAM

In Topic 2, we showed how we could develop an algorithm for a given problem.

Let us repeat the process here and then extend it to develop actual Python code
that can be executed to solve the problem.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
50
The problem we will be looking to solve is the following:
Derive an algorithm that when given two integer numbers, divides the first
number by the second, and prints out the integer division result (i.e., quotient)
and the remainder.

In order to solve this problem, we start by first understanding what is required,

creating an algorithm, and finally converting the algorithm into Python code that
can be executed.

3.4.1 Defining the problem

In any problem for which we are going to try and develop an algorithm there are
likely to be three components that we will have to address:

1. Input: What values (if any) must be given as input to the program?
2. Output: What values must the program produce or what should the result
of running the program be?
3. Processing: What are the actions the program must perform?

These three components can normally be identified quite easily from a careful
reading of the problem statement.

Using the given problem statement, we can see that the phrase “given two
integer numbers” hints at the fact that the input must be "two integer numbers".
Similarly it is also fairly easy to see that the output of the program should be the
quotient and remainder of dividing the two numbers.

The question that we have to answer now is "What processing does our program
have to do?" If we read the problem description carefully we will see words in it
that express actions, such as "divide" and "print" as well as words that hint at
actions, such as "get numbers" and "calculate remainder". These words provide
clues as to what processing the program must do, for example:

Get two numbers

Divide first number by second
Calculate remainder of first number divided by second
Print results

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
51
3.4.2 Designing a solution algorithm

The algorithm outline produced in the previous section can be expanded to give
us an algorithm to solve the given problem.

The first line of the outline is fairly easy and can be translated/expanded to
enter x
enter y
Similarly for the next two lines, which make use of mathematical operators to do
the calculations:
resA = x / y
resB = x modulo y
Note that we have expanded these two lines to include an assignment as well as
the basic calculations, because if we do not explicitly store the results of a
calculation, we cannot use them later in the algorithm.

This gives a final version of the algorithm as shown below:

Algorithm 3.1: Division/remainder algorithm in pseudocode

enter x
enter y
resA = x / y
resB = x modulo y
output resA
output resB

Before proceeding to the next stage of the development, i.e., the coding, it is
important to manually check that the algorithm created actually works. This is a
process called desk-checking and is done by working through the algorithm by
hand to see that it works.

For example, let us see what happens if the input is given as 20 for x and 6 for
y. Then resA = 20/6 = 3, and resB = 20 modulo 6 = 2.
So the results printed will be
3 2

As this is a very simple algorithm the true benefit of running through the
workings of the algorithm is not clearly seen. However, becoming proficient in
desk-checking your algorithms will stand you in good stead once the problems
being solved become more complex.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
52
3.4.3 Coding the algorithm

Using Algorithm 3.1 and the introduction to the Python syntax in Section 3.3, we
can now create Python code to solve the problem given. The result is given as
Python Listing 3.1.

Listing 3.1: Python code to calculate division/remainder of two numbers

myinput = input()
x = int(myinput)
myinput = input()
y = int(myinput)
resA = x // y
resB = x % y
print(resA)
print(resB)

The following should be noted about this code:

1. As input() returns a string value, we need to convert this to an integer
for storage in a variable (x and y in this example) that can then be used
with arithmetic operators. Strings cannot be used in arithmetic
calculations.
2. The // operator performs integer division, where any decimal part of the
result is truncated (i.e., cut off).

Although this code does work correctly, we can make the code more human
friendly by adding some extra Python functionality as shown in Listing 3.2.

Look out for the following changes:

1. More descriptive names for the variables.
2. Some comments explaining what certain parts of the code does.
3. A hint to the user that input is needed and what kind of input.
4. Output that makes more sense.

Listing 3.2: More user-friendly Python code to calculate division/remainder of two numbers

myinput = input("Please type in an integer number: ")

num1 = int(myinput)
myinput = input("Please type in an integer number: ")
num2 = int(myinput)
quotient = num1 // num2 # integer division operator used
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
53
rem = num1 % num2 # calculate remainder
print("Quotient is: ", quotient)
print("Remainder is: ", rem)

3.5 EXECUTING A PYTHON PROGRAM

3.5.1 Installing the software

In order to execute any Python code, you first need to install a Python interpreter
on your computer. There are numerous ways of doing this, but we will make use
of the Thonny integrated development environment (IDE) as this has been
specifically designed with beginner Python programmers in mind.

Figure 3.1: Where to find the download link on the Thonny webpage

Activity
Install the software needed to run Python programs on your own computer, by
following the steps given below:

1. In your browser, navigate to the webpage: [Link]

2. Click on the download link given after the text “Download version” – the
current download version is 4.0.1. Figure 3.1 shows where to find the
download link.
3. This should take you to a github page, something like:
[Link]
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
54
4. Towards the bottom of the page there is an “Assets” section with various
downloadable files. Select the appropriate one for your computer. For a 64-
bit Windows operating system (versions 8.1, 10 or 11) download the file
[Link] . If you are using Linux Ubuntu or MacOS as an operating
system, please skip to Step 9.
5. Once downloaded, double click on the file to execute the installation.
6. Follow the prompts, selecting the recommended option (or Next) at all
opportunities. On the “Select Additional Task” screen you should click in the
box to “Create a desktop icon”. Thereafter, click “Install” and after a while,
click “Finish”.
7. To open the Thonny IDE, click on the following icon on your desktop:

8. You are now ready to type in and run your first Python script using the
Thonny IDE.
Only for those using Linux or MacOS operating systems:
9. To install Thonny on Linux Ubuntu, follow the instructions given in the
YouTube video at [Link] .
10. For installing Thonny on MacOS, download the file [Link] and
install as usual on the Mac.

3.5.2 Running your first program

Before we attempt to run our program, it would be useful to understand the

functionality provided by the Thonny IDE that we have installed. The next activity
will assist in showing what functionality is available in the IDE, specifically
focusing on the editor and how to execute a program.

Activity
Read the tutorial on Thonny: the Beginner-Friendly Python Editor. Note that you
should skip the first section (called “Installing Thonny”) as it merely explains how
to install the software on Linux. However, we have already dealt with the
installation of the software on all the operating systems, namely Linux, MacOS
and Windows, in the previous subsection.

This tutorial explains the user interface (i.e., what you see on the screen)
provided by Thonny, the code editor (i.e., where you will be writing your code),

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
55
as well as some more advanced features (like the package manager) that we will
discuss later.

The tutorial also leads you through the various stages of running a program:
creating the file, writing some code, saving the file and then running the code.

Finally, we are ready to execute our first Python program using our own recently
installed software. Open the Thonny IDE and run the program first using script
mode and then using fully interactive mode as explained in the next activity.

Activity
Running a complete Python program (or script):
Now that you are more familiar with the Thonny IDE, type in the code for your
first program as developed in Listing 3.2 and run it using the “Run current script”
option on the menu.

Check that the output given, is what you expected. If not, there is an error (or
bug) in your code and you will need to follow the process given in the next section
to correct the code.

Executing a Python program one line at a time:

Note that you can also execute your Python program one line at a time by typing
one line of the program at a time into the Shell area of the IDE and hitting return
after each line.

Do this using the code in Listing 3.2 and see if the output is the same as when
running the complete script.

3.6 DEBUGGING YOUR PROGRAM

3.6.1 What is debugging?

It is very seldom that we write code that is completely free from errors.
Programming errors are referred to as bugs (a name that stems from a real bug
that caused errors in one of the first vacuum-tube computers in 1947), while the
process of finding these errors is called debugging.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
56
 Activity
Read about the world’s first computer bug:
[Link]
app-testing

There are different types of errors that can occur in your program code:

1. Syntax errors relate to incorrect structure of your code. At the first such
error, the Python execution system will stop, after giving you an error
message.

2. Runtime errors (also called exceptions) appear when you are running your
program. Whilst rare, these errors will stop the execution of your program
and thus need to be fixed. Attempting to divide by zero, for example, will
cause a runtime error.

3. Semantic errors relate to the meaning (or logic) in your code. Such errors
will not cause the execution system to stop, but it is likely that you will not
get the correct answer if there are semantic errors in your code. An example
of such an error, is using a < operator instead of a <= operator. In this case
your program might work for some input values, but will not produce the
correct answer for others.

3.6.2 How to debug your code

We have already mentioned the process of desk-checking (see Section 3.4.2) as

a crucial step in checking that the basic algorithm works. This process can also
be carried out on the actual program code, i.e., working through each line of the
code by hand to ensure that each statement does what it is should do.

A second method of debugging can be done with the aid of carefully placed print
statements. For example, by inserting print() commands at various points in
the code, we can print out the values of certain variables to ensure that the
values these variables take are as expected. Such print() commands can also
be used to indicate whether a certain statement in the code is executed or not.
This can help check that the conditions used in selection (if-else) statements are
correct.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
57
Finally, many IDEs provide an easier way of debugging using an automated
debugger. Thonny provides a simple debugger that allows you to step through
your code line-by-line (when executing your code in script mode). This allows
you to see what each line of the program achieves.

To run your program in this debug mode, simply click on the “bug” icon next to
the normal run button at the top of the Thonny window as shown below:

You will see that as each line is executed, it is highlighted in the top window of
the Thonny IDE.

Activity
Type the following code into the program window in Thonny.
a=1+2
a=a*2
print(a)

Now start execution of this program in debug mode by clicking on the “bug” icon.
You will need to click on the “step into” button (the yellow button in the middle,
showing an arrow pointing down between two lines) to move from one step to
the next in the execution.

You may be surprised by the number of steps needed to execute this small
program. This is because at some steps the debugger pauses to show you what
will happen next. Other steps are to perform each of the arithmetic operations,
and assignment and print statements.

The Thonny debugger also has other features like setting breakpoints (to allow
you to skip over some of the code that does not need debugging) and showing
the values of variables. These will be more useful when your Python programs
become more complex.

Suggested reading
A very comprehensive tutorial on using the Thonny debugger is available at:
[Link]

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
58
Some of the features described in the beginning of this tutorial would be useful
at this stage, but you will only be able to appreciate the full extent of the
debugger towards the end of this module once you have been introduced to and
have used more Python functionality.

Summary

This topic introduced the Python programming language, together with a few
basic constructs and the software needed to execute Python code.

Python 3 is the version of the programming language this module makes use of.
Instructions were provided for installing the Thonny IDE, which will be used for
writing and executing Python code. This IDE also provides a basic debugger that
can be used to step through program code one or more lines at a time to facilitate
finding errors.

Basic Python constructs for assignment, input and output, and evaluating
expressions was covered. In addition, basic types for variables were introduced.

Finally, the development of a solution to an example problem, from the initial

understanding of the problem to coding an executable solution in Python was
also discussed. This is the process that should be used for developing computer
programs to solve given problems going forward.

Self-Assessment Questions

For all the exercises, first manually desk-check the code to work out what
problem the code solves. Thereafter, type the code into the Thonny IDE and
execute it.

1. What problem does this code solve? What is the output when you execute the
code? What word should replace the ?? in the print statement to make the
output more meaningful to the programmer?

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
59
 a = 20
b = 30
if a > b :
x = a
print("?? value is a:", x)
else :
x = b
print("?? value is b:", x)

2. What problem does this code solve? What is the output when you execute the
code? What word should replace the ?? in the print statement to make the
output more meaningful to the programmer?

a = 20
b = 30
c = 10
t = a + b + c
print("?? of three numbers is ", t)

3. What does this code do? How does input() work? What is the output when
you execute the code?

name = input()
print("My name is", name)

4. What does this code do? What is the output when you execute the code?

a = 8
b = 5
c = 20
rem = a % b
div = c // a
div2 = c / a
print("Rem is ", rem)
print("IntDiv is ", div)
print("FloatDiv is", div2)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
60
5. This code does not work correctly. It should output:
The total = 40
Find the errors and fix these to allow the code to execute correctly.

a = 10
b = 5
c = 45
calc = b c a
print(The total = calc)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
61
 Topic 4
Basic programming constructs

4.1 INTRODUCTION

This topic relates to the following module outcomes:

3. Show mastery of basic programming constructs in the context of the

Python programming language by converting hand-crafted algorithms
into Python code.
4. Design efficient Python solutions to simple mathematical and logic
problems.
5. Execute, debug and create simple test procedures for Python programs.

On completion of this topic on basic programming constructs, you will be able to

write simple Python programs with conditions and iterations and making use of
predefined Python modules. Correct usage of alternative looping structures is
discussed. User-defined functions are introduced and categorized as either
returning a value (i.e., a fruitful function) or not. Usage of both categories of
functions is explained with the aid of several example programs. The many
practical exercises assist in understanding the new programming concepts.

In this topic, you will gain and apply knowledge in the following areas:

1. Using predefined Python modules and for loops

2. User-defined functions
3. Conditional statements
4. Functions that return values
5. More looping constructs

The following assessment criteria for sub-topics relate to module outcomes 3, 4

and 5:
 Algorithms: Convert simple algorithms into Python code that can be
executed.
 Debugging: Use the Thonny debugger to find and correct errors in Python
code.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
62
 Python programming: Explain the benefits of using pre-defined modules
in your code.
 Python programming: Explain the differences in use of the two Python
looping constructs (while and for loops) and show how these are used in
programs to solve simple mathematical and logic problems.
 Python programming: Understand the need for functions and how the
two different types of functions (i.e., those that return values and those
that do not) can be used effectively.

4.2 USING PREDEFINED PYTHON MODULES AND FOR LOOPS

Prescribed reading
Read Chapter 3, “Hello, Little Turtles” in the prescribed text by Wentworth et al.
(2012), How to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

Built into the Python programming language are several predefined modules that
provide powerful programming functionality with minimal coding. In this section
we use the turtle module with a for loop to facilitate the drawing of shapes.

4.2.1 Drawing shapes using turtles

Activity
Follow the instructions in Sections 3.1 and 3.2 of the Prescribed Reading for this
section, to draw some simple shapes using two turtle instances.

Ensure that you understand what each line of code given in these sections does.

The turtle module that you used in the activity provides a new Turtle type,
from which we can instantiate as many instances of turtle objects as needed.
Turtle objects have various attributes that can be set, e.g., the color attribute
of the pen they use to draw the shapes. Each instance of a turtle can have its
own individual values for any of the attributes.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
63
Turtle objects also have some predefined methods, such as forward() and
left(), which we can invoke (or call) in our code. These methods provide
instructions that the turtle object knows how to respond to.

4.2.2 Repetition using a for loop

As discussed in Section 2.5.3, repetition (also called iteration) is one of the basic
building blocks of programming. The for loop (or for statement) is one of the
constructs in Python that enables us to repeat a series of actions a number of
times.

The for loop is an example of what is referred to as a compound statement (or

construct), which has a header line (introducing the kind of statement, followed
by a body which contains the actions the statement performs. The syntax for the
for loop is given as:
for loopvariable in list :
statement1
statement2
. . .
statementn

Note that in the above construct all text in bold represents keywords or symbols
that must be present when constructing a for loop, while the text in italics
courier font represents code that the programmer provides to achieve the logic
required to solve the problem. Note that any number of statements can be
present in the body of the for loop, but all of these statements must be valid
Python statements with the same degree of indentation. We often refer to a
number of statements used in constructs like the for loop, as a statement block
or just a block.

An example loop can be written as:

for f in ["Joe","Zoe","Brad","Angelina","Zuki"]:
invite = "Hi " + f + ". Please come to my party!"
print(invite)

This code will produce the following output:

Hi Joe. Please come to my party!

Hi Zoe. Please come to my party!
Hi Brad. Please come to my party!
Hi Angelina. Please come to my party!
Hi Zuki. Please come to my party!

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
64
Another example of a for loop can be written as:

for val in [10,20,30,40,50]:

num = "The next number is: " + str(val)
print(num)

which gives the following output:

The next number is: 10

The next number is: 20
The next number is: 30
The next number is: 40
The next number is: 50

These examples clearly show how the for loop works: The number of elements
in the list determines how many times the loop will be executed and at each
iteration of the loop the loopvariable is assigned the next value given in the
list.

4.2.3 Using for loops with our turtles to simplify our code

We can simplify the code previously used to draw a square by thinking logically
about the instructions. Essentially a square is 4 straight lines with a 90 degree
angle between each. So using the for loop we can repeat the process of drawing
a line and turning 90 degrees, consistently either to the left or right.

Activity
Follow the instructions in Sections 3.5 and 3.6 of the Prescribed Reading for this
section to simplify drawing shapes using turtle instances.

Ensure that you understand what each line of code given in these sections does.
Note that some of the code examples introduce additional functionality of the
turtle objects, e.g., the penup(), pendown() and stamp() methods.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
65
4.3 FUNCTIONS

Prescribed reading
Read Chapter 4, “Functions” in the prescribed text by Wentworth et al. (2012),
How to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

This section introduces the concept of a function, which is just a named sequence
of instructions that together achieve some purpose, e.g., drawing a square using
turtles or sorting a list of numbers in ascending order. Combining sequences of
instructions together in named functions is one of the basic building blocks in
programming. Using functions sensibly can avoid duplication of code, thus
making the program shorter and easier to read.

4.3.1 Defining simple functions

Like for loops, function definitions are also compound statements, with a header
and a body part of the code. To create a function, we use the following code:
def funcname ( parameters ) :
statement_block

Note that as before the bolded text represents compulsory keywords and symbols
for defining functions, while the italics courier font denotes parts of the
code that are left to the programmer to insert.

Using the turtle example seen previously, we can rewrite the optimised code that
allows turtle alex to draw a square used in the activity in Section 4.2.3 above
as a simple function.

def drawsquare () :
for i in [0,1,2,3]:
[Link](50)
[Link](90)

or using a different for-loop construct that makes use of the range(n) function
which provides a quick way of producing the sequence of numbers 0 to n:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
66
def drawsquare () :
for i in range(4):
[Link](50)
[Link](90)

This function can then be used (called) in the rest of our program whenever we
require turtle alex to draw a square as shown in Listing 4.1.

Listing 4.1: Python code to allow turtle alex to draw two squares
import turtle
def drawsquare () :
for i in range(4):
[Link](50)
[Link](90)

wn = [Link]() # Set up the window and its attributes

[Link]("lightgreen")
[Link]("Alex")
alex = [Link]() # Create alex
drawsquare() # alex draws a square
[Link](100)
drawsquare() # alex draws another square
[Link]()

Activity
Execute the code in Listing 4.1 to see that using a defined function provides the
same result as when we explicitly wrote out the individual lines of code to draw
squares.

Now consider what would need to be changed to allow turtle tess to also be able
to draw a square. We could write a new function to allow tess to also draw
squares, something like:

def drawsquare_tess () :
for i in range(4):
[Link](50)
[Link](90)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
67
However, the code for this function is exactly the same as that for the original
drawsquare() except that we are using a different turtle object. Would it not be
useful if we could use the same function code for both turtle alex and turtle
tess?

This can be done by changing the way we define the function with the provision
of a list of parameters enclosed in parentheses. Up till now the parameter list
has been empty, but to generalize this function, we can add a parameter name
(say t) as a placeholder for an actual value that will be specified when we call
the function. So in this example, we would specify which turtle we want to draw
the square when we call the function. Note that the body of the function needs
to change accordingly to accommodate the use of the placeholder parameter
name.

The parameterized function becomes:

def drawsquare (t) :

for i in range(4):
[Link](50)
[Link](90)

and we call the function, providing the actual value for the parameter, like this:
drawsquare(alex)

We could of course, provide any number of parameters to generalize the function

even further. Perhaps we would like to be able to draw squares of different sizes.
This means we need to be able to change the distance the turtle moves forward.
We can do this by redefining the function as:

def drawsquare (t, size) :

for i in range(4):
[Link](size)
[Link](90)

and we call the function like this:

drawsquare(alex,50)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
68
Note that the definition of a function and the use (i.e., call) of that function are
two separate and distinct aspects of programming. The functions that we have
been defining here are often referred to as user-defined functions.

It is however, important to highlight that you have already used several other
functions, like print(), range() and str(), but that these functions are
provided as part of the Python as opposed to being user-defined.

In Listing 4.2 you will notice a string immediately after the function header. This
is termed a docstring and is given special treatment in the Python system.
Documenting what a function does and what is needed to call the function is
important to anyone wanting to use that function. Docstrings can be retrieved
at runtime to assist the user in this regard. This is the only way of providing
information about the code to the user at runtime, as all programmer comments
in the code are thrown away at the parsing stage, as these are purely aimed at
assisting the programmer in understanding the code while programming or
debugging.

Listing 4.2: Python code to allow any turtle object to draw squares of different sizes
import turtle
def drawsquare (t, size) :
"""Allow turtle t to draw a square with size dimension"""
for i in range(4):
[Link](size)
[Link](90)

wn = [Link]() # Set up the window and its attributes

[Link]("lightgreen")
[Link]("Alex")
alex = [Link]() # Create alex
drawsquare(alex, 50) # alex draws a square
[Link](100)
drawsquare(alex, 30) # alex draws another square
tess = [Link]() # Create alex
drawsquare(tess, 100) # tess draws a square
[Link]()

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
69
 Activity
Execute the code in Listing 4.2 to see how using parameters gives us more
flexibility and reuse of our function code.

Expand the code to add more turtles and experiment with changing the sizes of
the squares being drawn. You could also change the colour of each turtle to be
able to differentiate the squares drawn by each.

4.3.2 Functions calling other functions

Calls to other functions may be included as part of the body of a function. (Note
that you may also call the same function from within its own body, but this is an
advanced topic discussed in the section covering recursion much later.)

Note that when we call another function (say otherfunc()), the flow of
execution jumps to the first instruction in the body of otherfunc(), and when
that function finishes executing, execution flow returns to the statement
immediately following the call to otherfunc().

So consider writing a function to able to draw an equilateral triangle or hexagon

for example, i.e., other shapes that have equal length sides (like the square) but
with a different number of sides. A function for drawing an equilateral triangle
might look something like this:

def drawtriangle (t, size) :

for i in range(3):
[Link](size)
[Link](120)

Compared to the drawsquare() code, we have changed only the number of sides
(3 instead of 4) and the turning angle (120 instead of 90). It might make sense
to define a generic shape drawing function that contains the basic code that each
of these specialised functions can call.

def drawshape (t, size, numsides) :

for i in range(numsides):
[Link](size)
[Link](360/numsides)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
70
Now that we have this generic shape function, we can redefine our
drawsquare() and drawtriangle() using this helper function as follows:

def drawtriangle (t, size) :

drawshape(t, size, 3)

def drawsquare (t, size) :

drawshape(t, size, 4)

def drawoctagon (t, size) :

drawshape(t, size, 8)

In these examples, we have taken advantage of the similarity in the code for
these functions (i.e., the pattern), and made use of an existing function to
simplify the coding thereof.

Activity
Follow the instructions in Section 4.2 of the Prescribed Reading for this section
to see an alternative way of programming the drawsquare() function making
use of helper functions.

4.3.3 Arguments in functions

In the previous subsection we learnt how to make functions more general by

including parameters, the values for which are specified when we call the
function. These values that are provided in the function call are known as
arguments.

In fact, we have been using arguments for some time now when calling the built-
in Python functions, like print("something") and range(4). Here, the string
"something" is the argument for the print function while 4 is the argument for
the range function. Another example from Listing 4.2 is the code
drawsquare(alex, 50); here the arguments alex and 50 are passed in as the
initial values for the placeholder parameters, t and size, respectively.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
71
Python provides many other built-in functions, especially mathematical ones like:
 abs(-5) — computes the absolute value of the argument -5
 max(8,4,10) — computes the maximum of the values passed in as
arguments (note this function can take more than one argument)
 and many more.

4.3.4 Functions that return values

Python allows two distinct types of functions, those that calculate and return a
value that we can use (called fruitful functions) and those that just perform a
series of instructions and do not return any value (called void functions). Our
function drawsquare() is an example of a void function, i.e., this function merely
performs some instructions but does not return any value for later use in the
program.

The mathematical functions discussed in Subsection 4.3.3 are all fruitful

functions that return a value that we could use as part of an expression.

y = max(1,9,4) # assign the max value to y; so y = 9

x = abs(-5) + y # calculate abs value & add
print(x) # prints the value 14

Besides the built-in functions, we can write our own functions that return a value.
For example, if we wanted to calculate the area of a rectangle we could define
the following function:

def calcarea (width, height) :

area = width * height
return area

and then use it as follows:

area = calcarea(10,5)
print(area)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
72
In creating fruitful functions, we have introduced a new statement called return
which is followed by the value that we wish to return in the form of an expression.
So we could simplify our function to calculate area by writing it as:

def calcarea (width, height) :

return width * height

You should note that any variables we define inside a function can only be used
within the body of that function. Therefore, the variable area declared and used
in our first calcarea() definition cannot be used outside this function. We refer
to these variables as being local to the function. This is also the case for any
parameter variables that are defined in the function header; these too can only
be used inside the function body. If you attempt to use them outside the function
body you will get a NameError:

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

Activity
Write a fruitful function sumto(n) that returns the value of all integers from 1
to n. For example, sumto(5) will return the value 15 calculated as 1+2+3+4+5.

4.4 CONDITIONAL STATEMENTS

Prescribed reading
Read Chapter 5, “Conditionals” in the prescribed text by Wentworth et al. (2012),
How to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
73
In this section we explain the Python version of the selection construct (called
the if statement) that was introduced as a building block in Topic 2. But first we
explore ways of constructing Boolean expressions for use in conditions.

4.4.1 Boolean expressions

We have previously introduced a Boolean type as have a value either true or

false. Python supports a type called bool which can take one of the values True
or False (note the capitalization here, which is important).

A Boolean expression always has a Boolean value as its result. In creating these
expressions, we typically make use of the six comparison and/or three logical
operators listed below.

Comparison operators
== checks equality
!= checks inequality
> checks greater than
< checks less than
>= checks greater than or equal
<= checks less than or equal

Note that each of these operators has a logical opposite:

== is the opposite of != and vice versa
> is the opposite of <= and vice versa
<= is the opposite of > and vice versa

Logical operators
and logical and, which is true if both operands evaluate to true
or logical or, which is true if at least one of the operands evaluates to true
not negates the Boolean operand

Using these operators, we can create conditions of varying complexity such as:
17 >= 8 # evaluates to True
8 == 10 # evaluates to False
17 > 5 or 12 < 10 # evaluates to True
17 > 5 and 12 < 10 # evaluates to False

We can also assign Boolean values to variables:

adult = age >=21 # true if age >= 21 else false
teenager = age >= 13 and age < 20 # true if 13 <= age < 20
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
74
4.4.2 Truth tables and Boolean algebra

A truth table represents the output of the logical operators for all possible
combinations of values for the operands. This information is important to ensure
that when creating conditions, the correct Boolean value is obtained.

To set up a truth table we create a row for each different combination of the
operands and then fill in the output for a particular logical operator.

Thus the truth tables for the and and or operators would be something like:

First operand Second operand Result Result

(x) (y) (x and y) (x or y)
true true true true
true false false true
false true false true
false false false false

We can set up a truth table for the not operator as well, but as this operator
applies to only a single operand, we only need two rows in the table:

Operand Result
(x) (not x)
true false
false true

Boolean algebra provides rules whereby we can simplify complex Boolean

expressions, using rules of associativity, identity and many others similar to the
mathematical rules applied in numerical expressions. For example (note that in
the code below, ? denotes any Boolean value):

? and False == False

? or True == True
a and b == b and a
a or b == b or a
not (not a) == a

4.4.3 Python selection construct

In Topic 2 we discussed the selection if-else construct and its importance for
constructing algorithms. Python has a similar construct called the if statement.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
75
The syntax for this statement is given as:
if condition :
statement_block
else :
statement_block

The condition can be any test that produces a value of true or false, i.e., a
Boolean value. The else clause is optional and does not need to be present.
Finally, a statement_block means any number of valid Python statements all
indented to the same degree.

Some example uses of the if statement are given below:

age = int(input())
if age > 18 :
print("can vote")
else :
print("cannot vote")

a = int(input())
b = int(input())
if a > b :
max = a # storing max in case we need it later
print("maximum value is a", max)
else :
max = b # storing max in case we need it later
print("maximum value is b", max)

a = int(input())
if a < 0 :
a = abs(a)
print ("A positive value is ", a)

Chained if statements
If there are more than two options, we need to use what is referred to as chained
if statements, introduced by the keyword elif.

For example, consider an if statement that uses some input to determine which
user-defined function to call. If there are three different options we could code

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
76
this as follows (note that in this example we merely print what we would like to
achieve, we do not actually call the functions):

choice = int(input())
if choice == 1 :
print("call myfunction1")
elif choice == 2 :
print("call myfunction1")
elif choice == 3 :
print("call myfunction1")
else :
print ("Invalid input")

Nested if statements
If statements can also be used as a statement within the body of another if
statement. This is referred to as a nested if statement.

For example, using one if statement was sufficient to calculate the maximum of
two given numbers (as shown in the examples in Subsection 4.4.3). However,
what would happen if we needed to calculate the maximum of 3 or more
numbers?

In this case we would need to use another if statement in the body of each of
the if and else clauses to implement the correct decision making. Consider the if
statement below that calculates the maximum of 3 numbers:

a = int(input())
b = int(input())
c = int(input())
if a > b :
if a > c :
max = a
else :
max = c
else :
if b > c :
max = b
else :
max = c
print("Max number is ", max)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
77
 Activity
Define the function ttable() as given below. Now call it first with the argument
True and thereafter with the argument False, like this:
ttable(True)
ttable(False)
What does the output of this function represent in each of these cases?

def ttable(andop) :
if andop:
print(" i ", " j ", "i and j")
else:
print(" i ", " j ", "i or j")

for i in [True, False] :

for j in [True, False] :
if andop :
print (i, j, i and j)
else :
print (i, j, i or j)

Activity
Follow the instructions in Section 5.12 of the Prescribed Reading for this section
to create a Turtle Bar Chart.
Do not forget to add code to set up the screen and create a turtle tess.
Ensure that you understand exactly what each line of the code is aiming to
achieve.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
78
4.5 FRUITFUL FUNCTIONS AND CODE DEVELOPMENT

Prescribed reading
Read Chapter 6, “Fruitful functions” in the prescribed text by Wentworth et al.
(2012), How to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

In this section we look at more complex behaviour of fruitful functions, i.e., those
functions that can return a value. We also introduce some rules for good coding
practice as well as additional debugging features in the Thonny debugger to help
create bug-free code.

4.5.1 Return statements again

We previously introduced the return statement which is used to exit a function.

Note that this statement can be placed at any point in the function, but when it
is executed, the function immediately stops and control flow returns to the code
from where the function was called. Thus any code that appears after the return
statement in the same path, will never be executed and is effectively dead code.

def myfunc() :
print("hello")
return
print("goodbye")

If we were to execute the function above by calling myfunc(), "goodbye" will

never be printed, as the function exits (or returns to where it was called from)
at the return statement.

Return statements within fruitful functions must include a return value, which
can be retrieved in the code that calls the function. This could be done by
assigning the return value to a variable or by using the return value directly in
an expression or as an argument in another function call. Some examples of
using these return values are given below.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
79
def calcmax3(a, b, c) :
if a > b :
if a > c :
max = a
else :
max = c
else :
if b > c :
max = b
else :
max = c
return max

x = int(input())
y = int(input())
z = int(input())
print("Max number is ", calcmax3(x,y,z))
w = calcmax3(x,y,z)
print("Max number is ", w)
v = calcmax3(x, y, z) * 2
print("2 x max number is ", v)

Note that return statements can appear within an if statement, but care must
then be taken that each different execution path has its own return. For example
we could redefine calcmax3() as follows with four return statements
corresponding to the four execution paths:

def calcmax3(a, b, c) :
if a > b :
if a > c :
return a
else :
return c
else :
if b > c :
return b
else :
return c

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
80
Note that if you have multiple execution paths in the code for a function body
(due to the use of the if statement), leaving out one of the return statements
will result in a Nonetype being returned as the return value for that execution
path.

Activity
Consider the two functions abs_value() and bad_abs_value() that aim to
calculate the absolute value of a given value. Execute the test code given as print
statements, to help you understand why the one function works and the other
does not.

def abs_value(x):
if x < 0:
return -x
return x

def bad_abs_value(x):
if x < 0:
return -x
elif x > 0:
return x

print (abs_value(-2))
print (abs_value(2))
print (abs_value(0))
print (bad_abs_value(-2))
print (bad_abs_value(2))
print (bad_abs_value(0))

4.5.2 Boolean functions

Fruitful functions can also return Boolean values. Such functions are often useful
to simplify conditions. See the code for the function is_even() given below and
its use in the condition of the subsequent if statement:

def is_even(n) :
if n % 2 == 0 :
return True

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
81
 return False

val = int(input())
if is_even(val) :
print(val, " is even ")
else :
print(val, " is odd ")

Note that this is a very trivial example and having is_even() as a separate
function does not save much in the way of a complicated condition. However, the
example is useful for illustrating the use of fruitful Boolean functions.

4.5.3 More on debugging and testing

When developing new program code (and especially new functions) it is helpful
to test the new code frequently to ensure that it works correctly.

So for example, when developing new functions, it is advisable to develop these

in an incremental fashion to ensure that each new line or couple of lines of code
work as expected. By doing code development in this way, if you have made an
error, it will be easier to find and correct it if there are only a few new lines of
code to consider, rather than having to go through a complete program.

You can also make use of the Thonny debugger to check the values of your
variables at various points in the executing code. To do this, set a breakpoint at
the line of code you wish to inspect by clicking on the line number on the left of
the editor window. A red dot will appear. Then start the code running in debug
mode (by clicking on the bug and not the white arrow in the green circle as
normal). When the code reaches the breakpoint, you can single step through
each line of code using the “step over” option.

Or you can choose the “step into” arrow, which will show you exactly what is
happening whilst executing that line of code, including variable values and if the

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
82
code involves a function call, a new window will appear with the code for the
function called as well as all the local variables for that function.

An alternative way of debugging is by inserting extra print() instructions at

various points in the code. These instructions can confirm that a particular point
in the execution has been reached, but can also provide information on values of
variables.

Consider the code below which includes extra calls to print() to give the values
of the variables on each iteration of the loop. Note that these calls to print()
are not needed to solve the actual problem, but are merely there to provide the
programmer with information on what is happening in the code.

def sum(n) :
total = 0
for i in range(5) :
print("i = ", i) # not needed to solve problem
total = total + i
print("Total = ", total) # not needed to solve problem
return total

sum(5)

Testing correctness of individual functions is best done through a process known

as unit testing. This involves running a series of tests (called a test suite) on the
function and checking that the return value or printed output is as expected.

Activity
Follow the instructions in Section 6.7 of the Prescribed Reading for this section
to practice executing a test suite on a given function to check that all test cases
run correctly.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
83
4.6 ITERATION AGAIN

Prescribed reading
Read Chapter 7, “Iteration” in the prescribed text by Wentworth et al. (2012),
How to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

4.6.1 Some revision on assignments

An assignment statement allows a variable to be assigned a value using the

assignment operator =. It is important to always initialise a variable (i.e., give
the variable a value) before trying to use that variable in some expression:

x = 10 # initialise variable x by assigning a value to it

y = x + 5 # using the value of x to initialise variable y
x = 55 # assigning a new value to x

In the code above, it is important to note that variables can be assigned values
multiple times. The value stored in a variable may differ at different times during
the execution of some code, depending on whatever the most recent assignment
value is.

Note that if we were to execute a statement like:

b = r
without first initialising variable r, we would receive the following error:
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'r' is not defined

Finally, be careful not to confuse the assignment operator = and the equality test
operator ==. The former ensures that we can assign values to variables, while
the latter is used to evaluate a condition giving a Boolean result.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
84
4.6.2 For loop revisited

We introduced the for loop in Section 4.2.2 using the following example:

for f in ["Joe","Zoe","Brad","Angelina","Zuki"]:
invite = "Hi " + f + ". Please come to my party!"
print(invite)

Here we refer to f as the loop variable, which on each iteration of the loop will
be assigned one of the elements in the list in succession. Running through all
elements in a list is referred to as traversing the list.

Thus, on the first iteration of the loop, the assignment

f = "Joe"
will be done before entering the loop body.

On the next iteration of the loop, the assignment

f = "Zoe"
will be done before executing the loop body, and so on.

Activity
Step through the function to calculate factorials given below (either by hand or
using the Python debugger) to ensure you understand what the values are of
product and j on each iteration. Note that factorials can only be calculated for
positive integers.
Remember that range(n) evaluates to the series of values 0 … n-1 and hence
the need to multiply by (j+1).

def factorial (n) :

product = 1
for j in range(n) :
product = product * (j+1)
return product

print(factorial(3)) # should print 6

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
85
4.6.3 Repetition using a while statement

The while statement (or loop) in Python is very similar to the repetition construct
of the same name we discussed in Section 2.5.3, but has slightly different syntax:
while condition :
statement_block

Execution of a while loop starts by first evaluating the condition and if this
evaluates to true, the loop body is executed once. Thereafter, the condition is
once again evaluated and if it is still true, the loop body is again executed. When
the condition evaluates to false, the while loop exits and execution of the code
continues at the statement immediately after the while statement.

As an example of how this construct is used in Python, let us consider an earlier

algorithm to decrease the value of a user input number until it is less than or
equal to zero. In Python this portion of code might look like:

x = int(input())
while x > 0 :
print("Value of x =", x)
x = x - 1
print("Final value of x =", x)

Note that the print statements are included only to provide evidence that our
algorithm works. You should test this code with input values 5, 0, -1 for
example.

One of the main differences between the for loop and the while loop is that in
the former, the programmer sets up the loop to perform a fixed number of
iterations. Thus, the for loop automatically terminates after these iterations have
been completed. In the while loop, the condition is evaluated at the start of every
iteration and the result of this evaluation (i.e., either true or false) determines
whether the loop continues for another iteration or exits.

What this means is that the programmer must manage the termination of the
loop by ensuring that within the body of the while loop, one or more of the
variables used in the condition are changed, so that eventually the condition will
evaluate to false, and the loop can terminate. In our example above, the value
of x is decreased in the body of the loop until it reaches 0 and the loop then
terminates.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
86
Whilst it may seem that the while loop is more complicated than the for loop,
there are situations where the while loop is the preferred choice and can actually
simplify our code. Generally, if one can specify prior to execution what the
maximum number of iterations would be (i.e., when traversing a list, or
performing an operation a given number of times) then the for loop would be the
preferred construct to use. This is known as definite iteration. On the other hand,
indefinite iteration means that we cannot be sure how many times the loop will
need to be performed, in which case using the while loop is the better choice.

Note that later when we have more statements at our disposal, we will see that
we do not necessarily have to stick rigidly to this choice of the more sensible
construct.

Activity
Work through the Collatz problem given in Section 7.5 of the Prescribed Reading
for this section to see how using the while statement makes coding this solution
fairly trivial, whereas using a for loop at this stage would be near impossible.

4.6.4 Tracing the execution of a program

In Section 3.6.2 we introduced various ways of debugging code. Here we expand

on the idea of working through the code by hand in a process also known as
tracing a program. Having the ability to act like the computer and work out how
the value of each variable changes and also what output is created is a very
valuable skill for a programmer.

Tracing can be done by creating a table with a column for each variable, and also
a column for output produced. Then for each line of code we add any changes in
variable values or printed output to this table. In this way we can “execute” each
line of code to see that it achieves the correct results.

This process is a very tedious one, and for this reason we often resort to our
automated debuggers to assist. Using the debugger to single-step through the
code achieves the same result as checking each line manually, although this
manual process needs to be understood by all programmers.

Besides debuggers, there are also other tools that can help visualise the
execution of program code, but for now we suggest you gain experience in hand
tracing or using the Thonny debugger to assist in ensuring that your code is
error-free.
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
87
 Activity
Consider the Counting Digits problem given in Section 7.7 of the Prescribed
Reading for this section.
Trace the execution of the following line of code:
print(num_digits(710))
which should output 3.

4.6.5 Abbreviated assignment

Assignment statements like:

var = var + 1
var = var * x

appear frequently in program code. Thus, short cuts are provided in the form of
operators +=, -=, *=, //=, %= to make writing code like that given above
quicker and simpler:
var += 1
var *= x

4.6.6 Notation used in Python documentation

Extensive documentation is available for Python, including a manual giving

information on all built-in functions and types, libraries and modules. The Thonny
IDE does not have a menu item to access this documentation, but it can be
accessed through the following link:
[Link]

Figure 4.1: Python documentation for range(), available at:

[Link]

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
88
Consider Figure 4.1 which contains a section of information about the range()
function taken from the Python documentation.

The information given in Figure 4.1 can be deciphered as follows: There are two
forms of a call to range(). The first requires only a single argument (stop),
while the other requires both a start and stop argument, with or without a step
argument given. Thus, a call to range() can include either 1, 2, or 3 arguments.

To understand how we derived this information requires us to be able to

differentiate between what is the actual required syntax of a particular construct
and what is meta-notation. Meta-notation is defined as symbols or notations used
to help describe the syntax of a construct, but which do not form part of the
syntax itself.

Meta-notation is often included by way of using different formatting. Text in bold

type represent keywords that must be typed exactly as given in the syntax,
whereas text in italics represents aspects of the syntax that must be “something
of the same type ” as what is given in italics and possibly expanded on in the
description. So in this case stop, start and step must all be integer values or
variables.

Additional inclusion of meta-notation is found in the use of square brackets,

which is not part of the syntax, but denotes an optional part of the syntax. So,
the inclusion of “, step” is optional, and if not present in the syntax, defaults to
the value 1.

4.6.7 Generating and printing multi-dimensional tables

Multi-column tables (like multiplication or log tables) can be generated using a

loop. So for example if we wanted to generate the results of the 7-times table,
we could write code like:

for k in range(12) :
print (7 * (k+1)) # range(12) gives 0 .. 11, hence using k+1

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
89
which gives the following output:

7
14
21
28
35
42
49
56
63
70
77
84

This is not a very useful table, so we might like to make it more descriptive by
adding a column that contains the value of the loop variable, by changing the
print statement to:
print (k, 7 * (k+1))

This gives the following output, which whilst being more descriptive is not strictly
tabular (due to the values having different numbers of digits):

1 7
2 14
3 21
4 28
5 35
6 42
7 49
8 56
9 63
10 70
11 77
12 84

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
90
We can fix the layout by inserting a tab character between the two values and
possibly also adding some labels at the top using the code below:

print("Seven times table")

print("Multiplier", '\t' "Result")
for k in range(12) :
print (k+1, '\t', '\t', 7 * (k+1))

This gives the following tabular and much more descriptive output:

Seven times table

Multiplier Result
1 7
2 14
3 21
4 28
5 35
6 42
7 49
8 56
9 63
10 70
11 77
12 84

The “\t” string represent a tab character which causes the output to be moved
to the next tab stop.

From previous usage of the print statement, you should be aware that each time
you call print(), the arguments are printed followed by a newline character
(i.e., the next output will appear on a new line below). Sometimes however, we
wish a series of print statements to continue printing on the same line. To do this
we make use of an extra last argument, namely end =" ". Having an end=
argument suppresses the output of a newline and instead prints whatever
appears as the string.

Given below is the code used to print the output of the 7 times table as a single
line of numbers using the original version of our code we write:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
91
for k in range(12) :
print (7 * (k+1), end =" ")
print() # this prints a newline as usual

which outputs:
7 14 21 28 35 42 49 56 63 70 77 84

Now that we have code to print a 7 times table, we encapsulate this code into a
function that can then be transformed for more general use, such as being able
to print other times tables as well. This generalization step is similar to what we
did with the draw_square() function in an earlier topic when we created a
generalised draw_shape() function.

Code for times7() could be written as:

def times7 () :
for k in range(12) :
print (7 * (k+1), end =" ")
print()

while a more general function that can print the times table for any given number
could be generalised as:

def timesx (x) :

for k in range(12) :
print (x * (k+1), end =" ")
print()

Finally we might like to use this generalized function to produce a complete times
table for all values in a given range (say 1 .. 5) such as illustrated below:

1 2 3 4 5 6 7 8 9 10 11 12
2 4 6 8 10 12 14 16 18 20 22 24
3 6 9 12 15 18 21 24 27 30 33 36
4 8 12 16 20 24 28 32 36 40 44 48
5 10 15 20 25 30 35 40 45 50 55 60

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
92
To write such a generalized function we need to make use of a nested loop –
were the outer loop cycles through all the values in the range provided, whilst
the inner loop calls timesx() for the current value of the outer loop’s loop
variable:

def timesx (x) :

for k in range(12) :
print (x * (k+1), end ="\t")
print()

def timestable(start, stop) :

for k in range(start, stop+1) :
timesx(k)

timestable(1, 5)

You may notice that we have substituted a tab character instead of a number of
spaces to be used between output values from the print statement in timesx().
This is done to ensure that we line up all values correctly.

You may also have noticed that both functions timesx() and timestable()
make use of a variable k. This variable is considered local to each function, i.e.,
these are actually two different variables whose values cannot be used outside
of the function in which the respective k variable is found.

4.6.8 Break and continue statements

Thus far, when using the while loop, we have always checked for termination of
the loop at the start by using a condition that evaluates to a Boolean variable.

For example, the following code

while x > 0 :
# do something
x = x - 1

will continue executing until the value of x is <= 0.

Sometimes, it makes programming easier having a mechanism that can test for
termination in the middle of the body of the loop and exit if necessary. For
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
93
example, when processing user input, one might wish to terminate when the
user types in a certain value (for simplicity let us call this termination value a
flag). To do this, an algorithm such as the following would be needed:

while looping
input x
if x == flag then
exit loop
do something with x

Python has a break statement to do exactly this, i.e., exit a loop from somewhere
within the body.

To show how this statement works, we use as an example the problem of finding
the largest number in a series of positive integers input by the user. As soon as
the user enters a negative number, the program halts after printing the largest
value found.

Note that since we don’t know how many iterations we will need to execute, we
can set up an infinite while loop by using a condition that always evaluates to
true. The simplest such condition is using just the constant True.

# calculate the largest value of positive numbers input by user

largest = -1
while True :
x = int(input())
if x < 0 :
break # this exits the loop completely
if x > largest :
largest = x
print("largest=", largest)

Activity
Implement the code for the simple guessing game given in Section 7.17 of the
Prescribed Reading for this section. Trace the execution of this code to see how
different input values result in different execution paths through the while loop
and how the game eventually terminates.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
94
Python also provides a continue statement which differs slightly from the break
statement. Although it is also used within the body of a loop, instead of exiting
the loop completely, the continue statement skips any statements that come
after it in the body of the loop and proceeds directly to the start of the next
iteration of the loop.

For example, we could change the code in our previous example for calculating
the largest positive number by allowing the user to input any number, and then
effectively ignoring any negative number by using a continue statement.

#calculate largest positive number from any 10 numbers input

largest = -1
posnum = 0
for i in range(10) :
x = int(input())
if x < 0 :
continue # ignore values < 0 by jumping to loop start
posnum += 1
if x > largest :
largest = x
print(posnum, "positive numbers found. Largest=", largest)

4.6.9 More complex loops

We have seen several examples of loops thus far, but here we introduce a few
new ideas.

In the next topic, we discuss in detail the use of a new paired data type, known
as a tuple. However, to illustrate some of the more complex loop structures, we
briefly introduce this concept here.

Python allows us to make a pair of data items simply by combining them in

parentheses, so as one example, we could keep names of students and their test
marks together as a pair: ("Mickey Mouse", 55)

We could also create lists of these (name, mark) pairs:

testmarks = [("Mickey Mouse", 55), ("Donald Duck", 80),
("Tin Man", 40) ]

and print them all out:

print(testmarks)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
95
Or, we could just print out those students that had a test mark < 50. This would
involve traversing through the list and checking whose mark was < 50 and then
printing the name part of the paired data:

for (name, mark) in testmarks :

if mark < 50 :
print(name)

In the above code we see that our loop is controlled by two variables associated
with the paired data. On each iteration of the loop, each of these variables is
given a value based on the contents of the next pair in the data being analysed.

Assume now that instead of only having one test mark, each student has 5 test
marks. We could store this as paired data, where the second item in the pair is
a list of test marks: ("Mickey Mouse", [55, 44, 66, 77, 33])

Now assume we wanted to print the average test mark for each of our students,
we could use a nested for loop, i.e., a for loop within another for loop. The outer
for loop traverses through the list of paired student data, while for each student
the inner for loop traverses through the test marks summing these to calculate
the total mark.

for (name, marks) in classmarks :

total = 0
for score in marks :
total += score
print (name, "\t", total/5)
print("That's all folks!")

Activity
Implement the code for Newton’s algorithm for finding square roots in Section
7.23 of the Prescribed Reading for this section. This code shows a useful example
of using approximation algorithms for calculations, as well as an infinite loop with
an exit in the middle of the body. Ensure you understand what each line of code
is aiming to achieve.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
96
 Summary

This topic introduced the basic building blocks (both constructs and data
structures) for creating simple Python programs.

The turtle module was introduced and simple graphics programs were
demonstrated using the methods and attributes of the turtle object. User-defined
functions were covered next, showing how code can be packaged into a function
and then used repeatedly. Variations on generalising functions using parameters
were also shown. In a later section, the ability of a function to return a value
using the return statement was discussed.

Before introducing the Python selection statement, a summary was given of

Boolean algebra and its use to create Boolean expression to be used as
conditions. Truth tables related to the various logical operators were also
explained. The syntax and semantics of the Python if-else and elif statements
were described with several example programs for illustration.

Python iteration constructs, the while and for loops, were covered in-depth.
Differences and similarities in their use were explained, as well as the break and
continue statements used to exit loops prematurely or skip iterations,
respectively. This section also covered additional debugging techniques in the
form of tracing a program, adding documentation strings to programs for use at
runtime, and the use of abbreviated assignment statements.

Self-Assessment Questions

1. Write a program that uses the void function drawsquare() defined in Listing
4.2 in Section 4.3.1 to draw the image shown below. Assume the sides in
the small squares are 20 units and those in the large squares are 40 units.

2. Rewrite the factorial() code given in Section 4.6.2 to prevent incorrect

factorial values from being calculated if the function is called with an
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
97
 argument that is not a positive integer. The function should report an error
to the user if the argument is < 0 and should terminate without executing
the loop.

3. Write a function checkprime() that takes one parameter and returns a value
of True or False, depending on whether the argument given is a prime or
not. Your function should report an error to the user if the argument is < 0
should terminate immediately without further calculation. Your program
should exit as soon as it has a decisive result and should not do any
unnecessary calculations.
See the use cases below:
print(checkprime(-1)) # prints Error
print(checkprime(23)) # print True
print(checkprime(55)) # print False

4. Write a program that prints out a truth table for the logic expression given
below. That is, write out the result of evaluating the expression for all
combinations of x, y, and z.
(x or y) and (not x and z)

5. Fizz Bang is an old fashioned counting game that helps children with their
maths skills. Children take turns to say the next number between 1 and 100,
but instead of always saying the number, the following rules apply:
a. if the number is divisible by 3, say “Fizz”
b. if the number is divisible by 5, say “Bang”
c. if the number is divisible by both 3 and 5, say “FizzBang”
d. otherwise, say the number

These rules would lead to children counting as follows:

1, 2, Fizz, 4, Bang, Fizz, 7, 8, Fizz, Bang, 11, Fizz, 13, 14, FizzBang, 16, 17,
Fizz, 19, Bang, Fizz, 22, etc.

You need to write code to implement this game, i.e., to print out what the
children would say.

First, write a function fizzbang() that takes one parameter (a number) and
returns what should be said/printed for that number.
For example,
fizzbang(5) → Bang
fizzbang(15) → FizzBang
fizzbang(9) → Fizz
fizzbang(2) →2
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
98
 Now write code that can process numbers (by calling fizzbang() for each
number) in a given range, which is input as start and end points (both
inclusive) by the user. If the end point is smaller than the start point, the
game goes in reverse, i.e., starting at the end point and counting backwards.

For example, if the user inputs 3 and 10 as the range for counting, your
program should print:
Fizz, 4, Bang, Fizz, 7, 8, Fizz, Bang

6. As additional practice in coding, try some of the exercises given at the end of
Chapters 3—7 of the prescribed text by Wentworth et al. (2012), How to
Think Like a Computer Scientist, 3rd edition, Runestone Academy.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
99
 Topic 5
Compound data structures, modules and files

5.1 INTRODUCTION

This topic relates to the following module outcomes:

3. Show mastery of basic programming constructs in the context of the

Python programming language by converting hand-crafted algorithms into
Python code.
4. Design efficient Python solutions to simple mathematical and logic
problems.

On completion of this topic satisfying module outcomes 3 and 4, you will have a
better understanding of additional data types as well as further programming
concepts with which to create solutions to more complex problems.

This topic first introduces various compound data types (as opposed to the basic
types that have been used up until now) and shows how variables of these types
can be used in programs. The first type that is introduced, is the string, which
has already been used in small programs, but without any explanation of how
string variables can be manipulated. Thereafter, tuples and lists are introduced,
together with functions and algorithms for creating and manipulating variables
of these types. Examples programs are used to highlight the similarities and
differences in the use of these compound types.

Additional Python programming constructs in the form of user-defined modules,

and input/output to files allow for more flexibility in writing code. Creation of
user-defined modules also allows the seamless reuse of previously written code,
while file input and output makes entering data into a program and obtaining
output more practical and efficient.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
100
In this topic, you will gain knowledge in the following areas:

1. String manipulation
2. Effective use of tuples as a data structure
3. Definition and manipulation of lists
4. Further use of predefined modules
5. File input and output
6. Algorithms for manipulating lists

The following assessment criteria for sub-topics relate to module outcomes 3 and
4:
 Data structures: Explain how each of the compound data types (strings,
tuples and lists) is constructed and show how these can be used in
solving more complex problems, and/or writing more efficient code.
 Python programming: Explain the benefits of creating user-defined
modules, and show how these can be used in practice.
 Python programming: Understand the difference between input from and
output to the standard input/output devices (i.e., keyboard and monitor,
respectively) and that from/to files. Show how file input/output can be
used effectively.

5.2 STRING MANIPULATION

Prescribed reading
Read Chapter 8, “Strings” in the prescribed text by Wentworth et al. (2012), How
to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

Thus far we have made use of several built-in data types, including the simple
types, int, float, and bool, where each variable of such a type can only contain
one piece of data. We have also been introduced to strings, lists and pairs which
we refer to as compound types, since the data can be broken up into smaller
pieces. Variables of the string type (str) can be broken up into smaller strings
containing one of more character. For example, the string:
"abc"

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
101
can be decomposed into several individual strings
"a" + "b" + "c"
or the strings
"ab" + "c"

Activity
Follow the instructions in Sections 3.1 and 3.2 of the Prescribed Reading for this
section, to draw some simple shapes using two turtle instances.

Ensure that you understand what each line of code given in these sections does.

5.2.1 Strings as objects

We have already been introduced to the idea of attributes and methods when
programming with turtle objects. Since strings (like turtles) are also objects,
each string has its own attributes and methods. Of course the kinds of attributes
and methods differ for turtles and strings. Whereas we might have called the
forward method of a turtle or set the color attribute of a turtle, as follows
[Link](100)
[Link]("red")

for strings we have completely different methods and attributes.

For example, the upper() and lower() methods are used to change the case of
a string into all uppercase or all lowercase characters, respectively.

>>> mystring = "hello"

>>> uppmystring = [Link]()
>>> uppmystring
'HELLO'
>>> lowmystring = [Link]()
>>> lowmystring
'hello'

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
102
There are many methods for strings including those for finding the length of a
string, identifying a particular substring in a string, formatting and justifying a
string, partitioning a string in various ways, and many more. Some of these are
discussed in the subsections below, but a complete list of methods can be found
in the standard Python documentation at:
[Link]

5.2.2 Accessing parts of the string

An index is used to identify a single character in a string, where the index zero
indicates the first character in the string. In Python, a number within square
brackets, e.g., [3], is used to indicate an index. So, to find the second character
of mystring as defined below, we would execute:

>>> mystring = "hello"

>>> mystring
'hello'
>>> mystring[1]
'e'

It might also seem odd to use the index 1 to find the 2nd character in the string,
but this is due to the fact that in most computer programmer languages, all
indices start at 0 and not 1.

Note that since Python does not have a distinct character type, a character is
just depicted as a string of length 1, i.e., only one character in the string. Thus,
a string type is always returned when using an index on a string. It is also worth
noting that since lists are also made up of distinct parts, we can also use an index
on a list variable to return the particular element at that index. This is discussed
further in Section 5.4.

Note that unlike most other programming languages, Python allows the use of
negative integers as indices. A negative index means that the index value is
calculated going backwards from the end of the string, rather than going
forwards from the start of the string:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
103
>>> strng = "hello world!"
>>> strng[-1]
'!'
>>> strng[-5]
'o'

5.2.3 Traversing a string

A built-in function, len() can be used to find the length of a particular string,
i.e., the actual number of characters in the string:

>>> len(mystring)
5

This length function can similarly be used with lists, but more about this later.

The length function is useful if we want to traverse through each character in the
string to do something. If we know how many characters there are in the string,
we know how many iterations we need to set up in a loop to achieve this.

For example, we may wish to print out each character in a string in a particular
format, like for example, one character per line:

h
e
l
l
o

Code to do this would be:

mystring = "hello"
index = 0
while index < len(mystring):
print(mystring[index])
index+=1

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
104
Alternatively, if we wanted to print out the string in reverse order, we could write
code like:

mystring = "hello"
index = len(mystring) - 1 # start at last character
while index >= 0 :
print(mystring[index])
index-=1

A simpler way of programming the above is to use one of the for-loop constructs
that automatically traverses compound types and on each iteration sets the loop
variable to the next element in the compound type. Previously we used this kind
of for loop with lists, but it is also applicable for use with strings. When used with
string types, at each iteration the loop variable contains the next character in the
string:

mystring = "hello"
for ch in mystring :
print(ch)

5.2.4 Slicing up a string

Using a range of indices written as [m:n], we can slice up strings into smaller
substrings. The substring is created from the mth character in the main string,
up to, but not including, the nth character. For example, if mystring contains
the string "abcde",
print(mystring[1:4])
outputs the string bcd .

For ease of coding you can omit the starting point (in which case this defaults to
the start of the string) or the end point (in which case this includes everything
going forward to beyond the end of the string) of the range or both. So [ : 4]
means all characters from the 1st up to and including the 4th character; [3 : ]
means all characters from the 4th up to and including the last character; and [
: ] means all the characters in the string.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
105
5.2.5 Comparing and altering strings

Strings can be compared using the comparison operators discussed in Section

4.4.1. Thus, to check whether two strings are the same we can use code like:
if a == b :

Alternatively, to compare strings based on an alphabetic order, we could use

code like:

a = "small"
b = "big"
if a > b :
print("string a is later in alphabet")
else :
print("string b is later in alphabet")

Note that due to the representation of characters in a computer (which for those
interested, uses ASCII, which stands for American Standard Code for Information
Interchange and is based on integer numbers), all capital letters have a smaller
integer representation than lowercase letters, so the ordering obtained from
using the comparison operators may not be exactly as you would expect.

Activity
To fully understand the result of comparing various strings, replace "small" and
"big" as the values for a and b in the code given above with the following string
pairs and rerun the code:

"bigger" and "big"

"BIGGER" and "big"
"Bigger" and "bigger"
"BiggeR" and "Bigger"

Experiment with other pairs as well, to fully understand how the comparisons
work on a character by character basis.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
106
Whilst comparison of strings is a valid operation, altering a string is not. So, one
cannot change one of the characters in a string using code like:

>>> mystring = "hello"

>>> mystring[0] = "H"
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

Since strings are considered immutable (i.e., unchangeable), a string cannot be

changed once it has been created. The only way to obtain a changed string is to
create a new string with the desired change. So, the string "Hello" can be
obtained with code like:

>>> newstring = "H" + mystring[1:]

>>> print(newstring)
Hello

5.2.6 Identifying substrings

In mathematics, the in operator is normally used as a set operator and tests

whether the element given as the left operand is a member of the set given as
the right operand. In Python, when both operands are strings, the in operator
outputs a Boolean value denoting whether the string given as the left operand is
a substring of the string given as the right operand. Thus, membership in this
context means “is a substring of”.

Similarly the Python operator not in outputs whether the left operand “is not a
substring of” the right operand.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
107
 Activity
Execute the following lines of code to see how the in and not in operators
work:

"hello" in "hello"
"hel" in "hello"
mystring = "hello"
"hel" not in mystring
"hellos" in mystring

5.2.7 Finding and counting characters in strings

Two well-used algorithms are those for finding or counting the number of
occurrences of a particular character (or substring, which becomes a slightly
more complex problem) in a larger string. Both rely on traversing the string in
some way and comparing each character in the string with the character being
sought or counted.

A typical function for finding a character involves traversing the given string and
returning the index of the character where it was found. If the character is not
present in the string, one might return an improbable index, say -1. A simple
function to do this (which relies on two arguments namely, the string and the
character to find) could be coded as:

def findit (mystr, mych) :

i = 0
while i < len(mystr):
if mystr[i] == mych :
return i # found mych at this index
i += 1
return -1 # mych not found in mystr

Counting occurrences of a character in a larger string is very similar to the

findit() definition given above:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
108
 def countit (mystr, mych) :
i = 0
count = 0
while i < len(mystr):
if mystr[i] == mych : # add 1 if found mych
count += 1
i += 1
return count # return total counted

Various extensions can be added to these functions, including setting a start and
end index demarcating in which subsection of the string the search should
happen and many others. However, there is also a built-in string method
find(), which provides several variations on this theme.

Activity
Execute the following lines of code to see how the built-in find() method
works:
mystr = "This is a very long string"
[Link]("i")
[Link]("i", 8)
[Link]("i", 8, 13)

You may like to look up the definition of this method in the Python string methods
documentation to see how the arguments can be used to constrain the search.
[Link]

5.2.8 Splitting and formatting strings

Another useful built-in string method is split(), which splits a string into a list
of individual words according to the spaces or some other given delimiter that
separates the words. Some examples of the use of this method are given below:

>>> mystr = "This is a very long string"

>>> [Link]()
['This', 'is', 'a', 'very', 'long', 'string']

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
109
>>> mystr2 = "This,is,a,very,long,string"
>>> [Link](",")
['This', 'is', 'a', 'very', 'long', 'string']

The built-in string format() method allows the dynamic creation of strings, e.g.,
those that include the results of runtime calculations, together with a variety of
formatting applied to different parts of the string.

To achieve this, a template string that uses placeholders, depicted as {0}, {1},
etc. is created. Some examples of using this method are given below:

>>> mystr = "His name is {0}".format("Mickey Mouse")

>>> print (mystr)
His name is Mickey Mouse
>>> mystr2 = "His name is {0} {1}".format("Mickey", "Mouse")
>>> print(mystr2)
His name is Mickey Mouse
>>> mystr3 = "His name is {1} {0} with age
{2:.1f}".format("Mickey", "Mouse", age)
>>> print(mystr3)
His name is Mouse Mickey with age 5.2

Note that the placeholder numbers relate to the positions of the arguments
supplied to the format method call. In the last example given above, "Mickey"
is in position 0, "Mouse" is in position 1 and age is in position 2.

Also note that formatting of floating point numbers is done by attaching a format
to the placeholder number. In the last example above, {2:.1f} states that the
argument in position 2 must be formatted as a floating point number to 1 decimal
place.

Activity
Work through the code examples in Sections 8.15 and 8.16 of the Prescribed
Reading for this section. This code shows useful examples of the various string
methods discussed above. Ensure you understand what each line of code is
aiming to achieve.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
110
5.3 USING TUPLES

Prescribed reading
Read Chapter 9, “Tuples” in the prescribed text by Wentworth et al. (2012), How
to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

In Section 4.6.9 we made used of pairs of data items, e.g., ("Mickey Mouse",
55). This grouping of data items is formally known as a tuple and is a good
example of a data structure, which is a mechanism for organizing data for ease
of use.

5.3.1 Creating tuples

A tuple can contain any number of data items, normally enclosed in parentheses
with each item separated by a comma. Tuples are also known as records in some
programming languages, and allow us to group items of related data in a single
structure.

The index operator and the associated ranges that were previously used with
strings, are also applicable to tuples. Additionally, like strings, tuples are
immutable, so once they are created their contents cannot be changed. However,
there is nothing preventing us from reassigning the tuple variable to a different
group of data items.

The tuple below contains information about the Walt Disney character, Mickey
Mouse, who first appeared in a film in 1918 and has a girlfriend called Minnie
Mouse. Note that assigning values to a tuple, as shown below, is known as tuple
packing.

characterinfo = ("mickey mouse", "Walt Disney", 1918, "minnie

mouse")

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
111
As can be seen in the assignment above, tuples can contain items that are not
all the same basic type. This property of a tuple is known as being
heterogeneous.

Since we cannot change any item in this tuple after it has been assigned, if we
need to alter the information, we must reassign the new information to the same
or a different tuple variable. So, if for example, the date when Mickey Mouse first
appeared in a film was 1928 and not 1918, we cannot make the change as
follows:

>>> characterinfo[2] = 1928

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

but instead need to reassign the variable:

characterinfo = ("mickey mouse", "Walt Disney", 1928, "minnie

mouse")

Note that if tuples with only one item of information are created, the comma
after the first item must be included:
moviesSeen = (“Apocalypse”, )

By omitting the comma, we would simply be creating a string variable and not a
tuple variable.

5.3.2 Tuple assignment

This is a powerful assignment feature, where we can do multiple assignments in

one statement. For example, if we needed to assign simple variables name,
creator, firstmoviedate and girlfriend to each have a value, we could do
so with the single assignment, which is known as tuple unpacking:

(name, creator, firstmoviedate, girlfriend) = characterinfo

where characterinfo contains the information described above.

We can confirm that all the variables have been assigned correctly by executing
the following code:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
112
>>> name
'mickey mouse'
>>> creator
'Walt Disney'
>>> firstmoviedate
1928
>>> girlfriend
'minnie mouse'

For tuple assignment to work correctly there must be the same number of
variables on the left hand side of the assignment operator as the number of
values on the right hand side.

5.3.3 Using tuples as return values

Since functions can only return a single value, tuples are useful structures if a
function needs to return more than one value. This is done by combining all the
values that need to be returned into a single tuple, which then becomes the
single return value.

For example, for a function countsum() that counts and sums the numbers in a
list, we would want the function to return both the count and sum values. This
can be done most conveniently using a tuple as the return value.

def countsum(mylist) :
count = 0
total = 0
for i in mylist :
count += 1
total += i
return (count, total)

(mycount, mytotal) = countsum([1,2,3,4,5,6,7])

print(mycount) # should print 7
print(mytotal) # should print 28

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
113
5.3.4 Composing data structures

Whilst it is intuitive that lists, tuples and pairs can contain items of the basic
types, namely int, float and bool, items in these data structures could also
be other data structures. For example, we could have a list where one of the
items in the list is a tuple, or even another list. Likewise, we could have a tuple
that has as one of its items another tuple, or even a list. We refer to the former
case as having nested tuples, i.e., a tuple item nested inside a tuple data
structure.

In this way we can compose fairly complex data structures to satisfy the data
storage requirements of the problem solution.

5.4 MANIPULATING LISTS

Prescribed reading
Read Chapter 11, “Lists” in the prescribed text by Wentworth et al. (2012), How
to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

We have already learnt about and made use of simple lists, which are data
structures that contain a collection of items or elements in some order. In fact
lists are very similar to strings in that these are both sequences of some element
type. However, they differ in that strings can only contain characters, whereas
a list can contain elements of any type. However, much of the discussion on the
manipulation of lists in this section reinforces what you already know about
strings.

5.4.1 Creating and accessing list elements

Lists are created by enclosing the list elements in square brackets. You can even
create an empty list that has no elements. Remember that lists can have multiple
elements, which can be of different types, including compound types like other
lists or tuples. Thus, all of the lists given below are valid lists:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
114
# list of 10 integers
primes = [1,2,3,5,7,11,13,17,23,29]
# list of 4 strings
disneycharacters = ["Mickey", "Donald", "Minnie", "Goofy"]
# list with zero elements
emptylist = []
# list of 3 elements of different types
confused = [13, "unlucky", False]
# list of 2 elements of type list
listoflists = [ [1,3,5,7,9], [0,2,4,6,8] ]

Accessing an element in a list is done using the index operator [], as is the case
with strings. Do not confuse this operator with the notation for an empty list;
their uses are, however, quite distinct.

The following examples show valid accesses of single list elements and using a
for loop of all the list elements:

for i in disneycharacters :
print(i) # prints each item in the list
print(primes[3]) # prints 4th item -> integer 5
print(listoflists[1]) # prints 2nd item -> list of even numbers

If you try to access an element in a list that does not exist, an out of range error
will occur:

>>> print(listoflists[2])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: list index out of range

One difference between strings and lists is that unlike strings, lists are mutable,
i.e., the elements can be changed at any time. Thus, to change an item in a list
we use the index operator to identify which item to change, and we then assign
the new value to this item:

disneycharacters[0] = "Sebastian"

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
115
By printing the list disneycharacters we would see the change:
['Sebastian', 'Donald', 'Minnie', 'Goofy']

5.4.2 Operations on lists

Membership of items in a list is found using the in and not in operators exactly
as is the case for strings:

>>> "Minnie" in disneycharacters

True
>>> "Minnie" not in disneycharacters
False

Similarly, the built-in function len() can be used with lists to give the number
of items in the list. Thus,
len(listoflists) # length of listoflists
returns 2, while
len(listoflists[0]) # length of first item in listoflists
returns 5.

The length function can also be helpful when iterating (or traversing) through a
list using a while loop:

j = 0
while j < len(disneycharacters) :
print(disneycharacters[j]) # prints each item in the list
j += 1

Using the + and * operators with list operands allows us to concatenate and
duplicate lists. Some examples are given below:

>>> veryconfused = confused * 3 # creates list with 3 copies

>>> print(veryconfused)
[13, 'unlucky', False, 13, 'unlucky', False, 13, 'unlucky', False]
>>> interesting = primes + disneycharacters # concatenates lists
>>> print(interesting)
[1, 2, 3, 5, 7, 11, 13, 17, 23, 29, 'Mickey', 'Donald', 'Minnie',
'Goofy']

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
116
We can also slice up lists in much the same way as when dealing with strings,
i.e., using the index operator with a range specified.

shortprimes = primes[5 : ]
print(shortprimes) # prints [11,13,17,23,29]
femaledisney = disneycharacters[2:3]
print(femaledisney) # prints ['Minnie']
badluck = confused[ : 1]
print(badluck) # prints [13]

We can even use ranges to update parts of a list with a new assignment, like:

confused[1:3] = ["nutty", True]

print(confused) # prints [13, 'nutty', True]

Note that this assignment to change parts of the data structure is not possible
with strings, as strings are immutable objects, whereas lists are not.

Lastly, we can use the del (delete) statement to delete items from a list. Note
that whilst this can also be done using slicing and reassignment, the del
statement may be easier to use. Some examples are given below:

del confused[1]
print (confused) # prints [13, True]
del primes[5: ]
print (primes) # prints [1, 2, 3, 5, 7]

5.4.3 Storing data structures in memory

All data variables are stored in memory when the associated Python code is being
executed. However, the way mutable and immutable data structures are stored
differs.

To save memory, immutable objects with the same value are never duplicated
in memory. For example, we can create two string objects, str1 and str2, and
assign the same string to each:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
117
 str1 = "hello"
str2 = "hello"

The Python memory allocation system is clever enough to realise that these
strings are the same and therefore, does not store two versions of the string in
memory, but only one. So effectively str1 and str2 are referring to the same
storage in memory. We can confirm this by using the is operator, which tests
whether its two operands are exactly the same. Note that by exactly the same,
we mean the exact same version of the object in memory and not just having
the same value but with different versions thereof in memory. The == operator
tests only whether the value of two variables is the same and not whether the
two variables use the same storage.

If we were to draw how str1 and str2 are stored in memory, it might look
something like what is depicted in Figure 5.1.

memory

str1
hello
str2

Figure 5.1: Memory usage for two strings with the same sequence of characters

On the other hand, since lists are mutable objects, each list data structure is
stored separately in memory, even if the elements of two lists are exactly the
same.

The memory allocated for the two lists, list1 and list2, created as:

list1 = [1,2,3,4]
list2 = [1,2,3,4]

is depicted in Figure 5.2.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
118
 memory

list1 [1,2,3,4]

list2 [1,2,3,4]

Figure 5.2: Memory usage for two lists with the same elements

We can confirm that the two lists occupy separate memory spaces by executing:
list1 is list2
which returns False. Note however, that
list1 == list2
returns True as this is testing the equality of the elements only.

Why the difference in memory allocation? The reason lies entirely with the fact
that strings are immutable, and thus once they are assigned they cannot be
changed, whereas lists can be changed after assignment.

After executing code like:

list1[:2] = [3,4]
the contents of memory would change to what is depicted in Figure 5.3. Because
each list has its own storage, only the elements in list1 change, while list2
remains as it was.

memory

list1 [3,4,3,4]

list2 [1,2,3,4]

Figure 5.3: Memory after changing the elements in list1 only

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
119
However, if we were to assign list1 to list2,
list2 = list1
we would lose access to the old contents of list2 and memory would change as
shown in Figure 5.4. Executing
list1 is list2
would now return True as both list1 and list2 refer to the exact same
memory space.

memory

list1 [3,4,3,4]

list2

Figure 5.4: Memory after executing list2 = list1

We refer to list1 and list2 as being aliased, i.e., the same memory space
being referred to by two different names. Any changes made using either list1
or list2 will affect the same memory space and thus change the contents of
both list1 and list2 in the same way.

list1[0] = 10
print(list1) # prints [10, 4, 3, 4]
print(list2) # prints [10, 4, 3, 4]
list2[3] = 20
print(list1) # prints [10, 4, 3, 20]
print(list2) # prints [10, 4, 3, 20]

If this is not the behaviour you wanted, instead of assigning list1 to list2
using the assignment operator =, we could have copied the contents of list1 to
list2 using a technique called cloning. This can be done by executing
list2 = list1[:]
with the changes in memory storage as shown in Figure 5.5.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
120
 memory

list1 [10,4,3,20]

list2 [10,4,3,20]

Figure 5.5: Memory after cloning list1 and calling it list2

Now that list1 and list2 refer to separate memory storage, changes made to
one of these lists are not visible in the other list. Executing the following code:

list2[0] = 15
list1[3] = 50
print(list1) # prints [10, 4, 3, 50]
print(list2) # prints [15, 4, 3, 20]

results in the changes to memory as shown in Figure 5.6.

memory

list1 [10,4,3,50]

list2 [15,4,3,20]

Figure 5.6: Memory after changes made to cloned lists

Understanding how data are stored in memory is one of the skills that good
programmers should have, as it translates directly into more efficient use of the
available memory. Although modern computers mostly have sufficient memory
for most computational solutions, working with limited memory occurs frequently
when programming robots.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
121
5.4.4 Traversing lists

We have already seen how to traverse a list using a for loop, using code similar
to the following:

names = ["Joe","Zoe","Brad","Angelina","Zuki"]
for f in names :
invite = "Hi " + f + ". Please come to my party!"
print(invite)

However, sometimes, we do not only want access to the values of items in the
list, but also their positions or indices in the list. If we needed to print a human
readable list of the party invitees, such as:
0 Joe
1 Zoe
2 Brad
3 Angelina
4 Zuki

we would need to write code something like:

names = ["Joe","Zoe","Brad","Angelina","Zuki"]
index = 0
for f in names :
print(index, f)
index += 1

Since accessing both the values of the items in the list and their positions is
something that is quite common, Python provides a simpler way to do this using
enumerate, which produces (index, value) pairs in the list traversal:

for (index, f) in enumerate(names) :

print(index, f)

Activity
As lists intended for human use normally start at 1 and not 0, change the code
above to produce a list for human use, such as:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
122
1 Joe
2 Zoe
3 Brad
4 Angelina
5 Zuki

5.4.5 Lists passed as arguments

Normally when we pass a variable as an argument to a function, a copy of the

variable is made and this copy is used within the function. This is commonly
referred to as pass-by-value, as changes made to this copy are not seen outside
the function. This is shown clearly by executing the following code, where we
are passing a copy of n to the function and any changes to n made within the
function do not affect the original value of variable n outside the function.

def fact(n) : # copy of n is used in this function

fact = 1
while n > 1 :
fact *= n
n -= 1
return fact

n = 5
result = fact(n)
print("Factorial of ", n, "is ", result)

The output of this code is:

Factorial of 5 is 120

Pass-by-value parameter passing is not, however, used when we pass a list as

an argument to a function. No copy of the list is made, and instead only a
reference to the list is available within the function. This reference is similar to
the aliased list variables we discussed earlier. This means that any changes made
to the list parameter inside the function, will be visible in the contents of the list
variable used as the argument. This method of passing parameters is referred to
as pass-by-reference.

The code below shows clearly what happens when passing a list as an argument.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
123
def changelist(alist) :
alist[4] = 20
del alist[0]
alist[1] = 10
return

mylist = [1,2,3,4,5]
print(mylist) # prints [1, 2, 3, 4, 5]
changelist(mylist)
print(mylist) # prints [2, 10, 4, 20]

Figure 5.7 helps understand how this works by depicting what memory looks like
when executing the call to changelist() and passing mylist as an argument
to this function.

memory

mylist [1,2,3,4,5]

alist

Figure 5.7: Memory when calling a function with a list passed as an argument

From this figure, it is obvious that any changes made using the parameter alist
will also affect the original mylist variable. Figure 5.8 shows the effect on the
contents of the list after executing the body of changelist().

memory

mylist [2,10,4,20]

alist

Figure 5.8: Memory after executing the body of changelist() but before returning

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
124
The behaviour that results from passing lists by reference can be dangerous and
might cause unexpected results if the programmer is not aware of this. We refer
to the changes that result from this behaviour as side-effects and functions that
include such behaviour as modifiers.

We could do away with any possibility of side-effects by creating pure functions,

i.e., functions that do not make changes to lists passed as parameters, but
explicitly make copies of such lists for manipulation within the function body.

The function nochangelist() given below is an example of a pure function,

where a new list is created within the function and subsequently modified.

def nochangelist(alist) :
newlist = alist[:]
newlist[4] = 20
del newlist[0]
newlist[1] = 10
return newlist

mylist = [1,2,3,4,5]
print(mylist) # prints [1, 2, 3, 4, 5]
newlist = nochangelist(mylist)
print(mylist) # prints [1, 2, 3, 4, 5]
print(newlist) # prints [2, 10, 4, 20]

5.4.6 Methods for use with lists

As we saw when discussing strings, there are many built-in methods that can be
used with lists. For a full report on these please refer to the Python
documentation at [Link]
Some examples of code using these methods are given below:

primes = [1,2,3,5,7,11,13,17,23,29]
emptylist = []

[Link](0, "first")
print(emptylist) # prints ['first']
[Link]("last")
print(emptylist) # prints ['first', 'last']
[Link](1, "second")
print(emptylist) # prints ['first', 'second', 'last']
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
125
[Link]()
print(emptylist) # prints ['last', 'second', 'first']
print([Link](11)) # prints 1
[Link]([31, 37, 41, 43, 47])
print(primes) # prints [1, 2, 3, 5, 7, 11, 13, 17,
23, 29, 31, 37, 41, 43, 47]

5.4.7 String methods that create/use lists

We have already seen how to split a string into smaller substrings depending on
a given separation character (called a delimiter). When dividing a string into
words, we normally use a space character as the delimiter. However, when using
the split method we can specify any delimiting character. The result of applying
the split method to a string is a list of substrings. For example, executing
"hello world again".split()
yields
['hello', 'world', 'again']

The opposite of the split method for strings is the join method. This method takes
a list of substrings as an argument and joins them together, where each substring
is separated by a given delimiter string. The delimiter (or glue) is specified as
the string that invokes the join method.

words = "hello world again".split()

print(words) # prints ['hello', 'world', 'again']
newstring = " ".join(words)
print(newstring) # prints hello world again
delimiter = "--"
otherstring = [Link](words)
print(otherstring) # prints hello--world--again

5.4.8 Nested lists

We have alluded to the fact that an item in a list can itself be another list. This
item is what we referred to as a nested list, i.e., a list included or nested within
another list. To access the elements of this nested list, we first need to access
the list item that is the nested list, and then the individual items within this
nested list. This can be done with code like:

mylist = [1, "three", [2, 4]] # list with 3 elements

elem2 = mylist[2]
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
126
print(elem2) # prints [2, 4]
nestedelem0 = elem2[0]
print(nestedelem0) # prints 2

Or we can combine the accesses to the two different lists’ elements by writing:

print(strangelist[0][2]) # prints 2

The ability to nest lists allows us to represent two dimensional structures such
as a matrix:
1 3 5 7 9
0 2 4 6 8

Code to access this matrix is shown below. In accessing the matrix rows, columns
and individual elements, we have used the shorthand method from above, where
the first index represents the row and the second represents the column.

listoflists = [ [1,3,5,7,9], [0,2,4,6,8] ] # matrix

row0 = listoflists[0]
print(row0) # prints [1, 3, 5, 7, 9]
row1 = listoflists[1]
print(row1) # prints [0, 2, 4, 6, 8]
col0 = [ listoflists[0][0], listoflists[1][0]]
print(col0) # prints [1, 0]
col3 = [ listoflists[0][3], listoflists[1][3]]
print(col3) # prints [7, 6]
row1col3 = listoflists[0][3]
print(row1col3) # prints 7
row0col4 = listoflists[1][4]
print(row0col4) # prints 8

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
127
5.5 MODULES

Prescribed reading
Read Chapter 12, “Modules” in the prescribed text by Wentworth et al. (2012),
How to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

Please disregard all mention of the clock() method discussed in Chapter 12.2.
This method is no longer available in the time module and has been replaced
with the time() method as discussed in Section 5.5.2 below.

We have previously discussed use of two modules from the Python Standard
library, namely turtles and strings. In this section we look at what else is
provided by this library in the way of modules (containing data definitions and
associated methods) that can be incorporated into our own Python code.

5.5.1 Module random

This module provides algorithms for generating pseudo-random numbers for a

variety of distributions. Pseudo-random number generators, also known as
deterministic random bit generators, are algorithms that produce sequences of
numbers that have properties that approximate those of sequences of random
numbers. These sequences cannot be considered to be truly random as they are
wholly determined by the initial value (called the seed) used to start the
sequence.

A full explanation of what is contained in this module is given in the Python

standard documentation found at:
[Link]

Given below is sample code using the random module:

import random

# code to generate a random number between 1 and 10

randomgen = [Link]() # create random generator
mynum = [Link](1,11) # excludes range upper bound
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
128
print(mynum)

#code to generate a random even number between 2 and 10

evengen = [Link]() # create new random generator
evennum = [Link](2,11,2) # 3rd parameter is increment
print(evennum)

#code to create a list of 20 random numbers between 1 and 100

randomlgen = [Link]() # create the random generator
mylist = [] # create empty list to populate
for i in range (20) :
newnum = [Link](1,101)
[Link](newnum)
print(mylist)

Some things to note in the code above:

 A call to Random() sets up the number generator using a random seed
value. Once created, this generator can be invoked by repeatedly calling
randrange() to output a pseudo-random number. Note that each time
you create a generator, a different seed value is used, which means that
the random sequence produced will differ.

 If you wish to recreate the same random sequence (possibly for debugging
purposes), you need to create the random generator using a known seed.
This can be done by providing a seed value, as follows:
mygenerator = [Link](567)

 Method randrange() takes as parameters, a lower bound, an upper

bound, and optionally an increment parameter to define the range of the
random numbers generated. This range includes the lower bound up to
but excluding the upper bound, in increments defaulting to 1 or as
specified by the third parameter if present.

Activity
Implement the code for removing duplicates in a list of random numbers given
in Section 12.1.2 of the Prescribed Reading for this section. Ensure you
understand how the list methods are being used in conjunction with the random
module methods to achieve the desired outcome.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
129
5.5.2 Module time

Creating efficient code (in terms of execution time) is something that good
programmers strive for. In order to measure how long a particular section of
code takes to execute, we can use the time() method from the time module.
A full explanation of what is contained in this module is given in the Python
standard documentation at: [Link]

This time() method gives the time elapsed since the last epoch, which is defined
to have started at 00:00:00 on the 1 January 1970. Using an epoch is a way for
computers to specify how much time has elapsed. Thus, by calling this method
once at the beginning of the code needing to be timed, and then again at the
end of the code, and subtracting the latter value from the former, we get the
time taken to execute the code in seconds.

You should, however, be aware that since modern day processors are very
powerful, for your execution timings to be meaningful, you will need to ensure
that the amount of work being timed is large enough. What this means is that if
you are manipulating a list structure for example, you should use a very large
list, with at least a million elements — possibly more if you are doing a very
simple operation on each element. However, always test your code first on a
small list to ensure it works as expected.

The code below creates a list of 5 million elements, shuffles this list (using a
method from the random module) to mix up the numbers, and then proceeds to
sort the list using a built-in sorting method for lists.

import time
import random

num = 5000000
mylist = list(range(num)) # setup list of num items
[Link](mylist) # shuffle list to be unsorted
start = [Link]()
[Link]()
end = [Link]()

print("Time to sort items = {0:.2f} seconds".format(end-start))

print(mylist) # print sorted list to check

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
130
5.5.3 Module math

This module contains useful mathematical constants (e.g., pi and e) and

functions, like sqrt(), sin(), sqr() and many more. Note that unlike some of
the other modules (notably turtle and random), this module contains only
functions and constant definitions. There are no methods that operate on objects
of any kind.

The code examples below show the use of these pure functions and constant
definitions:

import math
a = [Link](16) # square root
print("{0:.4f}".format([Link]))# pi to 4 decimals
[Link]([Link](90)) # calculate sine of 90-deg angle
print([Link](5)) # calculate factorial
print([Link](10.4)) # ceiling function

A full explanation of what is contained in this module is given in the Python

standard documentation found at:[Link]

5.5.4 Creating new modules and namespaces

Anyone can create a module; that is, any file containing Python code, say
[Link] can be imported into another code file using:
import myfunctions # note we omit the .py extension

Thereafter, any defined function or constant from [Link] can be used

as if those functions/constants were defined within the file containing the import
statement.

Given that anyone can write a module, should one be concerned that similar
function names might be used in different modules and this might cause
confusion if more than one module were imported into a file? To answer this,
consider the listings of the two files [Link] and [Link] containing
Python function and variable definitions:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
131
 Listing 5.1: File [Link]
# [Link]
def myfunc(alist) :
for val in alist :
print(val)

mylist = ["a","b","c","d","e"]

Listing 5.2: File [Link]

# [Link]
def myfunc(alist) :
sum = 0
for val in alist :
sum += val
print(sum)

mylist = [1,2,3,4,5]

If we were to execute the following code, what do you think might happen?

# [Link]
import mycode1
import mycode2
print(mylist)

In fact, executing print(mylist) gives an error:

Traceback (most recent call last):

File "C:\code\[Link]", line 4, in <module>
print(mylist)
NameError: name 'mylist' is not defined

The reason for this error relates to the concept of namespaces in Python. A
namespace in Python is a collection of all the identifiers that belong to a particular
module (i.e., code contained within a single file). So each module has its own
namespace, which prevents any conflicts from arising when similar identifiers are
used in multiple modules. Note that the simplified implementation of namespaces
in Python, does not necessarily extend to other programming languages, where
namespaces, modules and files may not have a one-to-one relationship.
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
132
When importing a module, one must refer to the identifiers within that module
by prefixing the namespace name (i.e., the module name) to the identifier using
the dot operator. This is referred to as the identifier’s fully qualified name. See
the code below for examples of what can be done:

# [Link]
import mycode1
import mycode2

print([Link]) # prints ['a', 'b', 'c', 'd', 'e']

print([Link]) # prints [1, 2, 3, 4, 5]
[Link]([Link]) # prints 15
[Link]([Link]) # prints a b c d e on separate
lines
[Link]([Link]) # prints 1 2 3 4 5 on separate
lines

Note that variables defined in a module are called attributes of the module. Thus
modules contain both attributes and functions and both of these are accessed by
means of the dot operator when imported into other files.

How a module is imported, determines how attributes and functions of that

module must be referred to in the file importing the module.

There are three versions of the import statement:

import math
which means that all identifiers in this module must be referred to using
their fully qualified name, e.g., [Link](10)
from math import cos, sin, sqrt
which means that the identifiers named in the import statement can be
used as is (i.e., without prefixing the module name), e.g., sqrt(10)
from math import *
which means that all identifiers defined in this module can be used as is,
e.g., sqrt(10 or factorial(5)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
133
Namespaces also apply to functions, in that variables declared and used inside
any function, are considered to belong to that function. Thus, even if a similar
named variable is used inside and outside a function, their values are distinct.
This is highlighted in the code below:

def doit () :
sum = 0
for i in range(5) :
sum += i
print(sum)

sum = 50
print(sum) # prints 50
doit() # prints 10 that is, sum of 1..5
print(sum) # prints 50

In the above code, the variable sum assigned to 50 outside the function is a
different variable to the sum used inside function doit().

This can be better explained using the concept of scope. The scope of an identifier
is that part of the code where the identifier can be accessed or used. Python has
three different scopes:
 Local scope, which governs all identifiers declared within a function. Each
function has its own namespace.
 Global scope, which governs all identifiers declared within the current
module (or file).
 Built-in scope, which governs all identifiers built into Python, i.e.,
functions (like len()) and methods (like string format()) that can be
used without importing anything.

Local scope (i.e., the innermost scope) has the highest precedence and built-in
scope the lowest. Thus, any identifier used within the body of a function is
assumed to belong to the function namespace, rather than to a global or built-in
scope. Thus, identifiers in the innermost scope can shadow (or hide) variables
from outer scopes.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
134
5.6 FILES

Prescribed reading
Read Chapter 13, “Files” (excluding Section 13.9 “Fetching data from the Web”)
in the prescribed text by Wentworth et al. (2012), How to Think Like a Computer
Scientist, 3rd edition, Runestone Academy. Available at:
[Link]

We have previously touched on the fact that all variables used in a program are
stored in memory (typically random access memory or RAM) while the program
is executing. However, once the program stops executing, anything stored in this
volatile memory is no longer available to the programmer. Thus, if the
programmer wishes to be able to access the variables after the program stops
executing, these data structures need to be stored on some form of non-volatile
storage. This storage is normally available in the form of files written to a hard
disk drive or flash drive, for example.

Likewise, sometimes the input required by a program is more conveniently input

via a data file created prior to the running of the program, rather than having
the programmer type it in each time the program runs.

This section looks at how files can be used to store both input and output data
for Python programs.

5.6.1 Writing to a file

Before using a file, it must be opened, and after using a file it must be closed.
This is the case both when writing to or reading from a file. However, how the
file is opened differs for file input and output.

To open a file for writing we first need to create a file handle, which is effectively
a connection to the physical file that we can use thereafter to access the file:
myoutfile = open("[Link]", "w")

Here, myoutfile is the file handle that acts as a logical connection to the actual
file "[Link]", which will be opened for writing as specified by the second
argument, "w". Note that in the case of writing, if the actual file does not already
exist, it will be created in the current directory; however, if it does exist, the
existing file will be replaced by the new file.
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
135
Writing to the file is done by calling the write method for files:
[Link]("I can write to a Python file\n")
[Link]("I can write as much as I want!\n")

When we are done writing to the file, we close it:

[Link]()

Now the file can be opened in a normal editor and we should find the following
content:

I can write to a Python file

I can write as much as I want!

5.6.2 Reading from a file

Reading from a file can be done one line at a time, or the entire contents of the
file all at once.

Opening a file for input purposes, and reading the contents line-by-line can be
done using the following code:

myinfile = open("[Link]", "r")

while True :
nextline = [Link]()
if nextline == "" :
break
print(nextline, end="")
[Link]()

Things to note about this code:

 Using "r" as the second argument to the file open() method opens the
file for input purposes. The physical file must therefore, exist in the current
directory prior to attempting to read from it. If you try to open a file that
does not exist (or does not exist in the current directory), you will get an
error message, like:

Traceback (most recent call last):

File "<stdin>", line 1, in <module>
FileNotFoundError: [Errno 2] No such file or directory:
'[Link]'

 If you want to read from an input file that does not exist in the current
directory, you will need to include the full directory path together with the
filename:
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
136
 origfile = open("D:\\code\\[Link]", "r")

Note the use of the "\\" which is necessary as the backslash character has
special meaning in strings as an escape character. Thus, to include a single
backslash in a string, we need to use "\\". Compare the use of "\n" to
represent a newline character in a string.

 To read all the lines in a file, we use an infinite loop, which is terminated
once we find out that there are no more lines to read. In Python, the only
way to ascertain that there is nothing more to read, is by actually trying
to read something. If we have reached the end of the file contents, the
readline() method returns an empty string, "".

 As the default print() function always adds a newline after printing the
data given as the argument, we need to suppress this newline, as the
readline() method reads everything in each line of input including any
newline characters.

If we wanted to do more with our input data than just read a line and print it, it
is convenient to read in all the lines at once, and store these in a list that can
then be processed according to the programmer’s needs. The readlines()
method can be used instead of readline() to do this:

myinfile2 = open("[Link]", "r")

allines = [Link]()
for l in allines :
# do something here with each line OR
print(l) # just to show that each line does exist
[Link]()

This produces the output (note the extra blank lines as we have not prevented
print() from outputting a newline character):

I can write to a Python file

I can write as much as I want!

What has been done above, is effectively turning the input file into a list of lines,
each represented as a string.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
137
Alternatively we can read in the entire file and store it as a single string data
structure. Once this has been done, the string methods can be used to process
the data read in.

myinfile3 = open("[Link]")
completestr = [Link]()

[Link]()
print(completestr)
listofwords = [Link]()
print(listofwords)

Note that if no second argument is given to the open() method, reading mode
("r") is assumed. Executing this code produces the following output:

I can write to a Python file

I can write as much as I want!

['I', 'can', 'write', 'to', 'a', 'Python', 'file', 'I', 'can',

'write', 'as', 'much', 'as', 'I', 'want!']

5.6.3 Binary files

Thus far in this section we have only dealt with reading and writing text files,
which are files that are arranged around lines of ASCII characters, with each line
ending with a newline character (“\n”). The contents of binary files on the other
hand, are stored in binary format (zeroes and ones), i.e., in the same way that
data are stored in RAM for processing. Binary files can contain images, videos or
sound recordings, amongst others, and when opened in a text editor, for
example, do not contain human readable information.

However, the Python code to read and write binary files is very similar to what
has been discussed for reading and writing text files and can be done with the
open(), read() and write() methods with some small changes to the
arguments. The code below copies a binary image file (stored as a .jpg) to a
new jpg file:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
138
#binary file copy
origfile = open("[Link]", "rb") # opening files
newfile = open("[Link]", "wb")

x = [Link]() # reading from file

[Link](x) # writing to new file

[Link]() #closing files

[Link]()

Note that in this example, the type of buf is bytes, which is a data object that
we do not cover in this module. You are welcome to read more about this type
at:
[Link]

5.7 LIST ALGORITHMS

Prescribed reading
Read Chapter 14, “List Algorithms” in the prescribed text by Wentworth et al.
(2012), How to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

Searching through data to find a particular word or other pattern, and sorting
data in some order are two tasks that frequently need to be performed in
computer programs. In this section we discuss some useful searching and sorting
algorithms that can be applied to list data structures.

5.7.1 Linear search

This is a basic search algorithm that mimics the way humans might search a
sequence of data to find a particular element. The algorithm is also known as a
sequential search, as searching starts at the first element in the data structure
and continues until the element is found or the end of the data structure is
reached, which means that the element was not present in the list.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
139
A Python function to perform a linear search on a list of elements is given below:

def linearSearch(alist, elem):

# searches alist for element elem
# returns index of element if found
# else returns -1

for i in range(len(alist)):

if (alist[i] == elem):
return i
return -1

mylist = [1, 8, 2, 6, 4, 5, 3, 9, 7]
tofind = 7
found = linearSearch(mylist, tofind)

if(found == -1):
print("Element not found in list")
else:
print("Element found at index", found)

5.7.2 Binary search

A much more efficient algorithm for searching a list is a binary search. However,
unlike the linear search, this algorithm requires that the list is in some sorted
order.

With a sorted list, the binary search algorithm looks at the middle element and
then depending on whether this element is greater or larger than the element
being sought, searching continues in either the top or bottom sections of the list.
So effectively, after each unsuccessful comparison (i.e., one that does not result
in finding the sought after element), the size of the remaining search area is cut
in half.

Iterative code to achieve this is given below:

def binarySearch(alist, elem):

# searches alist for element elem
# returns index of element if found
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
140
# else returns -1

start = 0
end = len(alist)-1
while start <= end :
mid = (end-start)//2 + start
if alist[mid] == elem :
return mid

else :
if alist[mid] > elem :
end = mid - 1
else :
start = mid + 1
return -1

mylist = [1, 2, 3, 4, 6, 7, 8, 9, 10]

tofind = 5

found = binarySearch(mylist, tofind)

if(found == -1):
print("Element not found in list")
else:
print("Element found at index", found)

There is also an efficient recursive algorithm for binary search that is covered in
the next topic.

5.7.3 Removing duplicate elements

When solving certain problems, we might need to work with a data structure that
contains unique elements, i.e., no duplicates. Thus, an algorithm to remove
duplicates would be useful.

There are multiple ways to write such an algorithm, but the simplest method
would be to first sort the data structure and then create an algorithm that
removes adjacent duplicate elements. This is the approach we follow in the code
below:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
141
def remDuplicate(alist):
# removes all adjacent duplicates
# first sorts the list and then creates
# new list without duplicates
newlist = []
[Link]() # note this changes mylist outside the function
size = len(alist)
if size == 0 :

return newlist
previous = alist[0]
[Link](alist[0])
for i in range(1, size):
if (alist[i] != previous):
[Link](alist[i])
previous = alist[i]
return newlist

mylist = [1, 8, 6, 1, 3, 3, 2, 6, 4, 5, 3, 9, 7]
print(mylist)
uniquelist = remDuplicate(mylist)
print(mylist)
print(uniquelist)

The output from the code above would be:

[1, 8, 6, 1, 3, 3, 2, 6, 4, 5, 3, 9, 7]
[1, 1, 2, 3, 3, 3, 4, 5, 6, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Activity
Make sure you understand why the contents of mylist is different before and
after the call to remDuplicates().

Of course this side-effect behaviour can be prevented as explained earlier in this

section. Give the code to show how this can be done. Test your code by checking
that mylist does not change before and after the calls to remDuplicates().

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
142
5.7.4 Bubble sorting

Besides searching for various elements, sorting is another task that is often
needed in programs. We have already seen in the binary search that for this
search method to be applicable, the list being searched must be in a sorted order.

There are many different algorithms for sorting various data structures. In this
section we cover one of the simplest algorithms for sorting a list of elements of
the same type. This algorithm is called the bubble sort as this reflects the way
that larger elements (when performing a sort in ascending order) bubble to the
end of the list.

The algorithm involves a pair of nested loops, where the inner loop compares all
adjacent pairs of elements, and if they are in the incorrect order, swaps them
around.

The outer loop iterates at least n-1 times (where n is the number of elements in
the list), but can stop earlier, if no changes are made in a single iteration, as this
implies that the list is already sorted.

The naïve code for this algorithm is given as Listing 5.3. This code completes the
full n-1 iterations for the outer loop, irrespective whether the list is completely
sorted earlier.

Listing 5.3: Naïve algorithm for bubblesort

def bubsort(alist):
iter = len(alist)-1 # max number of iterations

for i in range(iter):
for j in range(iter):
if alist[j] > alist[j+1]: # swap adjacent elements
temp = alist[j]
alist[j] = alist[j+1]
alist[j+1] = temp
return

mylist = [1,4,2,6,8,0,3]
bubsort(mylist)
print(mylist) # prints [0, 1, 2, 3, 4, 6, 8]

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
143
The naïve algorithm is very inefficient as it always performs the maximum
number of iterations, even if the list provided is already sorted. A simple
improvement can be made to exit the outer loop if no swaps are made to the
elements in any iteration of the outer loop. Listing 5.4 shows the improved
bubblesort algorithm.

Listing 5.4: Efficient bubblesort without unnecessary loop iterations

def ebubsort(alist):
iter = len(alist)-1 # covers max number of iterations

for i in range(iter):
nochanges = True # assume list is sorted
for j in range(iter):
if alist[j] > alist[j+1]: # swap adjacent elements
temp = alist[j]
alist[j] = alist[j+1]
alist[j+1] = temp
nochanges = False # confirm changes made
if nochanges == True : # if no changes, exit
break
return

5.7.5 Merge sorting

The merge sort algorithm works with two sorted lists, which it interleaves (or
merges) to produce one sorted list.

To understand how this algorithms works, assume you have two queues of
people, where each queue is in sorted order according to the person’s height,
with the shortest person in each queue at the front, and the largest at the back.
Now merging these queues into a single sorted queue is easily done, by
comparing the people at the front of each queue and removing the shortest of
the two from his/her queue and placing them in a third queue, which will become
the final sorted queue. The process repeats by continually comparing the two
people at the head of each of their respective queues, and moving the shortest
of the two to the sorted queue.

When one queue becomes empty, all the remaining people in the other queue
can be added to the back of the final sorted queue.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
144
Code to do this is given as Listing 5.5.

Listing 5.5: Mergesort that merges two sorted lists and returns the new sorted list

def mergesort(alist, blist):

inda = 0 # index into alist

indb = 0 # index into blist
lena = len(alist) # length of alist
lenb = len(blist) # length of blist
sortlist = [] # create new sorted list

while inda < lena and indb < lenb: # elements in both lists
if alist[inda] <= blist[indb]:
[Link](alist[inda])
inda += 1
else:
[Link](blist[indb])
indb += 1

# Copy remaining elements from one of the lists

while inda < lena:
[Link](alist[inda])
inda += 1

while indb < lenb:

[Link](blist[indb])
indb += 1

return sortlist

list1 = [0, 1,3,5,7,9]

list2 = [0,2,4,6,8,10]
print(mergesort(list1,list2))

Activity
To see how some of these algorithms can be combined in the solution of a real
problem, read Sections 14.8 and 14.9 of the Prescribed Reading for this section.
These sections explain how to solve a well-known computing problem known as
the 8-Queens puzzle. Implement the code and ensure that the solutions
generated do actually solve the problem.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
145
 Summary

A great deal of programming content was covered in this topic. The first part of
the topic introduced useful data structures, while the latter sections shed more
light on the built-in modules provided with the Python system, the ability to use
non-volatile storage for input and output in executing programs, and useful
searching and sorting algorithms.

String data structures are immutable and thus cannot be changed once they have
been created. However, new strings can be created from old ones using the
available methods provided. There are also methods to access various parts of a
string, traverse a string, and compare strings. Example code was provided to
show how some of these tasks can be done.

Creation and manipulation of tuples was covered in detail, as well as showing

how tuples can be used to allow functions to return more than one value. Next,
the list data structure was introduced and shown to be very flexible in terms of
types of elements contained within the list and also the methods provided for
manipulation thereof. Unlike strings, lists are mutable such that the elements
can freely be changed.

The random, math and time built-in modules were explored by providing
example code to use aspects of each. Thereafter, file input and output was
introduced and code to implement reading from and writing to text files during
the execution of a Python program was explained.

The topic concluded with explanations of simple searching and sorting algorithms
for list data structures, together with simple code to implement each of the
algorithms discussed.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
146
 Self-Assessment Questions

1. Write a function that takes a list parameter and returns the reversed list. You
should not make use of any additional list storage whilst processing the list
(i.e., make changes directly to the original list). You should also not use any
pre-defined reverse methods available.

2. Write Python code to mimic a coin toss. (Hint: you may wish to make use of
the random module.)
Your program should “execute” 100 coin tosses and count how many of these
landed on “heads” and how many on “tails”. Output from the code should look
something like this:

100 coin tosses executed

Number of heads = 51
Number of tails = 49

3. Write Python code to read in binary numbers from a prepared text file, and
convert these to decimal (i.e., base 10) numbers. Your code should print the
original binary number as well as its conversion to an output text file as well.
For example, if you read in the number 10011 – the output should be 19.

4. Change the code for both the naïve bubblesort and the more efficient
bubblesort algorithms as given in Listings 5.3. and 5.4 to calculate how many
comparisons of elements (i.e., how many times the inner loop is executed),
as well as how many swaps of elements are done when sorting a list.

Now sort the following lists using each of the algorithms and record the
number of comparisons and swaps done in each case:

list1 = [1,2,3,4,5,6,7,8]
list2 = [8,7,6,5,4,3,2,1]
list3 = [1,4,2,6,8,7,3,5]
list4 = [1,8,2,7,4,5,3,6]

Comment on what type of input represents the best and worst cases for each
of the algorithms.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
147
5. Consider the following code for a swap function:

def swap(x, y): # does this work??

print("before swapping: x:", x, "y:", y)
(x, y) = (y, x)
print("after swapping: x:", x, "y:", y)

Does this code work in a way that you would expect it to? Test it as follows:

alist = [1,2,3,4,5]
blist = ["is","it","ok"]

print("before calling function: alist:", alist, "blist:",

blist)
swap(alist, blist)
print("after calling function: alist:", alist, "blist:",
blist)

Explain why the code does what it does. Hint: it has to do with how the lists
are stored in memory.

6. Attempt some of the exercises given at the end of Chapters 8, 9 and 11—14
of the prescribed text by Wentworth et al. (2012), How to Think Like a
Computer Scientist, 3rd edition, Runestone Academy.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
148
 Topic 6
Recursion and other advanced concepts

6.1 INTRODUCTION

This topic relates to the following module outcomes:

1. Apply problem solving and programming skills to design solutions to non-

trivial problems.
4. Design efficient Python solutions to simple mathematical and logic
problems.
5. Execute, debug and create simple test procedures for Python programs.

On completion of this slightly more advanced topic, you will understand the
concept of recursion, which can simplify the coding of solutions to certain types
of complex problems, be able to deal with potential exceptions arising in your
code in a managed way, and define and make use of dictionaries as a data
structure to handle paired data. All of these concepts are useful tools for solving
more complex problems, and can in some cases, make a seemingly unsolvable
problem, doable. Thus, whilst your current knowledge of Python programming
might seem sufficient for most problems that you have come across up until this
point, the use of recursion, exception handling and a new data structure covered
in this topic should not be discounted.

In this topic, you will gain knowledge in the following areas:

1. Recursion
2. Exception handling
3. Dictionaries as a compound data structure

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
149
The following assessment criteria for sub-topics relate to module outcomes 1, 4
and 5:
 Python programming: Explain how recursion works and show how
iterative program solutions can be rewritten as recursive ones.
Understand the requirements of a recursive solution.
 Python programming: Explain the benefits of exception handling and why
this should be included in your program solutions.
 Data structures: Explain the features and functionality of the dictionary
data structure and show how variables of this type can be used in solving
more complex problems, and/or writing more efficient code.

6.2 RECURSION

Prescribed reading
Read Chapter 18, “Recursion” in the prescribed text by Wentworth et al. (2012),
How to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

In mathematics, recursion means “defining a problem in terms of itself” and there

are many examples of this, for example, elements in the Fibonacci sequence:
F(n) = F(n-1) + F(n-2), where F(0) = 1; F(1) = 1

To ensure that a recursive definition is finite and hence possible to enumerate,

there must always be a simple case that does not involve recursion (i.e., we stop
the definition in terms of itself for certain input values). In the Fibonacci
sequence, this happens for the first two elements, F(0) and F(1).

To understand this concept in terms of mathematical definitions for now, let us

consider the mathematical evaluation of F(4) (i.e., calculate the first 5 elements
in the Fibonacci sequence):

F(4) = F(3) + F(2); # can’t evaluate – need values for F(3), F(2)
F(3) = F(2) + F(1); # can’t evaluate – need value for F(2), F(1)=1
F(2) = F(1) + F(0); # evaluates to 1 + 1

Thus, F(2) = 2, so we can now evaluate

F(3) = 2 + 1 = 3
and F(4) = 3 + 2 = 5
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
150
Thus, the first 5 elements are given as:
1, 1, 2, 3, 5
Thus, by postponing the evaluation of certain elements in this sequence, we can
finally reach a point where the evaluation of an element can happen (i.e., we
reach the simple cases, also called the base cases), and then we can return to
previous unevaluated elements and finalise these.

6.2.1 Recursive functions

Having seen that mathematical functions (notably the Fibonacci function) can be
defined in terms of recursive calls to themselves, we now look at how such
functions can be defined in Python code.

Since the general Fibonacci function contains two recursive calls, we will start by
looking at a simpler recursive function, one that calculates factorials in a
recursive way. But first we revisit the iterative code to calculate factorials
presented earlier:

def factorial (n) :

product = 1
for j in range(n) :
product = product * (j+1)
return product

print(factorial(3)) # prints 6

Writing a recursive function is done in the following way:

1. Create at least one base case that does not involve a recursive call and
can thus terminate the recursive calls.
2. Write the body of the function that includes calling the function
recursively.
Following this template, consider the code for a recursive fact() function:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
151
def fact (n) :
if n < 0 :
return
if n <= 1 :
return 1
thefact = n * fact(n-1)
return thefact

print(fact(3)) # prints 6

Similar to the analysis we did of the generation of the Fibonacci sequence in

Section 6.2, we now look at what calls are being made when we execute
fact(3).

From the above, we can see that at every recursive call (following the blue
arrows), we are breaking down the problem into a simpler problem, until it is so
simple that we can calculate the answer immediately, i.e., we know that the
factorial of 1 is 1. Once we have the answer to the simplest version of the
problem, we can return to the line of code where the recursive call was made
(i.e., following the red arrows), and fill in the returned value. By successively
returning to each of the recursive calls in reverse order, the problem is eventually
solved when the value from the first call to the recursive function is returned.

Making recursive calls is very much like passing-the-buck and trusting that by
making the problem simpler at each successive call, the problem will eventually
be solved.
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
152
 Activity
Read Section 18.1 in the Prescribed Reading for this section. Ensure you
understand how fractals, which have a self-similar structure, are drawn
manually. Now implement the code for drawing simple fractals to see how the
structure becomes more complex with increasing orders.

6.2.2 Recursive data structures

In an earlier topic, we referred to nested data structures where a particular data

structure, like a list or tuple, could have elements that were of the same type,
e.g., lists or tuples, respectively. These data structures are recursive in the sense
that if we wanted to traverse all the elements (even those within the nested
structures) we could make use of a recursive function to do so.

Assume that we have a list with elements being either integers, lists of integers
or even tuples containing int elements, e.g.,
recurlist = [ (1,2), 3, [4,5,6]]
and we want to print all the elements in this list. We define printL() to do this:

def printL (mylist) :

for elem in mylist :
if type(elem) == int : // found an int
print(elem)
else : // found complex type
printL(elem) // call function recursively
return

The function prints out an integer if one is found, else it calls itself recursively to
deal with any complex types found, i.e., lists or tuples. This function can deal
with any level of nesting, including having empty lists or tuples as elements,
which shows the power of recursion.

As a second example, we might want to count the number of elements in a nested

list, e.g.,
nestedlist = [[1,3,5], 7, [2,4,6,8], [10], 20, [[40,50]], 60]

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
153
The function countL() can do this for any level of nesting:

def countL (mylist) :

count = 0
for elem in mylist :
if type(elem) == int :
count += 1
else :
count += countL(elem)
return count

Note the base case where we increment the count if we find an element of type
int.

Activity
How would you change the code for countL() to be able to deal with elements
of other types, such as float, bool, str, and so on?
Hint: you might consider adding additional base cases.

6.2.3 Recursive Fibonacci sequence

Finally, let us consider the code to calculate the Fibonacci sequence using a
recursive function. For this function, our base cases will be the first 2 values in
the sequence, i.e., 1 and 1:

def fibo(n) :
# return the n'th Fibonacci number
if n < 0 :
return # sequence starts at zero'th number
else :
if n <= 1 :
return 1 # zero'th and 1st elements both 1
else :
return (fibo(n-1) + fibo(n-2))

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
154
 Activity
Consider how you could use fibo() to create a list containing the first m
Fibonacci numbers.
Hint: don’t overthink this – rather keep fibo() intact and write a new function.

6.3 EXCEPTION HANDLING

Prescribed reading
Read Chapter 19, “Exceptions” in the prescribed text by Wentworth et al. (2012),
How to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

Runtime errors are called exceptions, and when such an error occurs, the
program stops running and an exception object is created. By this stage you are
likely to have experienced such an error, which causes traceback information to
be printed to allow the programmer to find where the error occurred, together
with information about the error.

There are various reasons for runtime errors including, divide-by-zero attempts,
accessing elements in data structures that do not exist, i.e., indices that are out
of bounds, or trying to assign to an element in an immutable data structure, like
a string or tuple.

An example of the exception raised in the latter case is the following:

>>> mystring = "abcd"

>>> mystring[2] = "c"
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
155
6.3.1 Handling exceptions

To prevent the program terminating when an exception occurs, we can try to

handle the exception by creating some code that tells the Python runtime system
what to do if such an exception occurs.

The general syntax for exception handling code is as follows:

try :
do something i.e., normal code
except :
code to handle/report any problem that occurs

Note that you will need to use multiple except clauses if there is more than one
possible problem or error that could occur when running your program code.

Divide by zero is a common error in programming. If we do not provide code to

handle this error, our program will fail and give a ZeroDivisionError message
as shown below:

>>> a = 0
>>> b = 50
>>> c = b/a
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ZeroDivisionError: division by zero

If we include exception handling code, we get the following response:

>>> try:
... c = 50/(10-10)
... except ZeroDivisionError:
... print ("You cannot divide by zero")
...
You cannot divide by zero
>>>

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
156
Other common runtime errors are illustrated below in an example context and if
relevant, with code to handle the error:

1. NameError: denotes that you have used a local or global name that
has not yet been defined. We could write an exception handler for this,
but without having the correct value for this variable, there is normally
no reason to continue executing as the logic of the program is likely to
be compromised.

>>> answer = rubbish + 5

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

2. ValueError: occurs when an inappropriate value is provided for a

given type, and you have not used an IndexError specification to
handle this occurrence.

>>> while True:

... try:
... x = int(input("Please enter an integer: "))
... print (x)
... break
... except ValueError:
... print("You have not entered a valid integer - try
again")
...
Please enter an integer: 45.5
You have not entered a valid integer - try again
Please enter an integer: w23
You have not entered a valid integer - try again
Please enter an integer: 5
5

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
157
3. TypeError: occurs if you try to combine incorrect types in a statement
or expression.

>>> a = 5 + "six"
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'str'
>>>

4. IndexError: occurs if you use a sequence subscript that is out of

bounds.

>>> list = [1,2,3,4,5]

# trying to print a non-existent element in the list
>>> print (list[10])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: list index out of range

# handling the exception

>>> try:
... print(list[10])
... except IndexError:
... print("The index used is out of bounds!")
...
The index used is out of bounds!

5. RecursionError: is raised if you have incorrectly set up the

termination condition on some recursive code, and the system detects
that the number of recursive levels reached is too many for it to handle.

def mybadfunc(n): # bad recursive function to print n downto 1

print(n) # note no stop case
mybadfunc(n-1)

>>> mybadfunc(4) # this is not going to end well!

4
3
2
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
158
1
0
-1
-2
-3
… many more lines like this

-988
-989
-990
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 3, in mybadfunc
File "<stdin>", line 3, in mybadfunc
File "<stdin>", line 3, in mybadfunc
[Previous line repeated 992 more times]
File "<stdin>", line 2, in mybadfunc
RecursionError: maximum recursion depth exceeded while calling a
Python object
-991

# correct recursive function to print n downto 1

def myfunc(n):
if n < 1: # stop case
exit
else:
print(n)
myfunc(n-1)

>>> myfunc(4)
4
3
2
1

6.3.2 Raising exceptions

Programmers can make use of the in-built exceptions to make their programs
more robust. A simple example is to catch errors made when users input data
that does not conform to what is required.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
159
Assume our program requires a user to input integer data that is within a specific
range. We can enforce this by defining a special form of the ValueError and
then raising the exception when data not in the specified range is input as
illustrated in the code below:

# [Link] file
def getAnswer():
print("Please input an integer between 0 and 100:")
ans = int(input())
if (ans < 0) or (ans > 100):
# Create your variation of an exception
inputErr = ValueError("{0} is not a valid
input".format(ans))
raise inputErr
return ans

# testing getAnswer()

>>> getAnswer()
Please input an integer between 0 and 100:
333

Traceback (most recent call last):

File "<stdin>", line 1, in <module>
File "C:\[Link]", line 31, in getAnswer
raise inputErr
ValueError: 333 is not a valid input

Naturally, we could validate the input in the actual code itself, to ensure that it
is within the specified range:

def getAnswer2():
while (True):
print("Please input an integer between 0 and 100:")
ans = int(input())
if (ans < 0) or (ans > 100):
print("Answer not in the valid range. Try again!")
else:
Break
return ans
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
160
>>> getAnswer2()
Please input an integer between 0 and 100:
-1
Answer not in the valid range. Try again!
Please input an integer between 0 and 100:
333
Answer not in the valid range. Try again!
Please input an integer between 0 and 100:
45
45

Suggested reading
For a more comprehensive guide to exceptions and exception handling, read
Section 8.2 in Guido van Rossum’s, “Python Tutorial”. Available at:
[Link]

6.4 DICTIONARY DATA STRUCTURES

Prescribed reading
Read Chapter 20, “Dictionaries” in the prescribed text by Wentworth et al.
(2012), How to Think Like a Computer Scientist, 3rd edition, Runestone Academy.
Available at:
[Link]

Similar to lists and tuples, dictionaries are a compound data type that maps keys
to specific values to provide data structures that resemble “lookup tables”. In
the same way that a dictionary for a spoken language allows a user to look up a
word (the key part) to obtain its definition (the value part), so too can a Python
dictionary data type be constructed.

A key in a Python dictionary, which must be an immutable type, is mapped to its

associated value, which can be any type (as is the case for lists and tuples). The
dictionary thus contains any number of these key-value pairs.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
161
6.4.1 Creating a dictionary

An empty dictionary data structure is denoted by { }. We can then add key-

value pairs to the dictionary as follows (assume we are creating a dictionary,
called CityUniversities containing cities and their main university):

CityUniversities = {} # start with an empty dictionary

CityUniversities['Cape Town'] = 'UCT' # add key-value pair
CityUniversities['Belville'] = 'Stadio' # add more pairs
CityUniversities['Makhanda'] = 'Rhodes'
CityUniversities['Johannesburg'] = 'WITS'

>>> CityUniversities
{'Cape Town': 'UCT', 'Belville': 'Stadio', 'Makhanda': 'Rhodes',
'Johannesburg': 'WITS'}

Note that the key-value pairs in the dictionary are separated by commas. Within
the pair, the key and value are separated by a colon.

We can also create a dictionary by providing a list of key:value pairs:

CityUnis = {'Cape Town': 'UCT', 'Belville': 'Stadio',

'Makhanda': 'Rhodes', 'Johannesburg': 'WITS'}

>>> CityUnis
{'Cape Town': 'UCT', 'Belville': 'Stadio', 'Makhanda': 'Rhodes',
'Johannesburg': 'WITS'}

Some of you might be wondering why we need dictionaries at all given that it is
possible to associate values with “keys” using a list of tuples. For example:

Unis = [ ('Cape Town', 'UCT'), ('Belville', 'Stadio'),

('Makhanda', 'Rhodes'), ('Johannesburg', 'WITS')]

The main reason for including the dictionary data type, is that looking up values
in a dictionary is very fast because the dictionary lookup uses a technique called
hashing to locate the key and access its associated value.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
162
6.4.2 Accessing values

Accessing values in a dictionary is done by using the key, rather than an index,
since there is no order associated with the key-value pairs in a dictionary.

>>> print(CityUnis['Belville'])
Stadio
>>> print(CityUnis)
{'Cape Town': 'UCT', 'Belville': 'Stadio', 'Makhanda': 'Rhodes',
'Johannesburg': 'WITS'}

6.4.3 Dictionary operations and methods

We can obtain the length of a dictionary (i.e., the number of key-value pairs
contained in it) by using the len operation:
len (CityUnis) # this returns 4 in our example

We can also delete a key-value pair using the del operation:

del CityUnis['Belville']

The in and not in operators can be used to check whether a key exists or does
not exist within a dictionary, respectively:

'Makhanda'in CityUnis # returns True

'Durban' in CityUnis # returns True
'Durban' not in CityUnis # returns False

Methods are available to access all the keys or all the values in a dictionary,
namely keys() and values(). These methods enable us to iterate through a
dictionary using a for-loop or to print all the keys or values. Some examples are
given below:

>>>list([Link]())
['Cape Town', 'Makhanda', 'Johannesburg']

>>>for i in [Link]():
print(i)

Cape Town
Makhanda
Johannesburg

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
163
6.4.4 Aliasing versus copying dictionaries

Similar to what was discussed with respect to lists, we must be aware of the
difference between aliasing and copying a dictionary structure. Copying implies
making a new version of a dictionary data structure and for this we use the copy
method. When creating a copy, new memory is allocated for the copy of the
dictionary. On the other hand, if we assign an existing dictionary to a new
variable using the assignment operator, we are creating an alias of the existing
dictionary, i.e., we are just creating a new variable that refers to the same
memory as the original data dictionary.

Because dictionaries are mutable, if we make a change to the dictionary, all

aliased versions of the dictionary will also be changed. This is not the case if we
make a copy of the dictionary and then change aspects of the copy or the original
dictionary. The code given below illustrates this well:

>>> CityUnis = { 'Cape Town': 'UCT', 'Belville': 'Stadio',

'Makhanda': 'Rhodes', 'Johannesburg': 'WITS'}

>>> newCityUnis = [Link]() # create new copy

>>> aliasCityUnis = CityUnis # create alias to original

>>> print(newCityUnis)
{'Cape Town': 'UCT', 'Belville': 'Stadio', 'Makhanda': 'Rhodes',
'Johannesburg': 'WITS'}

>>> print(aliasCityUnis)
{'Cape Town': 'UCT', 'Belville': 'Stadio', 'Makhanda': 'Rhodes',
'Johannesburg': 'WITS'}

>>> del CityUnis['Cape Town'] # delete an element from original

>>> newCityUnis['Durban'] = 'UKZN' # add pair to copy

>>> print(newCityUnis) # contains new pair

{'Cape Town': 'UCT', 'Belville': 'Stadio', 'Makhanda': 'Rhodes',
'Johannesburg': 'WITS', 'Durban': 'UKZN'}

>>> print(aliasCityUnis) # element deleted here as well

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
164
{'Belville': 'Stadio', 'Makhanda': 'Rhodes', 'Johannesburg':
'WITS'}

Activity
Experiment further with aliasing versus copying to understand fully the difference
in the memory usage of each technique. As discussed in Section 5.4.3, it helps
to draw what each data structure would look like in memory.

Summary

This topic focussed on more advanced Python programming concepts, namely

recursion and runtime errors, as well as introducing an additional data structure,
the dictionary.

Recursion is a mathematical concept that allows a function to call itself. This is

useful in programming to implement repetition, but also in some cases to make
the programming of the iterative code easier. In the topic we looked at recursive
function calls, both for programming repetition and for traversing and
manipulating recursive data structures.

Exceptions are normally the result of runtime execution errors and cause the
executing program to terminate prematurely. By writing an exception handler,
the programmer can change this fatal termination behaviour.

Finally we introduced the dictionary data structure and showed how to create a
dictionary and access the data in the form of key-value pairs. One advantage of
using a dictionary instead of a list of key-value tuples is the fast access ability of
the dictionary due to using hashing to locate the key. Several examples of the
use of a dictionary were provided.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
165
 Self-Assessment Questions

1. Write a recursive function, reverse() that takes a string as a parameter and

prints out the string backwards. So if the argument is ‘BACKWARDS’, the
function prints out ‘SDRAWKCAB’. Ensure that you have suitable stop cases to
avoid a RecursionError exception.

2. Write a recursive function, printbinary() that takes an integer as a

parameter, and prints out the binary representation of the integer. First think
about how to convert an integer number (i.e., a base-10 decimal number like
6) into a base-2 binary number (i.e., 110). Then work out how to do this as a
recursive function.

3. Rewrite the code for getAnswer() given in Section 6.3.2 (file [Link])
to include both checking for valid integers (i.e., those between 0 and 100) as
well as handling a ValueError exception caused by the user providing input
that is not considered to be an integer at all. For example, typing in a floating
point number instead of an integer.

4. Writing coded messages has been ongoing for many centuries. Write a
program that allows you to code and decode messages written using a cypher
where each letter is replaced by another letter according to the code
conversion given in the table below:

Actual Coded Actual Coded

character character character character

a g n a
b h o b
c i p c
d j q d
e k r e
f s s f
g t t l
h u u m
i v v n
j w w o
k x x p
l y y q
m z z r

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
166
 You must use a dictionary (probably multiple dictionaries) to store the codes
for encoding and decoding. For example, the string, “dosomeworknow”
would be coded as “jbfbzkobexabo”.

5. Write a recursive function binaryfind() that searches for a given number

in a sorted list of numbers. The function takes two parameters, num, the
number to search for, and mylist, the list that needs to be searched. The
function should return the index in the list where the number was found. If
it was not found, -1 should be returned.

Hint: The function should make use of the binary search algorithm.

6. Attempt some of the exercises given at the end of Chapters 18, 19 and 20 of
the prescribed text by Wentworth et al. (2012), How to Think Like a Computer
Scientist, 3rd edition, Runestone Academy.

Glossary of terms

Aliasing occurs when more than one variable points to the same memory where
a data structure is stored. In other words, the data structure can be accessed
by any of the aliased variables.

Algorithm is a blueprint (or recipe) that sets out the steps needed to solve a
problem. Algorithms for the basis of computer programs.

Algorithm analysis is the process of analysing the efficiency of algorithms in

terms of either storage space or execution time. Normally we like to know what
the efficiency of an algorithm is in the best, worst and average cases (here case
refer to different input data that the algorithm would process). The best case for
an algorithm refers to input data that allows the algorithm to complete in the
quickest amount of time, or to use the least storage. The worst case is the
opposite and relates to the most amount of time being used or the most storage.
The average case gives the execution time or storage used on average.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
167
Attribute is a property or feature of an object instance.

Base case in a recursive function is a statement (or group of statements) that

does not involve a recursive call to the function. At least one base case is needed
in a recursive function body to ensure that the function will terminate.

Binary format contains only zeroes and ones (i.e., 0 or 1).

Block or statement block is a number of statements (0 .. n) that can appear in a

programming construct like a for loop, function body, or as the body of the if or
else part of an if-else statement. In Python, all statements in a statement block
must have the same degree of indentation.

Compiler is a tool that translates code written in a high-level programming

language into very low level code or actual machine code, so that the code can
be executed on a computer. The compilation process normally results in the
creation of an executable file.

Computer programming is the act of writing a computer program that contains

instructions that can be executed by a computer.
Condition is a Boolean expression that evaluates to either True or False. It can
be used in a selection statement or to control a loop.

Constants are data items used in the execution of a program, but the values of
these data items are fixed and may not be changed by any instructions in the
program. Constant are thus opposite to variable values (see Variable below).

Data structures are used a storage repositories for the data used during the
execution of a computer program. A shopping list might be considered a human
data structure as it contains the items that a shopper would not want to forget
to purchase.

Data types dictate what kind of values may be stored in a variable. Integer types
are whole numbers (positive and negative), float types are decimal values,
character types contain a single alphanumeric or special letter (e.g., punctuation
or mathematical operators), string types contain sequences of characters, and
Boolean types contain only true or false values.

Debugging is the process of finding and correcting errors (also called bugs) in
your program code. Debugging can be done manually, or with the aid of a

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
168
debugger tool, which is normally provided with the programming language
development environment.

Deductive reasoning is the ability to take general facts and knowledge and apply
these to solve a new specific problem.

Desk-checking is a manual process whereby we “execute” an algorithm by hand

to see that the code actually works.

Epoch is defined as a period of time in history. In the context of computer

programming, the last epoch started at 00:00:00 on 1 January 1970.

Error handler is code that allows the user to deal with exceptions in a controlled
way, enabling the programmer to determine what should happen when the
exception occurs.

Exceptions are fatal errors that occur whilst running a user program and which,
if not handled in the code, cause the program to terminate immediately.

Flowchart is a graphic representation of an algorithm. Basic flowchart symbols

include start/stop oval symbols, rectangular process or task symbols, diamond
decision symbols and input/output symbols in the shape of a parallelogram.
Arrows show the control of flow through the flowchart.

Hashing makes use of a mathematical function known as a hash function to

generate a lookup value from a key, given as a string or a list of numbers. The
lookup value is normally a small integer value that is used as an index into a
hash table or dictionary.

High-level programming language is a programming language that is easier to

understand and use by the programmer, but which needs to be converted into a
format that a computer can understand. Examples of these languages are C,
C++, C#, Java, Python, Go, and many others.

IDE (integrated development environment) is software that provides the

necessary tools for developing computer programs, amongst others, a file editor,
a debugger, and a means for executing the code.

Immutable means that after being initialised, the value of a data variable cannot
be changed during the execution of a program.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
169
Inductive reasoning is the ability to take solutions to very specific problems and
induce a solution to a more general problem.

Instance is a single occurrence of an object. The process of creating an instance

of an object is called instantiation.

Interpreter is a tool that executes individual lines of code written in an interpreted

programming language. Interpreting program code line by line is normally slower
than executing compiled code.

Looping refers to repetition of some instructions in program code. Thus the body
of a loop (or loop body) contains the instructions that must be repeated
depending on some condition.

Methods are processes or functions that objects can perform.

Machine code refers to the binary (i.e., zeroes and ones) instructions that a
computer can understand and execute.

Modifiers are functions that cause side-effects.

Namespace in Python is a collection of all the identifiers (variables, constants,

function/member names, etc.) that belong to a particular module (i.e., code
contained within a single file).

Nesting occurs when a data structure type includes an element of the same type,
e.g., a list includes an element that is also a list. Nesting can also be used in the
context of loops, where a second loop appears as a statement within the original
loop’s body.

Object is a type of data structure used in an object oriented language (like

Python) to hold data. All objects can have their own methods and attributes that
define what processes can be performed as well as what features or properties
belong to each object instance.

Parameter is a placeholder in a function’s parameter list, that allows us to supply

the actual value (also called an argument) to be used in the function body only
when we call the function.

Pass-by-reference parameter passing means that the original argument is passed

to the function. Any changes made inside the function body to the parameter are

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
170
visible as changes outside the function as well. This form of parament passing is
normally only used for compound data structures like lists and objects.

Pass-by-value parameter passing means that a copy of the argument is made

and passed to the function. Any changes made inside the function body to the
parameter do not reflect as changes outside the function.

Pseudocode refers to the use of mathematic symbols combined with English-like

instructions to express algorithms. Other spoken languages can be used instead
of English. There is no standard way of writing pseudocode, so it is up to the
programmers to devise their own form of writing.

Pure functions are those that do not make any changes to arguments passed as
parameters by reference (e.g., lists). In other words, pure functions do not cause
any side-effects.

Recursion means defining something in terms of itself. Thus a recursive function

is a function that calls itself from within its body. It is important that within a
recursive function there is a simple base case that ensures that the function will
terminate.

Scope of an identifier is that part of the code where the identifier can be accessed
or used.

Semantics of program code refers to the meaning of expressions, constructs or

program units, i.e., what is the logic represented by that code.

Side-effects are caused by functions making changes to arguments passed as

parameters by reference (e.g., lists). Such functions are called modifiers.

Syntax refers to the technical format of expressions and constructs in a

programming language or even the entire program. An analogy with natural
languages is how words are created from letters, how words are arranged in a
sentence and the correct use of punctuation.

Traceback information, also called a stack trace, shows what methods/functions

were called (in the correct order) to reach a particular point in the code, normally
where an exception has occurred.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
171
Tracing is a standardised process that does much the same as desk-checking,
except that it can also help keep track of values of variables as they change
during execution and other technical aspects too.

Unit testing involves testing individual functions to see that they work correctly
before completing the whole program in which the function will be used. To do
so, some code scaffolding must be set up to initialise variables to be passed as
arguments to the function being tested, as well as actually make calls the
function being tested.

Variable in a computer programming context is defined simply as storage for a

piece of data that is used in a computer program. In other words, the data item
can have variable values at different times during the execution of the program.

Volatile memory refers to storage that is no longer available to the programmer

once a program using that memory stops executing, e.g., the random access
memory used by the program while executing to store data and other
information. Non-volatile storage refers to data files stored on hard disk or flash
drives.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
172
 References

Ada Developers Academy, 2016. Notes on Algorithms [Online]. Available from:

[Link]
lessons/problem-solving/algorithms. [Accessed: 2023-01-05]

Gouws, L.A. 2013. The Role of Computational Thinking in Introductory

Computer Science. MSc. thesis, Rhodes University, South Africa.

Hardson-Hurley, K. (n.d). Thonny: The Beginner-friendly Python Editor

[Online]. Available from: [Link]
[Accessed: 2023-01-06]

[Link] (n.d.). Using the Debugger (Thonny) [Online]. Available from:

[Link]
[Accessed: 2023-01-06]

Knuth, D.E. 1997. The Art of Computer Programming: Volume 1: Fundamental

Algorithms, 3rd Edition. Addison-Wesley Professional. Available:
[Link]
[Accessed: 2023-01-05]

Python Dev. (Producer/owner) (2022). Installing Thonny on Linux Ubuntu

[Online video]. Available from:
[Link] [Accessed: 2023-01-06]

[Link] (Producer/owner) (2023). The Python Standard Library [Online].

Available from: [Link] [Accessed: 2023-01-06]

Thonny (n.d). Thonny: Python IDE for beginners [Online]. Available from:
[Link] [Accessed: 2023-01-05]

Van Rossum, G. (Producer/owner) (2023). The Python Tutorial [Online].

Available from: [Link] [Accessed:
2023-07-15]

Wang, P.S. 2016. From Computing to Computational Thinking. CRC Press, Boca
Raton, Fl, USA.

Wentworth, P., Elkner, J., Downey, A.B., and Meyers, C., 2012. How to Think
Like a Computer Scientist, 3rd edition. Runestone Academy. Available from:
[Link]
[Accessed: 2023-01-05]

Wing, J. 2006. Computational thinking. Communications of the ACM, 49(3):33–

35. Available from: [Link]
[Accessed: 2023-01-05]

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
173
Wirth, N. 1967. Algorithms + Data Structures = Programs. Prentice-Hall, USA.

Wolfram MathWorld. (Producer/owner) (December 2022). Greatest common

divisor [Online]. Available from:
[Link]
[Accessed: 2023-01-05]

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
174
 Answers to Self-Assessment Questions

TOPIC 1 SELF-ASSESSMENT ANSWERS

1.
Answer = 192 individual digits

By focusing on the way numbers increment, you will see a pattern of 1-digit,
2-digit and 3-digit numbers. Knowing how many of each of these numbers
there are, you can create a subtotal of digits for each category:
1-digit = 9 numbers (1-9) -> 9 digits
2-digit = 90 numbers (10-99) -> 180 digits
3-digit = 1 number (100) -> 3 digits

2.
Answer = 20 km

This problem is iterative in nature, so finding a pattern is relatively easy:

Day 1 = x km; Day 2 = x+10; Day 3 = x+10+10 = x+20;
Day 4 = x+20+10 = x+30; Day 5 = x+30+10 = x+40
Thus, x+(x+10)+(x+20)+(x+30)+(x+40) = 200
5x +100 = 200
5x = 100
x = 20

An alternative way to calculate this is to add up the extra kms walked on

days 2 to 5 (100 km in total) and subtract this from 200 and then divide the
remainder (100) by 5.

3.
Answer = BALL

Writing out the codes for each letter of the alphabet helps to understand the
problem clearly. Thereafter, one can simplify the problem by focusing only on
letters that could appear in the coded word, namely 1 = A, 2 = B, 11 = K, 12
= L, 21 = U, and V = 22. The only possible first letters are ‘B’ and ‘U’. Given
that the word is a common English word, it makes sense to assume that the
word starts with ‘B’ rather than ‘U’ and then to pursue all options that are
likely to lead to a solution.
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
175
4.
Answer = 1110

A brute force method is just to keep multiplying 15 by an increasing number

– but this method will take 74 iterations to find the solution.
Alternatively, you can create a pattern of numbers containing only 1 and 0
digits by starting with 10 and then iteratively adding either 0 or 1 to each of
the right hand sides, or changing the rightmost digit to a 0 or 1. Note that
having numbers end in 1 can never be divisible by 15 (and are highlighted in
red below), but we need them to create the full list of possible number.
This way you will build up a sequence of numbers (containing only 0 or 1
digits) that can then be checked for divisibility by 15.
The sequence of numbers created would be something like: 10, 11, 100, 101,
110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110.

5.
Answer = V

The pattern is an increasing list of letters (starting with 1 letter, Z) from the
end of the alphabet:
Z, Z, Y, Z, Y, X, Z, Y, X, W, Z, Y, X, W, V, Z, Y, X, W, V, U

6.
Answer = (d) Four of the statements are false.

This problem is more easily solved by negating the question and solving the
question: Which four statements are false? This will lead to finding which
one statement is true – and it is in fact the statement that says that four
statements are false.

7.
Answer = approx. 163.75 min rounded up to 165 min

The pattern to observe here is that it takes 20 min (5 to run and 15 to rest)
to move 20 m up the mountain. However, once you have reached 160 m up
the mountain, you can do the last 30 m in less than 5 min, and you do not
need to include the resting as you will be on top of the mountain and won’t
slide down. It is easy in this question to forget that the final sprint to the top
does not need the rest time (which is often referred to as an off-by-1 error)!

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
176
8.
Answer = A-D-E-G-H-X 10 units of travel time

One way of solving this problem is to find the shortest path from each node
to the crash site, starting with the nodes closest to the crash and working
backwards. This might give a list like this: X = 0 (no time to move from X to
X); H = 2 (direct path H-X); G = 3 (path is G-H-X); C = 5 (path is C-H-X); E
= 5 (path is E-G-H-X); B = 7 (path is B-C-H-X); D = 8 (path is D-E-G-H-X);
F = 6 (path is F-E-G-H-X). With this information it is now easy to see what the
best path is from A: either (5 + time from B) = 12; or (2 + time from D) =
10; or (6 + time from F) = 12. Thus, shortest time is 10 units following the
route A-D-E-G-H-X.

TOPIC 2 SELF-ASSESSMENT ANSWERS

1.
Some of the properties are:
 The algorithm must solve the given problem correctly — correctness
 Each instruction must be precise and unambiguous — definiteness
 The algorithm must be able to be executed by the computational
device (possibly after suitable translation) — feasibility
 The algorithm must eventually terminate — finiteness
 The algorithm must have zero or more inputs and one or more output

2.
The instructions you provide must enable your friend to reach the
supermarket without issues.

3.
input value to compare – call this N

WHILE there are still items in the list that have not been scratched out
move to leftmost item that has not been scratched out
call this the current item
compare N with the current item
IF these are the same
THEN write out “FOUND item” and exit the algorithm
ELSE scratch out the current item
END WHILE
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
177
 if you get here, you have checked all the items in the list and the item
you were looking for was not found in the list

4.
You could use exactly the same algorithm as in (3) to do this, but a more
efficient algorithm that can be used with a sorted list (called binary search)
is to start by comparing N to the item in the middle of the sorted list.

This comparison will result in one of three optional paths:

a) If N is greater than this middle item, then you can scratch out all items
to the left of this middle number (including the middle number) and
continue searching only the unchecked items to the right.
If there are no more items to check in this right sublist, then you have
failed to find the item and the algorithm exits.
Else you repeat the algorithm by starting a new search that checks the
item in the middle of this new sublist.

b) If N is smaller than this middle item then you can scratch out all items to
the right of this middle number (including the middle number) and
continue searching only the unchecked items to the left.
If there are no more items to check in this left sublist, then you have
failed to find the item and the algorithm exits.
Else you repeat the algorithm by starting a new search that checks the
item in the middle of this new sublist.

c) If N is equal to the middle item, then you have FOUND your item and you
can stop searching.

5.

enter N
product = 1
k=1
WHILE k <= N
product = product * k
k=k+1
END WHILE
output product

This can also be solved as follows:

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
178
 enter N
product = 1
k=N
WHILE k > 1
product = product * k
k=k-1
END WHILE
output product

6.
a) 1 2 3 4 5 6 7 8 9 10 11 12
b) 5 4 3 2 1
c) 01234567
d) 1 2 3 4 5 6 7 8
e)
There will be no output from this code as j is not greater than 8 when
the condition is evaluated for the first time

TOPIC 3 SELF-ASSESSMENT ANSWERS

1.
The code determines the maximum value of a or b.
The output is:
?? value is b: 30
It would be make sense to replace the ?? with the word “Maximum”

2.
The code sums the values of a, b and c.
The output is:
?? of three numbers is 60
It would be make sense to replace the ?? with the word “Sum”

3.
The code requires the user to type in a name and then outputs whatever the
user has typed in. The input() command seems to stop the execution –
with the cursor flashing at the left side of the shell window. This is the prompt
for the user to type in a string.

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
179
 If the user types in Mickey, the output will be:
My name is Mickey

4.
The code calculates various mathematical expressions: first the remainder
when dividing a by b, next the integer division of dividing c by a, and finally
the floating point division of dividing c by a.

The output is:

Rem is 3
IntDiv is 2
FloatDiv is 2.5

5.

#Corrected code
a = 10
b = 5
c = 45
calc = b + c - a
print("The total =", calc)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
180
TOPIC 4 SELF-ASSESSMENT ANSWERS

1.

import turtle
def make_window(colr, ttle):

w = [Link]()
[Link](colr)
[Link](ttle)
return w

def make_turtle(colr, sz):

t = [Link]()
[Link](colr)
[Link](sz)
return t

def drawsquare (t,size) :

[Link]()
for i in range(4):
[Link](size)
[Link](90)

wn = make_window("lightgreen", "Squares")
alex = make_turtle("hotpink", 5)
drawsquare(alex, 20) # alex draws a small square
[Link]()
[Link](50)
drawsquare(alex, 40) # alex draws a big square
[Link]()
[Link](70)
drawsquare(alex, 20) # alex draws a small square
[Link]()
[Link](50)
drawsquare(alex, 40) # alex draws a big square
[Link]()
[Link](70)
drawsquare(alex, 20) # alex draws a small square
[Link]()
[Link](50)
[Link]()

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
181
2.

def factorial (n) :

if n < 0 :
return "Invalid value" # catches incorrect values
product = 1
for j in range(n) :
product = product * (j+1)
return product

print(factorial(-3)) # prints an error

3.

def checkprime(n) :
if n <=0 :
return "Invalid" # only check positive nums
prime = True # assume n is prime
div = 2 # start checking from 2
while div <= (n // 2) : # only need to check first half
if n % (div) == 0 : # no remainder - so not prime
prime = False
break # exit if divisor found
div += 1
return prime

print(checkprime(-1)) # prints 'Invalid'

print(checkprime(23)) # print True
print(checkprime(55)) # print False

4.

def truthtable() :

print(" x\t", " y\t", " z\t",

"(x or y) and (not x and z)")
for x in [True, False] :
for y in [True, False] :
for z in [True, False] :
result = (x or y) and (not x and z)
print (x, "\t", y, "\t", z, "\t\t", result)

truthtable()
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
182
5.

# code for FizzBang game where user types in a range

# supports counting both forwards and backwards
# using the same code

def fizzbang(num) :
if (num % 3 == 0) and (num % 5 == 0) :
return "FizzBang"
elif (num % 3 == 0) :
return "Fizz"
elif (num % 5 == 0):
return "Bang"
else :
return num

# code to run the game

print("Please type in a starting number:")
start = int(input())
print("Please type in an ending number:")
end = int(input())
if end > start : # count forwards
inc = 1
else : # count backwards
inc = -1
num = start
while num != end+inc : # find stopping point
print(fizzbang(num))
num += inc

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
183
TOPIC 5 SELF-ASSESSMENT ANSWERS

1.

def reverse (alist) :

start = 0 # first element
end = len(alist)-1 # last element
while start < end : # if not crossed halfway
temp = alist[start] # swap elements
alist[start] = alist[end]
alist[end] = temp
start += 1 # move to next element from left
end -= 1 # move to next element from right
return alist

2.

import random
# generate random numbers either 1's or 0's
# to denote heads or tails

randomgen = [Link]() # create random generator

tails = 0 # to sum the number of tails
heads = 0 # to sum the number of heads
N = 100

for i in range(N) : # 100 coin tosses

mynum = [Link](0,2) # to get 0's or 1's only
print(mynum) # not needed but good for checking
if mynum == 0 :
tails+= 1 # add 1 to tails total
else :
heads+= 1 # add 1 to heads total

print(N, "coin tosses executed")

print("Number of heads = ", heads)
print("Number of tails = ", tails)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
184
3.

# converts a binary number as a string to a decimal number

def binary2dec (astring) :
i=0
digits = len(astring)-2 #last digit, excl newline
num = 0 #to calculate decimal number
while i <= digits :
num += (int)(astring[digits-i]) * (2 ** i)
print(int(astring[digits-i]))
i+=1
return num

# processes the data file and outputs to results file

myinfile = open("[Link]", "r")
myoutfile = open("[Link]", "w")
while True :
nextline = [Link]() # reads newline too
if nextline == "" :
break # no more data
binarynum = nextline[:]
decimalnum = binary2dec(binarynum)
[Link](str(decimalnum))
[Link](" is the decimal conversion for binary ")
[Link](binarynum)
[Link]()
[Link]()

[Link] file:

100011
1010101
1111111
11
1
0
100000

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
185
 [Link] file:

35 is the decimal value of binary 100011

85 is the decimal value of binary 1010101
127 is the decimal value of binary 1111111
3 is the decimal value of binary 11
1 is the decimal value of binary 1
0 is the decimal value of binary 0
32 is the decimal value of binary 100000

4.
Code changed as follows (see bolded lines) in the efficient bubblesort. Note
that the same additions should be made to the naïve bubblesort code.

def effbubsort(alist):
# code includes collecting metrics
iter = len(alist)-1 # max number of iterations
comparisons = 0
swaps = 0
for i in range(iter):
nochanges = True # assume list is sorted
for j in range(iter):
comparisons += 1
if alist[j] > alist[j+1]:
# swap adjacent elements
temp = alist[j]
alist[j] = alist[j+1]
alist[j+1] = temp
swaps += 1
nochanges = False # confirm changes made
if nochanges == True : # list sorted so exit
break
print("Comparisons done = ", comparisons, " Swaps done =
", swaps)
return

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
186
 Results when executing the naïve code:
List1:
Comparisons done = 49 Swaps done = 0
List2:
Comparisons done = 49 Swaps done = 28
List3:
Comparisons done = 49 Swaps done = 9
List4:
Comparisons done = 49 Swaps done = 12

Results when executing the more efficient code:

List1:
Comparisons done = 7 Swaps done = 0
List2:
Comparisons done = 49 Swaps done = 28
List3:
Comparisons done = 35 Swaps done = 9
List4:
Comparisons done = 35 Swaps done = 12

Best case input for both algorithms is a list already sorted in the correct order.
Worst case input for both algorithms is a list sorted in the reverse order.

5.
The function swap() does not actually swap the lists in variables a and b. This
is related to the way that lists are passed as parameters. Recall Figure 5.7
which is reproduced below with some changes related to this question:

memory
x
alist [1,2,3,4,5]
y
blist ["is","it","ok"]

Memory when calling swap() with alist and blist passed as arguments

When a list is passed as an argument (e.g., alist), the local parameter

variable (e.g., x) is made to point to the original storage of the list. So any
changes made to the elements within the list will reflect in the original alist
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
187
 contents. However, if we were to change x to point to another list, say the
list that y points to, nothing changes when we return from the function call
to swap(), as both alist and blist still contain the same elements as
before.

memory
x
alist [1,2,3,4,5]
y
blist ["is","it","ok"]

Memory after executing the swap code inside the function

TOPIC 6 SELF-ASSESSMENT ANSWERS

1. Note the base case … an empty string

def printback (str) :

if len(str) == 0: # string empty – base case
return
printback(str[1:]) # recursive call
print(str[0]) # print str[0]

printback("abc") # prints cba

printback("") # prints nothing
printback('backwards') # prints sdrawkcab

2. Calculating binary representations from a decimal number is done using

integer division (//) and modulo (%) operators. Note the order of the recursive
call and the print command. What would happen if you reversed these?

def printbinary(num):
# print a base-10 number as a base-2 number
if num == 0: # base case; print 0
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
188
 print(0)
return
if num == 1: # base case; print 1
print(1)
return
if num % 2 == 0: # note order of recursive call & print
printbinary(num//2) # recursive call first
print(0) # then print
else:
printbinary(num//2) # recursive call first
print(1) # then print
return

printbinary(1) # prints 1
printbinary(27) # prints 11011 -- each digit on new line
printbinary(100) # prints 100100 -- each digit on new line

3. To solve this problem it is easier to just catch a generic ValueError and to

include an out of range print statement in the code of the if-statement.

def getAnswer2():
# better function with exception handling of general ValueError
try:
print("Please input an integer between 0 and 100:")
ans = int(input())
if (ans < 0) or (ans > 100):
print("Your input is not between 0 and 100")
raise ValueError
except ValueError:
print("Your input is not valid")
return -1
return ans

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
189
Some testcases:

>>> getAnswer2()
Please input an integer between 0 and 100:
aef
Your input is not valid
-1

>>> getAnswer2()
Please input an integer between 0 and 100:
6
6

>>> getAnswer2()
Please input an integer between 0 and 100:
-1
Your input is not between 0 and 100
Your input is not valid
-1

4.

# cyphers to code original characters into coded characters

actual_code = {"a":"g", "b":"h", "c":"i", "d":"j", "e":"k",
"f":"s", "g":"t", "h":"u", "i":"v", "j":"w", "k":"x", "l":"y",
"m":"z", "n":"a", "o":"b", "p":"c", "q":"d", "r":"e", "s":"f",
"t":"l", "u":"m", "v":"n", "w":"o", "x":"p", "y":"q", "z":"r"}

# cyphers to decode coded characters into original characters

code_actual = {"g":"a", "h":"b", "i":"c", "j":"d", "k":"e",
"s":"f", "t":"g", "u":"h", "v":"i", "w":"j", "x":"k", "y":"l",
"z":"m", "a":"n", "b":"o", "c":"p", "d":"q", "e":"r", "f":"s",
"l":"t", "m":"u", "n":"v", "o":"w", "p":"x", "q":"y", "r":"z"}

def encode(str):
#translate a string into code
newstr = ''
index = 0
while index < len(str):
newstr += actual_code[str[index]]
index+=1
return newstr
© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming
CTIP152
190
def decode(str):
#translate a coded string back into the original string
newstr = ''
index = 0
while index < len(str):
newstr += code_actual[str[index]]
index+=1
return newstr

# tests
encode("hello") # returns "ukyyb"
encode("dosomeworknow") # returns "jbfbzkobexabo"
decode("ukyyb") # returns "hello")
decode("jbfbzkobexabo") # returns "dosomeworknow")

6. Function binaryfind() calls a helper function search(), which uses a recursive

algorithm to search various halves of the list based on the binary search
algorithm.

def binaryfind(n, mylist):

if len(mylist) == 0:
print ("Not found, empty list")
else:
# call helper function to do actual search
res = search(n, mylist, 0, len(mylist)-1)
if res == -1:
print ("Not found")
else:
print ("Found at index ", res)

def search(n, mylist, start, end):

# start & end denote the range of sublist to search
if start > end : # stop case: have checked everything
return -1
if end == start: #calculate mid if only one element
mid = start
else:
mid = start + ((end-start) // 2) # find middle element
if mylist[mid] == n: #check middle item

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
191
 return mid
else:
if mylist[mid] > n:
# search bottom half of list
return(search(n, mylist, start, mid-1))
else:
# search top half of list
return(search(n, mylist, mid+1, end))

Some testcases:

#define a list to search

thelist = [0,1,3,5,7,9,11,13]

binaryfind(100, thelist)
binaryfind(-1, thelist)
binaryfind(5, thelist)
binaryfind(4, thelist)
binaryfind(0, thelist)
binaryfind(10, thelist)

#test helper function too

search(9, thelist, 0, 7)

© STADIO (Pty) Ltd Computational Thinking and Introduction to Programming

CTIP152
192