Algorithms and Mathematical

Concepts in Computing
Topic 1:
Computational Thinking

© NCC Education Limited

 Computation Thinking Topic 1 - 1.2

What do you think?

• Why Algorithms and Mathematical Concepts is

important?

• What are you hoping to learn from this Unit?

 Computation Thinking Topic 1 - 1.3

Unit Aims
The aim of algorithms and mathematical concepts in
computing is to provide a foundation for solving
complex computational problems efficiently and
effectively.
These concepts are fundamental to computer science
and play a crucial role in various aspects of
computing, including software development, data
analysis, artificial intelligence, and more.
 Computation Thinking Topic 1 - 1.4

Unit Syllabus

1. Computational Thinking
2. Number Systems
3. Boolean Algebra and Propositional Logic 1
4. Boolean Algebra and Propositional Logic 2
5. Predicate Logic and Set Theory
6. Statistics
 Computation Thinking Topic 1 - 1.5

Unit Syllabus – continued ….

7. Introduction to Data Structure 1

8. Introduction to Data Structure 2
9. Searching and Sorting 1
10.Searching and Sorting 2
11.Tree Data Structure and Searching Algorithms
12.Unit Summary
 Computation Thinking Topic 1 - 1.6

Unit Delivery
• The teacher-led time for this unit is comprised of
lectures and laboratory sessions.
• Lectures are designed to start each topic.
– You should be active during lectures by raising
questions and taking part in discussions.
• Laboratory sessions are designed to follow the
respective topic lecture.
– During these sessions, you will be required to work
through practical tutorials and various exercises.
 Computation Thinking Topic 1 - 1.7

Private Study
• You are also expected to
undertake private study to
consolidate and extend your
understanding.

• Exercises are provided in

your Student Guide for you
to complete during this time.
 Computation Thinking Topic 1 - 1.8

Assessment

• This unit will be assessed by:

– an assignment worth 60% of the total mark
– an exam worth 40% of the total mark
 Computation Thinking Topic 1 - 1.9

References

Essential
• Cormen, T.H., Charles Eric Leiserson, Rivest, R.L., Stein, C. and
Al, E. (2009). Introduction to algorithms. MIT Press.
Recommended
• Sedgewick, R. and Wayne, K. (2014). Algorithms. Addison-Wesley
Professional.
• Donald Ervin Knuth (2005). The art of computer programming,
volume 1. Upper Saddle River, Nj: Addison-Wesley.
 Computation Thinking Topic 1 - 1.10

Algorithms and
Mathematical Concepts
Topic 1 – Lecture 1:
Computational Thinking
 Computation Thinking Topic 1 - 1.11

Scope and Coverage

This topic will cover:
• Introduction to the unit
• Introduction to the software development process
• Solving problems in computing
• Modelling, diagrams and pseudocode
• Definition and design of simple algorithms
• Using abstraction and decomposition when attacking a large complex
task. Separation of concerns.
 Computation Thinking Topic 1 - 1.12

Learning Outcomes

By the end of this topic students will be able to:

• Ability to break down complex problems into
smaller, manageable steps.
• Proficiency in designing algorithms to solve specific
tasks or challenges.
• Capacity to identify patterns and trends within data
or information.
• Recognition of similarities across different problems
or scenarios
 Computation Thinking Topic 1 - 1.13

Introduction to the unit

 Computation Thinking Topic 1 - 1.14

What do you currently know ?

What is current knowledge in How good is your Maths?

Computer Science?

Have you ever written computer

code?
 Computation Thinking Topic 1 - 1.15

Computational mathematics is
the area of technology
involving the application of
mathematical topics using
computing technology.

Simplify: Math's on computer

 Computation Thinking Topic 1 - 1.16

What are Real Life Applications of Computational

Maths

1. Internet 2. Searching
Security- shortest and
Encryption Reliable Routes to
Algorithms Destinations
(Google
4. DigitalMap)
Logic
3. Science and
and Design
Engineering
Applications
 Computation Thinking Topic 1 - 1.17

