DEPARTMENT OF COMPUTER

ENGINEERING, ABU ZARIA

COEN201
COMPUTATIONAL THINKING

2021 - 2022

1
Computational Thinking teaches students
how to:

✓ Describe a problem

✓ Identify the important details needed to

solve this problem

✓ Break the problem down into small, logical

steps,

✓ Use these steps to create a process

(algorithm) that solves the problem

✓ Evaluate this process

These skills are transferable to any other

curriculum area
2
 ALGORITHMS DESIGN
✓Algorithm is any well-defined For a process to represent an algorithm, it
computational procedure that must be:
takes some value, or set of
values, as input and produces ✓ Finite: The algorithm must eventually
some value, or set of values, solve the problem.
as output. ✓ Well-defined: The series of steps must
Definition ✓Algorithm is a tool for solving be precise and present steps that are
of a well-specified computational
understandable.
Algorithm problem.
✓ Effective: An algorithm must solve all
✓Algorithm is an iterative, step-
cases of the problem for which someone
by-step procedure for
computation. defined it.

✓Algorithm is a finite sequence

of instructions or a set of rules
used to solve a given problem.
3
 ✓ A problem describes a class of computational tasks.
Problem versus
✓ A problem instance is one particular input from that
Problem Instance
class.

✓ An algorithm is correct when it translates every

Correct versus input instance into the correct output.
Incorrect ✓ An algorithm is incorrect when there is at least one
Algorithms input instance for which the algorithm gives an
incorrect output.
 Flowchart
❑A visual representation of the sequence of steps
and decisions needed to perform a process.

✓Each step in the sequence is noted within a

diagram shape.

Expression ✓Steps are linked by connecting lines and

directional arrows.
of ✓ Flowchart Start
✓Example:
algorithm: ✓ Pseudocode Ask a question

Pupil
responds

Is the
Say that s
Answer
wrong
correct?

Say that s right

Symbols commonly used in Flowchart

✓Terminal – indicate the starting or ending

of the program.

✓Input/Output – use for taking Terminal

Decision
input/output operation, i.e., taking input
and showing output.

✓Process – indicates any type of internal

operations like initialization, calculation,
etc. Input/Output Process
✓Decision – use for asking questions that
Connector
can have either TRUE or FALSE (YES or NO)
as an answer.

✓Connector – used to connect breaks in the

Control Flow
flowchart.

✓Control Flow – show direction of flow

Pseudocode How are algorithms used in the real world?

❑A compact and informal high level ✓ Search Engines such as Google or Bing

description of a program. use algorithms to put a set of search

results into order, so that more often
❑It employs whatever expressive method
than not, the result we are looking for is
is most clear and concise to specify a
at the top of the front page.
given algorithm
✓ Facebook news feed is derived from
Repeat 10 times:
friends’ status updates and other
Ask a maths question
activity, but it only shows that activity
If the answer is right then: which the algorithm thinks you will be

Say well done! most interested in seeing.

Else: ✓ Credit ratings, interest rates and

mortgage decisions are made by
Say think again!
algorithms.
 Correctness is means that a right result is
Correct obtained for all possible problem
ness instances.
✓ A correct algorithm solves the given
computational problem.

✓ An incorrect algorithm might halt with

There are
an incorrect answer.
three basic
features of Maintainability is the effort required to
algorithm: locate and fix an error in the algorithm
Efficien Maintai
cy nability Efficiency means how the time and
computer resources needed to
successfully carry out the algorithm
application scale with the problem size
 Sequencing is the technique of deciding the order
instructions are executed to produce the correct
result.

❑Imagine that we have the following instructions

There are three (A, B, C) to make a loaf of bread:

building blocks ✓ Sequencing ✓Allow to sit at room temperature for 1 hour

to develop a ✓ Selection ✓Bake for 30 minutes
new algorithm: ✓Combine ingredients
✓ Iteration
C->A->B is a standard algorithm for a yeast bread.

A different sequence, C->B->A, might produce a

result that is edible but not high quality.

Even worse, a sequence of B->C->A would not even

produce something edible
Selection is the technique of allowing the Iteration allows an algorithm to repeat
algorithm to select which instructions to instructions.
execute depending on criteria.
❑For example, here is an algorithm to

✓ Using the previous bread baking bake 2 loaves of bread:

example, algorithm C->A->B works if ❑Repeat 2 times:

the ingredients include yeast, but
✓ Combine ingredients
algorithm C->B->A would be faster if
✓ If ingredients contain yeast, allow to
the ingredients do not include yeast.
sit at room temperature for 1 hour

Selection allows us to create one ✓ Bake for 30 minutes

algorithm to solve both cases:

✓ Combine ingredients

✓ If ingredients contain yeast, allow to sit

 SORTING AND SEARCHING
Imagine trying to find the definition of a
Searching
word in a dictionary – we have a number
of possible approaches:
✓ Locating information or verifying that
the information you see is the ✓ we could pick a word at random, check

information you want is an essential if it’s the right word, and repeat this

