Department of Computer Science
COS 132 - Imperative Programming
Study Unit 1: Introduction to Algorithms
Copyright ©2025 by Linda Marshall, Inge Odendaal, Mark Botros and Cobus Redelinghuys. All rights reserved.
Contents
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Algorithmic Thinking . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Toasted Sandwiches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Steps of Algorithmic Thinking . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Flowcharts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.1 Flowchart Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Flowchart Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.3 Drawing flowcharts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
[Link] Collatz Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
[Link] Toasted Sandwiches . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.5 Alternative Representations . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Pre and Post Conditions for Algorithms . . . . . . . . . . . . . . . 11
1.5 Brief history of C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7 Document Change Log . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1
1.1 Introduction
This study unit introduces one of the fundamental skills any programmer needs to possess
in order to survive in any development environment. This skill allows the programmer
to develop a solution to a problem in an abstract manner, which they can then translate
into a programming language which is compiled or interpreted to produce executable
code. This skill is known as “algorithmic thinking” and the mastery of this skill is crucial
for the successful completion of any programming module.
1.2 Algorithmic Thinking
Algorithmic thinking will be introduced by first considering an example. The steps in-
volved in developing an algorithm will be formalised for the specific example.
1.2.1 Toasted Sandwiches
Before delving into the depths of algorithmic thinking, consider the following scenario:
The week before going to university to pursue your dreams of obtaining your degree, you
decide to throw a fancy sandwich party for you and your friends. You ask each of your
friends to design a fancy sandwich, and they will need to explain to you how to create the
sandwich.
On the day of the party, one of your friends provides you with the following fancy sandwich
description:
A salami and salmon sandwich with brown bread. Between each layer of salami and
salmon, there is lettuce and cucumber. Between the bread slices and the first layer of
salmon and salami, there needs to be placed a bed of rocket and basil pesto. In the middle
of the sandwich a layer of sun-dried tomato can be found.
Overwhelmed by this description, you decide to break it down into smaller parts. You
identify the following key points:
• Brown bread
• Layers of salami and salmon containing lettuce and cucumber.
• Between bread and salami and salmon layer, there is rocket and basil pesto.
• In the middle there are sun-dried tomatoes.
From your vast experience of making fancy toasted sandwiches, you know the following:
• The bread needs to be buttered on both sides before being toasted.
• The number of layers in the sandwich is different depending on the person’s hunger
levels.
• Basil pesto should only go in the inside of the sandwich.
2
• To ensure the structural integrity of the sandwich, you know that the lettuce should
be broken into smaller pieces and the cucumber should be cut into smaller pieces.
With this knowledge, you decide to derive a set of steps to create the sandwich.
1. Prepare outer bread slices.
2. Ask the “sandwich eater” how many layers they would like.
3. Prepare that number of layers.
4. Add half of the layers to the sandwich.
5. Add the sun-dried tomatoes.
6. Add the rest of the layers to the sandwich.
7. Place the sandwich into the toaster.
8. Close the toaster and wait for it to be sandwich to be ready.
This list can be expanded to be more specific:
1. Turn the toaster on.
2. Butter bottom bread slice on the inside.
3. Add basil pesto.
4. Ask the “sandwich eater” how many layers they would like.
5. Prepare that number of layers.
6. Add half of the layers to the sandwich.
7. Add the sun-dried tomatoes.
8. Add the rest of the layers to the sandwich.
9. Butter the inside of the top bread slice.
10. Add basil pesto to the inside top bread slice.
11. Add the top slice of bread to the sandwich.
12. Butter the outside of the top piece of bread.
13. Place the sandwich upside down on the toaster.
14. Butter the outside of the now top bread slice.
15. Close the toaster and wait for it to be sandwich to be ready.
What you have just done is the process of applying algorithmic thinking using a set of
steps to solve a problem by designing an algorithm. Most everyday tasks can be thought
of in an algorithmic manner, like boiling a kettle, driving to work, greeting your friends
and much more.
3
1.2.2 Steps of Algorithmic Thinking
Algorithmic thinking consists of the following steps:
1. Decomposition:
This step consists of breaking the problem down into smaller constituent parts.
This allows for “easier” sub-problems to be solved which when combined, solves the
original problem.
2. Pattern Recognition:
This step consists of identifying similar parts previously defined or from experience.
Experience allows you to apply a part of a solution from one problem in an attempt
to solve another problem. By recognising patterns and re-using solutions, the speed
at which you develop programs as well as the quality of the produced programs will
increase. Thus it is important to expose yourself to as many problems as possible.
3. Abstraction:
The process of abstraction is to identify the steps that are required to solve the
problem. The steps are usually semi-granular high-level descriptions of how you can
solve the problem.
4. Algorithm:
Formalising the final algorithm is the culmination of all of the previous steps, and
consists granularly of defining the rules/steps that need to be applied to solve the
problem.
Revisiting the toasted sandwich example in Section 1.2.1. We can see that we performed
decomposition when we identified the key points of the algorithm to make the fancy
sandwich. We applied pattern recognition to enhance the algorithm by looking at common
things we do while making sandwiches. Combining decomposition and pattern recognition
we created a set of abstracted steps to create the sandwich. Lastly, we expanded the
abstracted set of steps to create the final algorithm for creating the sandwich.
Although the numerical list we used to define the algorithm worked, we require a more
formal and visual way to define the algorithms, for example, a flowchart.
1.3 Flowcharts
Flowcharts are a visual representation of an algorithm. Flowcharts allow the algorithm de-
signer to showcase all the basic building blocks (formally referred to as flowchart symbols)
to be used for creating an algorithm. Another way to think of the visual representation of
an algorithm is to see it as an abstraction of the algorithm. The idea behind visualisation
is that external memory, in the form of a picture, is used to convey a difficult concept.
This also has the benefit of technical and non-technical people understanding how the
code will work without needing an in-depth understanding of the intricacies of program-
ming. Once the abstracted algorithm is visually created, the process of converting to a
programming language to be compiled or interpreted into concrete executable code, is
simplified.
4
1.3.1 Flowchart Symbols
Table 1 contains the basic flow chart symbols as defined in the ISO 5807 1 standard.
When these symbols are combined any algorithm can be effectively modelled, and then
translated into a high-level programming language to again be translated into executable
code.
Symbol Description Illustration
Type
Start The start symbol indicates where
the initial/entry point is for the algo-
rithm represented by the flowchart.
Start Start
or
End The end symbol indicates the termi-
nation point of an algorithm repre-
sented by the flowchart.
End
Process The process symbol is used to indi-
cate operations or manipulation of
data is performed at that stage of
Process
the algorithm.
Predefined The predefined process indicates a
Process pre-defined sub-process that forms
part of the algorithm but the steps
are not explicitly shown or for- Predefined Process
malised yet.
Decision The decision symbol indicates a
symbol choice/decision that is performed
which can result in two or more al-
ternative “paths” through the flow
chart. The alternative options are A Decision B
labelled.
1
Note you do not need to purchase this document. It was linked for interest’s sake.
5
Symbol Description Illustration
Type
Input/ This symbol is used to model input
Output from external sources, like user in-
symbol put, or output to external sources,
like terminal output. Input/Output
Flow The flow arrow symbol is used to in-
arrows dicate the direction of the informa-
tion flow.
Table 1: Basic symbols used in flowcharts
The symbols listed in Table 1 are a subset of possible flowchart symbols that are important
for COS 132. There are other symbols that are less used, such as to indicate displays,
stored data, databases, and many more.
By combining these symbols in a highly structured manner, flowchart structures can be
defined.
1.3.2 Flowchart Structures
As discussed flow charts are used to model an algorithm in an abstracted visual manner.
Thus, flowcharts allow us to illustrate the following high-level patterns:
• Linear Execution: A set of instruction that is executed in order one after the
other to form a sequential structure. This is illustrated in Figure 1.
• Decision Making: A point in the algorithm where two or more alternative options
can be selected which form a selection structure. This is illustrated in Figure 2.
• Repetition: A set of instructions which is repeated until some termination con-
dition is satisfied to form repetition structures. This allows an algorithm to easily
perform repetitive tasks. This is illustrated in Figure 3.
6
Start
Start
Start
Process 1 Repeat? No
No
Process B Decision Yes
Process 2
Yes Process
7
Process A
Process 3
Finish
End
End
Figure 1: A simple sequen- Figure 3: A simple repeti-
tial flowchart with three pro- Figure 2: A decision flowchart with a Start, tion (loop) flowchart with a
cess steps. Decision, two branches, and an End node. process inside the loop.
1.3.3 Drawing flowcharts
As flowcharts are used by both technical and non technical people, some drawing conven-
tions have been proposed:
• Ensure that flowcharts are easy to read and easy to follow.
• Flowcharts should fit on a single page.
• The sizes of shapes should remain consistent.
• Ensure that the styling of the flow arrows remains consistent.
• The font and styling of the text used in the flowchart remain consistent.
• Ensure that as far as possible, the flow arrows do not cross.
• Ensure that flow arrows consist of straight lines.
• Ensure symbols are appropriately spaced out.
There are more conventions for flowcharts, often which is specified either by the company
you work for or the programming language you develop for. Ensure that you are aware
of the conventions and that you follow them.
1.3.4 Examples
Two examples of flowcharts are shown below. The purpose of these two examples are
to showcase how complicated problems can be reduced to algorithms that can be easily
understood with the aid of flowcharts.
[Link] Collatz Conjecture
The Collatz Conjecture, also known as the 3n + 1 problem, is a simple yet deceiving
mathematical problem, as it remains unsolved till today. The Collatz Conjecture uses
Equation 1 to create a sequence of numbers as defined by Equation 2:
3n + 1 if n is odd
(1) f (n) = n
if n is even
2
where n ∈ Z+ .
(
n i=0
(2) CCi =
f (CCi−1 ) otherwise
where CCi is the ith number in the Collatz Conjecture number sequence.
8
The Collatz Conjecture states that the sequence defined by Equation 2 for any positive
integer value, will eventually reach the value of 1. So for example, if we take CC5 we
obtain the number sequence: 5, 16, 8, 4, 2, 1. If we take CC6 we obtain the number
sequence: 6, 3, 10, 5, 16, 8, 4, 2, 1. CC5 and CC6 are trivial cases and these sequences
can become extremely large. CC27 for example takes 111 steps before reaching a value
of 1. Now using the process of algorithmic thinking we can produce an algorithm for the
Collatz Conjecture and illustrate it as a flowchart – refer to Figure 4.
Figure 4: Flowchart for the printing the Collatz Conjecture.
In Figure 4 we used an input block to obtain the initial value of the sequence, and an
output block to print out the current value of n. We used two conditional blocks to
determine if the value of n == 1 and if n is odd. The flowchart in Figure 4 contains
examples of all three structures discussed in Section 1.3.2.
9
[Link] Toasted Sandwiches
The abstract algorithm laid out for the fancy toasted sandwich discussed in Section 1.2.1
can be expressed by the flowchart in Figure 5. The flowchart contains a series of predefined
processes which encapsulates a series of smaller steps which can be modelled as their own
algorithm.
Figure 5: Flowchart of the abstract algorithm to make a fancy toasted sandwich
10
1.3.5 Alternative Representations
Although flowcharts are a brilliant way to represent an algorithm, they can occupy a
large amount of space, especially for small programs where a text-based solution will
work better. This is where the idea of pseudo-code came from. Pseudo-code is where you
express the algorithm in natural language sentences which again can easily be translated to
executable code. Pseudo-code is less restrictive than flowcharts as the main requirement is
each sentence should convey a single concept and that the pseudo-code should be easy to
understand. There are multiple online resources you can find that delve into pseudo-code
in more depth.
Using the flowchart depicted in Figure 4, the Collatz Conjecture can be expressed with
the following pseudo-code:
Algorithm 1 Pseudo-code for the Collatz Conjecture algorithm depicted in Figure 4
Require: n ∈ Z+
while not n == 1 do
print out n
if if n is odd then
n = 3n + 1
else
n = n2
end if
end while
1.4 Pre and Post Conditions for Algorithms
Now that we know how to create algorithms, and how to visualise and express the algo-
rithms, we need to formalise what can be assumed before the algorithm starts and what
can be assumed after the algorithm has been completed. This is where the pre-conditions
and post-conditions for algorithms comes in.
• Pre-conditions are all the conditions that can be assumed to be true before the
algorithm starts.
• Post-conditions are all the conditions that can be assumed to be true after the
algorithm terminates.
Relating these back to the examples listed in Section 1.2.1 the pre-conditions for the
Collatz Conjecture is that the input number is a positive integer and the post-conditions
is that the sequence of numbers that were printed, terminated with the value of 1. For
the toasted sandwich example, the pre-conditions are that all the ingredients exist and
are available, that you possess the cooking skills to make a toasted sandwich and you
have the friends to suggest the fancy sandwich. The post-conditions are that you get a
tasty fancy sandwich and a messy kitchen.
Now we have our algorithms designed, we can translate them into a high-level program-
ming language. In our case, we will be translating the algorithms into the C++ program-
ming language.
11
1.5 Brief history of C++
C++ is a strongly typed compiled language. This means that the data types of variables
are determined at compile time. C++ initialy fell into the procedural paradigm of pro-
gramming languages, but has been expanded to also fall into the object-orientated and
generic programming paradigms.
C++ was developed and implemented in 1979 by Bjarne Stroustrup (Figure 6), with the
first version of C++ being released in 1983. C++ comes from a long line of programming
languages, as illustrated by Figure 7, and is the direct successor of the C programming
language. The name for C++ is actually derived from adding the increment operator
(++) to C making C++.
Figure 6: Bjarne Strousup [Obtained from the Columbia Engineering faculty page on
08/02/2025.]
In 1985, The C++ Programming Language textbook was published, with the 4th edition of
the book being published in 2013. The different versions of C++, are referred to as stan-
dards, where the capabilities and functionality of different features of C++ is described.
Interestingly, the implementation of some features differed depending on the author of
the compiler. One such example is how random numbers are generated. Currently, the
latest standard of C++ is C++232 which was released in October of 2024. For COS132
you will be using C++98. One of the C++ compilers is the GCC compiler, which started
supporting C++ in 1987. The current version of GCC is 14.2 which was released on the
1st of August 20243
2
Again these standards are linked for curiosity’s sake. Please do not purchase these standards!
3
This information was verified on the 08/02/2025.
12
Figure 7: A brief history of high level programming languages from 1956 to 2004 [Obtained
from Research Gate on 08/02/2025.]
13
1.6 Conclusion
As stated at the start of this study unit, algorithmic thinking is at the core of programming
and problem-solving. The ability to apply the steps outlined in this study unit to create
an algorithm which is expressed in a flow chart can be the difference between a novice
programmer and an excellent programmer. In this series of study units and by extension
in COS 132, you will be expected to be able to do the following to demonstrate your
algorithmic thinking capabilities:
• Design an algorithm for a given scenario and produce a flowchart for the algorithm.
• Convert a flowchart to and from a segment of C++ code.
• Convert a flowchart to and from a segment of pseudo code.
• Apply the steps provided in a flowchart when debugging code.
• Identify errors in flowcharts which resulted in a faulty algorithm being produced.
• Trace a path through a flowchart and determine the conditions needed to reach a
certain state or given a certain precondition, trace the path through a flowchart.
1.7 Document Change Log
Date Change
9 Feb 2025 Initial preparation and presentation of the document.
14