Encryption Algorithms
• Use to provide confidentiality
• Encryption Algorithm: Transforms the plaintext
into ciphertext
• Decryption Algorithm: Transform the ciphertext
into plaintext
1. Internet • Plain Text: Hello World
Security (1) • Ciphertext: Ebiil Tloia
• Example
– Substitution Algorithms: Caesar cipher
algorithm
– A, B, C…..1 2 3
 Computation Thinking Topic 1 - 1.18

Encryption Algorithms
q Caesar cipher -
classical simple
encryption algorithm.
q Easily breakable
q Involve little
mathematics
1. Internet q Advanced Encryption
Algorithm (AES)
Security (2) q Modern complicated
algorithm
q Involves many
mathematical
operations
q Matrix calculation,
mixing rows, shaping
digits, swapping
columns, dropping bits
and adding bits etc.
 Computation Thinking Topic 1 - 1.19

2. Searching
shortest and
Reliable Routes to
Destinations

qSearching Algorithms
qGoogle Map uses A*
algorithm to find the
shortest paths to desired
destinations.
 Computation Thinking Topic 1 - 1.20

3. Science and Engineering

DNA and RNA sequencing Machine learning and AI techniques

to predict a determined health
problem in humans

Machine learning and AI techniques

to predict the weather forecasting,
stock exchange forecasting,
pandemic forecasting
 Computation Thinking Topic 1 - 1.21

• Used to develop hardware, e.g. circuit boards &

4. microprocessors: comprises of millions of components to carry

out operations such as arithmetic etc.

Digital
• Logical And Gate, Logical OR gate, Logical Nor Gate, Adder,
Subtractor

Logic
and
Design
 Computation Thinking Topic 1 - 1.22

Computers are powerful machines…

 Computation Thinking Topic 1 - 1.23

…but also stupid on their own

 Computation Thinking Topic 1 - 1.24

How computers know what to do with data?

Input Process Memory Storage Output

 Computation Thinking Topic 1 - 1.25

Decimal Binary Octal Hexadecimal

0 0000 000 00
1 0001 001 01
2 0010 002 02
3 0011 003 03

Computer
4 0100 004 04
5 0101 005 05
Number 6 0110 006 06
7 0111 007 07
System 8 1000 010 08
9 1001 011 09
10 1010 012 0A
11 1011 013 0B
12 1100 014 0C
13 1101 015 0D
14 1110 016 0E
15 1111 017 0F
 Computation Thinking Topic 1 - 1.26

• The branch of mathematics that deals

with the properties and relationships of
Some
numbers,Number
variety of different types:
Theory
• odd 1, 3, 5, 7, 9, 11, . . .
• even 2, 4, 6, 8, 10, . . .
• square 1, 4, 9, 16, 25, 36, . . .
• cube 1, 8, 27, 64, 125, . . .
• prime 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.
• composite 4, 6, 8, 9, 10, 12, 14, 15, 16, . .
• 1 (modulo 4) 1, 5, 9, 13, 17, 21, 25, . . .
• 3 (modulo 4) 3, 7, 11, 15, 19, 23, 27, . . .
• triangular 1, 3, 6, 10, 15, 21, . .
• perfect 6, 28, 496, . . .
• Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, . . .
Computation Thinking Topic 1 - 1.27
Prime Factors
Computation Thinking Topic 1 - 1.28

• Prime factor is the factor of the given number which is a prime number also.
• Example to find prime factors of 210
• We need to divide 210 by the first prime number 2 we get 105.
• Now we need to divide 105 by the prime number 3 and we get 35.
• Again we need to divide 35 by the prime number 5 and we get 7.
• And, again we need to divide 7 by the prime number 7 and we get 1.
• Therefore, 210 = 2 × 3 × 5 × 7
• In the same way if we find the factors of 14 are 1, 2, 7 and 14,
• Out of these 2 and 7 are prime numbers.
• Therefore, 2 and 7 are prime factors of 14. Hence, 14 = 2 × 7
• The prime factors of 15 are 3 and 5; 15 = 3 × 5.
• The prime factors of 21 are 3 and 7; 21 = 3 × 7
 Computation Thinking Topic 1 - 1.29

Greatest Common Divisor (GCD)