task. until we get the one we want;

✓ Without this ability, it wouldn’t be ✓ we could start at the beginning,

possible to perform many tasks online, checking each word in turn until we get

such as finding the website on the to the word we want;

Internet selling the perfect coffee pot ✓ we could pick a word in the middle,
for your office. decide whether our word is before or
after that, pick a word in the middle of
that half, and keep narrowing down
 Random Search Start

There are three

Pick a random
number
possible
algorithms for ✓ Random Search
Yes
searching an ✓ Linear Search
item in a list of Is the
✓ Binary Search number
data:
wrong?

No

Stop
 Linear Search

Start ✓ Linear search is a very simple search

algorithm.

✓ In this type of search, a sequential

Set guess to 0 search is made over all items one by
one

✓ Every item is checked and if a match is

Is found then that particular item is

Yes
guess Increase guess by 1 returned, otherwise the search
wrong? continues till the end of the data
collection.
No

Linear Search
Stop
 Start Binary Search
Binary Search
Set lower limit
✓This search algorithm works on the principle
Set upper limit of divide and conquer.

✓For this algorithm to work properly, the data

Is Yes
Set guess to half
collection should be in the sorted form.
Lower < way between
upper? lower and upper
✓Binary search looks for a particular item by
comparing the middle most item of the
No

Is
Stop number < No
collection.
guess?
✓If a match occurs, then the index of item is
Yes
returned.
Set upper =
Set lower = guess
guess - 1 ✓If the middle item is greater than the item,
then the item is searched in the sub-array to
the left of the middle item

✓Otherwise, the item is searched for in the

sub-array to the right of the middle item.
 Compare the value stored at location 4,
Example
with the value being searched.
✓ Given the following sorted array, use
binary search to search the location of
value 31.

Change the low to mid + 1 and find the

new mid value again.
Solution
low = mid + 1
✓ First, we shall determine half of the
mid = low + (high − low)/ 2 = 7
array by using this formula −
mid = low + (high − low)/ 2 = 4
The value stored at location 7 is not a
Compare the value stored at location 5,
match.
with the value being searched.

Change the high to mid – 1 and find the

new value again. It is a match.

high = mid − 1 ✓ We conclude that the target value is

mid = low + (high − low)/ 2 = 5 stored at location 5.
Summary of Binary search

17
Binary search versus Linear Search
 SEARCHING ALGORITHMS
Brute Force Algorithm Common Brute Force Algorithm

✓A brute-force algorithm tends to use the ❑Breadth-first search:

simplest possible approach to solving the ✓This technique begins at the root node,
problem. explores each of the child nodes first, and

✓The advantage of this approach is that you only then moves down to the next level.

don’t need any domain-specific knowledge to ✓It progresses level by level until it finds a
use one of these algorithms. solution.

✓The disadvantage is that a brute-force ✓Advantage: it can check for duplicate nodes,
approach works well only for a small number which saves time, and it always comes up
of nodes. with a solution.

✓Examples: ✓Disadvantage: it uses a considerable amount

✓Computing n! of memory for a large number of nodes.

✓Multiplying two matrices

✓Searching for a key of a given value in a list.

❑Depth-First Search:

✓This technique begins at the root node and

explores a set of connected child nodes until
it reaches a leaf node.

✓It progresses branch by branch until it finds

a solution.

✓Advantage: it’s memory efficient.

✓Disadvantage: it can’t check for duplicate

nodes, which means that it might traverse
the same node paths more than once.

❖In fact, this algorithm may not find a

solution at all, which means that you must
define a cutoff point to keep the algorithm
from searching infinitely.
20
❑A* Search:

✓The algorithm tracks the cost of nodes as it

explores them using the equation:

f(n) = g(n) + h(n), where

❖n is the node identifier.

❖g(n) is the cost of reaching the node so far.

❖h(n) is the estimated cost to reach the goal

from the node.

❖f(n) is the estimated cost of the path from n

to the goal.

✓The idea is to search the most promising

paths first and avoid expensive paths.
21
❑Greedy best-first search:

✓The algorithm always chooses the path that

is closest to the goal using the equation:

f(n) = h(n)

✓This particular algorithm can find solutions

quite quickly, but it can also get stuck in
loops, so many people don’t consider it an
optimal approach to finding a solution.

22
Greedy Algorithm Applications of Greedy Algorithm
❑A greedy algorithm always makes the choice
❑Optimal solutions:
that looks best at the moment
✓Change making for “normal” coin
❑Examples:
denominations
✓Playing cards
✓Minimum spanning tree (MST)
✓Invest on stocks
✓single-source shortest paths
✓Choose a university
✓Simple scheduling problems
❑Two elements are essential for distinguishing
✓Huffman codes
a greedy algorithm:
❑Approximations
✓At each turn, you always make the best
decision you can at that particular instant. ✓Traveling salesman problem (TSP)

✓You hope that making a series of best ✓Knapsack problem

decisions results in the best final solution. ✓Other combinatorial optimization problems
23