Computational Problem Solving
and Algorithm Design
Computers
PBS101:Computational Problem Solving and Algorithm Design 2
Computational Problem
It consists of an input --- set of data.
An expected output --- solution derived from the input.
Can be solved by an algorithm.
Defined by a function that maps input to outputs.
Example: Sort a list of numbers
• Input: Unsorted list
• Output: Sorted list
• Sorting Algorithm
PBS101:Computational Problem Solving and Algorithm Design 3
Computational
Problem Examples
• Search for a number
• Sort a list
• Making decisions
• Finding an optimal solution
• Counting
• Matrix multiplication
• Pattern matching
PBS101:Computational Problem Solving and
Algorithm Design 4
Computational
Problem Solving
Recall …
• Decomposition
• Pattern Recognition
• Abstraction
• Algorithm Design
PBS101:Computational Problem Solving and Algorithm Design 5
Decomposition
PBS101:Computational Problem Solving and Algorithm Design 7
Pattern Recognition
Identifies patterns among individual sub-problems to simplify the overall
complex problem.
The effect is to make the overall solution more manageable and widely
applicable.
In the previous example (drawing a simple face), we went from drawing
very basic shapes (lines, circles, etc.), to drawing an eye with specific
dimensions, and then ended up able to draw an eye of any size.
PBS101:Computational Problem Solving and Algorithm Design 8
Abstraction
A way of expressing an idea in a specific context while at the same time
suppressing details irrelevant in that context.
In the previous chapter’s drawing example, we created a shape as an
abstraction.
By itself, the idea of a shape tells you some things – such as that we’re
dealing with a form that has an external boundary or surface – but other
things, like the number of its sides and its internal angles, are unknown
details
PBS101:Computational Problem Solving and Algorithm Design 9
Logical Thinking: Applying logic assumes
you already know at least some things for
sure and allows you to use that knowledge to
arrive at some further conclusions.
Computational
Problem Example: If it is raining and I go out, I will get
wet.
Solving
Algorithm: A sequence of clearly defined
steps that describe a process to follow a
finite set of unambiguous instructions with
clear start and end points.
PBS101:Computational Problem Solving and Algorithm Design 10
Algorithm
Collection of individual steps.
Like a recipe.
Each step should be precisely defined and do only one thing like pre-heat the
oven to 350 degree Celsius.
The steps should be sequential, and the order of steps should be followed.
With execution of each step, the state of things can change like in this previous
example when you pre-heat the oven, the temperature will change.
PBS101:Computational Problem Solving and Algorithm
11
Design
Algorithm
Variables: You need variables in algorithm to keep track of the
states like temperature of the oven can be called “temp”.
Iteration: If you need to repeat a set of steps in an algorithm, also
known as looping. For Ex; if the recipe wants you to break 4 eggs,
you can write “break an egg” and repeat it for 4 times.
Conditions\ Decisions\Selection: When the computer has to
decide between performing a set of steps or not.
PBS101:Computational Problem Solving and Algorithm
12
Design
Let’s design some Algorithms…
Write an algorithm to
make peanut butter
and jelly sandwich
PBS101:Computational Problem Solving and Algorithm Design 13
To check if a number
is even or odd
PBS101:Computational Problem Solving and
Algorithm Design 14
Make a cup of Coffee
PBS101:Computational Problem Solving and Algorithm Design 15
Tying Shoelaces
PBS101:Computational Problem Solving and Algorithm Design 16
The goal of problem-solving using computational thinking is a
solution that a computer can execute. That means an algorithm
with precise, unambiguous meaning that requires neither creative
intelligence nor common sense to understand fully.
Also, things should be explained thoroughly and with great detail.
PBS101:Computational Problem Solving and Algorithm Design 17
References
Beecher, Karl. Computational Thinking : A Beginner’s Guide to
Problem-Solving and Programming. 1st edition, BCS: the Chartered
Institute for IT, 2017
PBS101:Computational Problem Solving and Algorithm Design 18