• In mathematics, the greatest common divisor (gcd) of two or more integers, which are not
all zero, is the largest positive integer that divides each of the integers.
• Example: What is the greatest common divisor of 54 and 24?
• The number 54 can be expressed as a product of two integers in several different ways:
54 × 1, 27 × 2 , 18 × 3 , 9 × 6
• Thus, the divisors of 54 are: 1 , 2 , 3 , 6 , 9 , 18 , 27 , 54.
• Similarly, the divisors of 24 are: 1 , 2 , 3 , 4 , 6 , 8 , 12 , 24.
• The numbers that these two lists share in common are the common divisors of 54 and 24:
1,2,3,6.
• The greatest of these is 6. That is, the greatest common divisor of 54 and 24.
• One writes: gcd ( 54 , 24 ) = 6.
 Computation Thinking Topic 1 - 1.30

Prime
Number
Identificatio
n Flowchart
 Computation Thinking Topic 1 - 1.31

Group In group of 2, write an algorithm to print

Activity even numbers from 1 to 20.

How many numbers do we need?

How many steps do we need?

Will be about 10 minutes

 Computation Thinking Topic 1 - 1.32

Topic 1 – Lecture 2:
Introduction to the Software Development
Process
 Computation Thinking Topic 1 - 1.33

Software Development Process

A starting point
Three main - identifying
steps:
and selecting IS projects
• Identifying potentials
• Classifying and ranking each
potential
• Selecting a project

Criteria can include:

• Best fit for mission and
objectives
• Provide best means to take
advantage of opportunities
• Solve existing problems
 Computation Thinking Topic 1 - 1.34

Problems in Practice

Traditionally, organisations have not used systematic planning processes to

determine how to allocate IS resources
Usual method is to solve isolated organisational problems
• What procedure (application program) is required to solve
this particular problem as it exists today?

• Problem with this approach???

 Computation Thinking Topic 1 - 1.35

What is a feasibility study?

• What to study and conclude?

Feasibility Types of feasibility

• Technical
study Legal and contractual?
• Economic
• Schedule Political?
• Operational
Quantifying benefits and costs
Comparing alternatives
 Computation Thinking Topic 1 - 1.36

“Expanded” SDLC - Lifecycle stage and

connectivity
Two main activities:

qRequirement's
determination –
fact finding
qRequirements
structuring –
process view
leading to
systems design
 Computation Thinking Topic 1 - 1.37

An interesting example …

(Valacich et al, 2017)

 Computation Thinking Topic 1 - 1.38

That’s why we end up

with this!
 Computation Thinking Topic 1 - 1.39

Solving Problems in
Computing
 Computation Thinking Topic 1 - 1.40

How to Solve Problems with

Computational Maths?
Obviously with simpler problems solutions can be solved
normally, but how computer will solve these simple
problems?

1+1=? 123 – 86 = ?

36 + 85 = ? 8x7=?

144 ÷ 4 = ?
74 – 39 = ?

but how computer will solve these simple problems?

 Computation Thinking Topic 1 - 1.41

More Complex Problems?

 Computation Thinking Topic 1 - 1.42

What is an algorithm?

• Advantages
• Step-wise Representation
• Definite Procedure
• Programming Language
Independence
• Logical Sequence
• Problem Decomposition
• Disadvantages
• Time consuming
• Difficult to show
Branching and Looping in
Algorithms.
• Big tasks are difficult to
put in Algorithms.
 Computation Thinking Topic 1 - 1.43

There are three key points towards

designing an algorithm.

• Accuracy
Algorithms
• Efficiency

• Stability
Computation Thinking Topic 1 - 1.44
 Computation Thinking Topic 1 - 1.45

Problem Solving
Hercule-Poirot approach
• Breakdown into smaller logical units
• Logically putting together evidence
Jane-Marple approach
• Finding analogies relevant/similar to the
problem at hand
Hit and trial
• Brute force …
Finding similar problems
 Computation Thinking Topic 1 - 1.46

Visualise it …

“while thinking about your solution is useful, writing

it down even more so for two reasons.
• First, once written an idea can be retrieved.
• The second reason is that writing something
down requires thinking very clearly about it”
How to think like a programmer. (2008)
 Computation Thinking Topic 1 - 1.47

Problem Solving (Decomposition)

 Computation Thinking Topic 1 - 1.48

Problem Statement Breakdown

Givens
• Initial state, values
Goals
• Outcome, objectives
• Single/multiple
• Hierarchical/exclusive
Resources
• Given
• Needed
 Computation Thinking Topic 1 - 1.49

Problem Solving Tools

Pseudocode
• Storylines, itemised/sequenced lists
Diagrams
• Storylines, timelines
Flowcharts
Sequence diagrams
• Block diagrams, state machines, collaboration
diagrams,
Visualizations
 Computation Thinking Topic 1 - 1.50

Flowcharts
Start Start

Username/
Input password

Process
Check length
try again

Match
Condition login
false
false
true pwd
true

Process Load user

profile

End End
 Computation Thinking Topic 1 - 1.51

Pseudocode: Making a Cup of Tea

START
Fetch a tea cup
Add 300 ml of water to the kettle
Boil the water until the kettle switches itself off
Place a new tea bag into the bottom of the cup
Pour 200 ml of boiling water from the kettle, into the cup
Leave the tea bag to stew for 10 seconds
Use a metal spoon to stir the tea bag for 3 seconds
Using the spoon, remove the tea bag from the cup
Dispose of the tea bag
END
 Computation Thinking Topic 1 - 1.52

Problem Solving (Pattern Recognition)

Can you find the pattern?

3
The given sequence follows an
6 arithmetic pattern where each term is
obtained by adding a constant
10 difference to the previous term.
15
Term 2: 3 + 3 = 6
21 Term 3: 6 + 4 = 10
28 Term 4: 10 + 5 = 15
Term 5: 15 + 6 = 21
36 Term 6: 21 + 7 = 28
Term 7: 28 + 8 = 36
45 Term 8: 36 + 9 = 45
 Computation Thinking Topic 1 - 1.53

Modelling, diagrams and

pseudocode
 Computation Thinking Topic 1 - 1.54

Standardised methods for systems design and

development;
Specifies how activities are organised

Works as an interface;
Modelling
Always being developed and evolving;

Covering in-depth later on

 Computation Thinking Topic 1 - 1.55

Analysis techniques

- Process modeling - Data modeling

Context diagrams Entity Relationship Diagrams (ERD)
Data Flow Diagrams (DFD’s) (Normalisation)
Process specifications
• Structured English
• Decision tree/tables
• Flow charts
 Computation Thinking Topic 1 - 1.56

Pictorially models system boundaries and project

scope
Modelling
Scope -
Presents an overview of entire system with data
flowing between it and the outside world

Context
(external entities)

Diagrams
Shows how system (the box) interacts with these
external entities (people, Institutions, other
systems)

Helps provide a high-level conceptualisation of the

system being analysed
56
 Computation Thinking Topic 1 - 1.57

Definition and design of

simple algorithms
 Computation Thinking Topic 1 - 1.58

What is an algorithm?

An algorithm is “a finite set of precise instructions for performing

a computation or for solving a problem”
• A program is one type of algorithm
– All programs are algorithms
– Not all algorithms are programs!
• Directions to somebody’s house is an algorithm
• A recipe for cooking a cake is an algorithm
• The steps to compute the cosine of 90°is an algorithm
Some algorithms are harder than
Computation Thinking Topic 1 - 1.59

others
Some algorithms are easy
• Finding the largest (or smallest) value in a list
• Finding a specific value in a list
Some algorithms are a bit harder
• Sorting a list
Some algorithms are very hard
• Finding the shortest path between Miami and Seattle
Some algorithms are essentially impossible
• Factoring large composite numbers
 Computation Thinking Topic 1 - 1.60

Algorithm 1: Maximum element

Given a list, how do we find the maximum element in the

list?

To express the algorithm, we’ll use pseudocode

• Pseudocode is kinda like a programming language,
but not really
 Computation Thinking Topic 1 - 1.61

Algorithm 1: Maximum element

Algorithm for finding the maximum element in a list:

procedure max (a1, a2, …, an: integers)

max := a1
for i := 2 to n
if max < ai then max := ai

{max is the largest element}

61
 Computation Thinking Topic 1 - 1.62

Algorithm 1: Maximum element

procedure max (a1, a2, …, an: integers)
max := a1
for i := 2 to n
if max < ai then max := ai 9
4
7

10
9
8
7
6
5
4
3
2
 Computation Thinking Topic 1 - 1.63

Properties of algorithms
Algorithms generally share a set of properties:
• Input: what the algorithm takes in as input
• Output: what the algorithm produces as output
• Definiteness: the steps are defined precisely
• Correctness: should produce the correct output
• Finiteness: the steps required should be finite
• Effectiveness: each step must be able to be performed in a
finite amount of time
• Generality: the algorithm should be applicable to all
problems of a similar form
 Computation Thinking Topic 1 - 1.64

Using abstraction and

decomposition when
attacking a large complex
task. Separation of concerns.
 Computation Thinking Topic 1 - 1.65

Abstraction and Decomposition

• Essential problem-solving techniques that can be

particularly useful when dealing with large and complex
tasks.
• Break down the task into manageable parts and allow us
to focus on specific aspects or concerns.
• The concept of "separation of concerns" is closely
related and emphasizes keeping different aspects of a
system or problem distinct from each other.
 Computation Thinking Topic 1 - 1.66

Abstraction
• Abstraction involves simplifying complex systems or tasks by focusing on
the essential details while ignoring non-essential ones.
• It helps to create a high-level view of the problem and its components.
• When attacking a large complex task, we can use abstraction by:
• Identifying the core objectives or goals of the task.
• Defining the main components or entities involved.
• Creating a high-level overview or diagram that illustrates the
relationships between these components.
• For example, when developing a software application, you might
abstract the user interface, data storage, and processing components as
separate entities to understand their interactions at a high level.
 Computation Thinking Topic 1 - 1.67

Decomposition
• Decomposition is the process of breaking down a complex task into
smaller, more manageable sub-tasks or modules.
• Each sub-task can then be tackled independently, making it easier to
understand, implement, and test.
• To apply decomposition:
• Identify the major sub-tasks or components required to achieve the
overall goal.
• Break down these sub-tasks further into smaller, more specific tasks.
• Continue breaking tasks down until you have manageable units of work.
• For instance, if you're planning a large event, decomposition would
involve identifying sub-tasks like venue selection, budgeting, guest list
management, catering, and entertainment, and then breaking each of
these down further into actionable steps.
 Computation Thinking Topic 1 - 1.68

Separation of Concerns
• Separation of concerns is a design principle that suggests isolating
different aspects or concerns of a system to make it more modular,
maintainable, and easier to understand.
• It ensures that each component or module has a well-defined
responsibility and doesn't mix unrelated concerns.
• To apply separation of concerns:
• Clearly define and document the responsibilities of each component or
module.
• Minimize dependencies between different concerns, allowing for easier
changes or replacements.
• Ensure that changes or updates to one concern do not impact others.
• In software development, this might involve separating user interface
code from business logic, database interactions, and error handling.
 Computation Thinking Topic 1 - 1.69

Some other useful links

(documentation)
 Computation Thinking Topic 1 - 1.70

Documentation
• Khan Academy: Khan Academy provides excellent, free tutorials on a wide
range of mathematical concepts, from basic arithmetic to advanced calculus.
They also cover algorithms and computer science topics.
Website: Khan Academy
• Coursera: Coursera offers a variety of courses related to algorithms and
mathematics. You can find courses from top universities and institutions.
Website: Coursera
• edX: Similar to Coursera, edX offers a selection of online courses, including
those related to algorithms and mathematics.
Website: edX
 Computation Thinking Topic 1 - 1.71

Summary
This topic covered:
• Introduction to the unit
• Introduction to the software development process
• Solving Problems in Computing
• Modelling, diagrams and pseudocode
• Definition and design of simple algorithms
• Using abstraction and decomposition when attacking a large complex
task. Separation of concerns.
Topic 1 – Computational Thinking

Any Questions?