Problem Solving Chapter1!3!115749

Chapter One
LET THERE BE – JUST…PROBLEMS!
INTRODUCTION
Problem solving is both quite difficult to teach and practice.
It is both a science and an art. To learn problem solving, you
must do it. As in riding a bicycle, explanations are helpful,
but eventually you must do it yourself. You may fall, but that
is usually necessary in learning to ride a bike. There are no
shortcuts or magic formula to problem solving for a particular
event, task or scenario. However, there are techniques, tools
and procedures or processes that we can all explore in our
quest for ground-truth.
Problem Solving is the science, art and process of generating

solutions from observed data.
- A problem is characterized by a set of goals that the
problem solver must reach.
- A problem is characterized by a set of objects
- A problem is characterized also by a set of operations
- A problem must have a set of states, which must start at
some point S (that is, the initial state), and terminates or
ends its actions when the conditions of a final point G
(that is, the goal state) is reached.
- A problem must have series of action that the problem
solver must move with or take to reach the goal state.
- The plausible solution to any problem must have a cost
or weight associated with each action taken or explored.
- Each action must be accompanied by a penalty – which is
associated to the task or problem if the problem solver
takes the wrong move or jumps off to a state that does
not lead to a possible solution.
A problem space is an abstract domain that encompasses
all valid states that can be generated by the application of
any combination or operators on any combination of objects
to yield the desired solution. The problem space may also
contain one/more solutions. The solution is a combination
of operations and objects that achieves the goal state. A
search refers to the act of navigating the problem space in
quest for ground-truth or solution. The search proceeds with
different types of search control strategies, which will be
mentioned in a later section.
Defining a Problem
What then is a Problem? Defining it is not so easy. A problem
exists when what is currently happening – often differs from
what should be happening. This is so the case because, what
is happening is the current state, and what should happen
is the desired goal state. A problem can either be a one-time
problems or recurring problems. Deciding the total student
enrolment into the Department of Computer Science each
year can be said to be a recurring problem (since there is an
agreed staff-student ratio, which determines the carrying-
capacity for each Department). However, to determine why a
machine failed or why a device is faulty – can be regarded as
a one-time problem.
Many concepts for problem solving apply to both kinds/types

of problems; Though, the problems have different situations.
Recurring problems require continuing data collection, report,
and other infrastructure. Every problem has a lifespan. Some
problems must be solved quickly, but others are not urgent.
We cannot take too long to develop a schedule for programs
run on a computer, because the time to run programs id
usually short. Conversely, we have more time to determine
the location of departments in a plant to be built next year.
Problems have also different impact. Problems solved should
be worthy of the resources required to solve them. If it costs
more to do the study than it will save, don’t do it. The
problem impact should determine the around of effort we put
into solving the problem.
Defining A Solution
Problems by nature and typically, do not go away of their
own accord unless acted upon, or when we do something to
resolve them. This intervention and action is often referred to
as the art and science of problem solving. While, many of us
often seek to explore and exploit easy and quick solutions;
Also, complex problems often require complex and dynamic
solutions. Solving a well-structured problem can be found to
be quite easy. To find the minimum of a quadratic function,
we use first and second derivatives. However, to solve an ill-
defined or ill-structured problems is not obvious and in often
cases, termed as intractable as such solutions may be out
of, or beyond our reach. For example, how would you reduce
world hunger? A large part of problem solving is transforming
ill-structured problems into well-structured problems.
There are four (4) approaches to a problem namely:

a. Absolution, ignores the problem and hopes it gone away,
which is seldom a good approach.
b. Resolution finds an acceptable solution to the problem
using common sense; resolution is usually better than
absolution, but the answer may not be a good one.
c. Solution is the third approach. It uses quantitative and
experimental methods to get the “best” answer under the
current conditions.
d. Dissolution as the fourth approach seeks to redesign the
system to eliminate the cause of the problem. This
approach, if possible and not too costly, is the preferred
one.
To solve a problem, five (5) conditions should exist namely:

1. What gap does exist between the current state (that is,
as we have it now operating), and the goal state (what it
actually is that we should be operating)?
2. An awareness of the gap, in which we recognize the
problems that creates that distance between what it is
now and what it should be?
3. The motivation to close the gap since the problem task is
quite important to someone and is of great importance –
which will allow them to devote time, resources and man-
hours, to resolve the problem task.
4. The ability to measure what the size and performance
gap is using performance metrics; Else, while there may
be no end to what revisions we can do – we may also
never attain/reach a solution. Thus, this measure informs
us of the severity of the task, and lets us to know when
such improvement has occurred.
5. The ability and resources to close the gap using available
tools, processes and techniques that have proven to be
successful in similar scenarios; we have the methodology
to solve the problem and the resources to carry out the
solution.
If one or more of these conditions is found to be missing, our

successfully solving the problem becomes quite unlikely. But,
if and where these conditions exist and are well-formulated
or defined, we can proceed with the problem-solving stages
or approaches. Thus, if/when a problem is ill-formulated, ill-
defined and ill-structured, the problem-solving framework
can provide useful insights to resolving it.
Thus, every problem/task is defined by its elements and their

relations. The right perspective and a formal description of a
problem (space and/or domain), every well-formulated, well-
defined and well-structured problem must meet all conditions
as mentioned above; while also allowing the problem-solver
to identify the following:
1. Define the problem state space that contains all possible
configurations and the relevant objects including some
impossible ones also.
2. Specify all the states that describes all possible situations
from which the problem-solving process may start. These
states are called the initial state(s).
3. Specify one/more state(s) that will be acceptable solution
to the problem called the goal state(s).
4. Specify the rules that describes the actions (operators)
available within the problem space (domain).
Thus, a problem can be solved simply by using the rules, in

combination with the appropriate search control strategy
to move through the problem space (domain) until a path
through the series of state(s) from the initial to a goal – is
found. This process is called a search; And it is fundamental
to problem solving process. Search is the general mechanism
that can be used when more direct methods is unknown. A
search provides the framework into which more direct
methods for solving subparts of a problem can be embedded.
Critical Thinking
The importance of Problem Solving (PS) can never be over-
emphasized as it directly and indirectly impacts our daily lives
and will continue to play critical roles in our way of living for
decades to come. Research have been dedicated to PS, with
attempts made by educationists and psychologists to make it
accessible to all in various degrees.
No wonder the Nigerian Universities Commission (NUC) has

now entrenched this course, as an educational policy at the
core of Computing Science(s). Wherever numerical problems
exist and is involved, from the simple 2+3 to the complex,
chaotic and numerical analysis – tools have been advanced
(from simple calculator to sophisticated computer programs)
have been developed to assist the problem-solver to resolve
such challenges more effectively and efficiently. Gone, are
the days of slide rule and logarithmic tables.
Even graduates today – experience great difficulty in solving

real life problems. Somehow, they cannot apply many taught
theories into practice; nor can they posit, formulate, reflect
or even theorize on practice. In fact, it is the human mind in
the end that has to be applied in a problematic situation and
solve the problem. Its capacity to solve the problem is
directly related to the knowledge stored in the mind. And
knowledge is a product of thinking. Thinking can vary from a
very simple and mundane thought, to a very sophisticated
and complex one. The nature of the problem dictates the
level of thinking.
Higher-order thinking can be conceptualized as a complex

mode that can generate multiple solutions. Such process can
involve abstraction, uncertainty, applying multi-goal/criteria,
reflection, and self-regulation. It also facilitates the transfer
of knowledge (i.e., use and transformation of already existing
knowledge in creating new knowledge). Conversely, lower-
order thinking may be considered as one that requires
minimum cognitive effort and it is algorithmic. In an attempt
by humans to increase the power of the mind, thinking is
information-processing; And computers by design accomplish
such feats using programs so that they are today – regarded
as thinking machines. Thinking can also be viewed as making
sense or judgements (and directly relates to critical thinking).
The complexities and dynamics of critical thinking is evident

from the fact that there are no globally-accepted definition.
But, many scholars have noted that critical thinking skills as
identified may include: (a) analysis and synthesis, (b) making
judgements, (c) drawing warranted conclusions, (d) decision
making, and (e) generalizations. Critical thinking is thus, a
prerequisite need to PS. When computers are used in the PS
situation, the need for computational thinking (CT) is another
prerequisite. CT broadly speaking, describes a set of thinking
skills that are integral to solving complex problems using a
computer.
Living in a knowledge-based, digital revolution era with the

continued advances in digital technology and informatics,
such evolution portends the constant progression and ever-
increasing trend that seeks to combine as well as leverage on
knowledge and technology to solve problems is becoming the
mode rather than the exception. This has continued to
advance the field of knowledge discovery in database (KDD).
Creativity and innovation driven by tacit knowledge, and
critical thinking driven by logic, making judgements, analysis
and synthesis and so on become the tools for problem
thinking and PS. If technology is added as another tool to the
process, then CT is a pre-requisite (and must transcend its
mere performing computations). CT frees a problem-solver’s
memory so that s(he) can concentrate on the essence of the
problem.
Discovering Knowledge Data

Knowledge Discovery in Data (KDD) is a systematic process
that identifies valid, potentially useful, and understandable
patterns from large amounts of data. It’s about transforming
raw data into valuable knowledge.
The KDD process typically consists of the following steps:

1. Data Cleaning – One truth is that real-life data are quite
often, messy and unstructured. So, the process or step
seeks to remove any inconsistencies, errors, or outliers
that might skew the results. Simply put, it removes noise
(unwanted data) and inconsistent data.
2. Data Integration – Data is often collected from multiple
sources, and each has its own format and structure. This
step merges all these data into a unified set, and ensures
there is consistency to also reduce redundancy or data
replication. Thus, it combines data from different sources.
3. Data Selection – not all data are relevant for analysis.
This step helps us to select the data-subset that pertains
to our specific objective and choose, only data relevant
for our analysis.
4. Data Transformation – Data may need to be summarized,
aggregated, or transformed to make the dataset, suitable
for mining.
5. Data Mining – It uses various algorithms and techniques,
patterns, trends, and relationships are extracted from the
data.
6. Pattern Evaluation – not all recognized data patterns are
useful, meaningful or interesting. This step helps filter
out the noise, ensuring only valuable insights are
considered.
7. Knowledge Presenting – This step helps visualize, report,
or make the knowledge accessible and understandable in
a proper format.
Figure 1.1. Knowledge Discovery in Database (Data Mining)
The Many Definitions of PS

1. Polya as the pioneer in PS – defines solving a problem
means finding a way out of a difficulty, a way around an
obstacle, attaining an aim that was not immediately
understandable.
2. Schoenfeld [14] notes that a problem is only a problem, if
you do not know how to go about solving it. A problem
that has no surprises in store, and can be solved
comfortably by routine or familiar procedures (no matter
how difficult!) it is an exercise.
3. Green and Gilhooly [5] PS in all its manifestations is an
activity that structures everyday life in a meaningful way.
This activity draws together the different components of
cognition. Thus, the kind of problem will dictate the type
of cognitive skill necessary to solve the problem: linguistic
skills are used to read about a certain task and debate
about it, memory skills to recall prior knowledge and so
on. Depending on the knowledge and thinking skills
possessed by a problem solver, what could be a problem
for one might not be a problem for somebody else.
4. Martinez‟s [4] PS can be defined simply as the pursuit of
a goal when the path to that goal is uncertain. In other
words, it is what you do when you do not know what you
are doing. In concluding, we adopt the following working
definition for this paper: PS is an activity that makes use
of cognitive or cognitive and physical means to overcome
an obstacle (problem) and develop a better idea of the
world that surrounds us.
5. Ojugo et al. (Ojugo et al., 2016) Many authors and
scholar agree that PS is a cognitive process, and findings
continue to suggests that PS is a product of a number of
cognitive processes and actions; Though, it is not actually
the processes that are of value; But, the successful action
that yields or leads to a solution of the problem.
Engaging in PS implies conscious and subconscious
thinking. And the type of problem will dictate the type of
thinking: The more complex a task, the higher the level
of thinking required.
6. Voskoglou et al. [21] Mathematics by its nature explores
and exploits PS at its core and essence. It does examine
the role of PS in learning and attempts a review of the
evolution in the emergence of a solution as a self-
sufficient science at the 1960‟s until today.
A rough chronology of this progress is as thus:
a. 1950‟s – 1960‟s: Polya‟s ideas on the use of heuristic
strategies in PS ([13], [16], etc). 1970‟s: Emergency of
mathematics education as a self – sufficient science
(research methods were almost exclusively statistical).
Research on PS was still based on Polya‟s ideas.
b. 1980‟s: A framework describing the PS process, and

reasons for success or failure in PS: „Expert performance
model‟ ([17], [18], etc). 1990‟s: Models of teaching
using PS, e.g. constructivist view of learning [19],
mathematical modelling and applications (e.g. see [20]
and its references), etc.
c. 2000‟s: While early work on PS focused mainly on

analyzing the PS process and on describing the proper
heuristic strategies to be used in each of its stages, more
recent investigations have focused mainly on solvers‟
behaviour and required attributes during the PS process;
e.g. „Multidimensional PS Framework‟ (MPSF) of Carlson
& Bloom [21]. More comprehensive models for the PS
process in general (not only for mathematics) were
developed by Sternberg & Ben-Zeev [22], by Schoenfeld
[23] („PS as a goal-oriented behaviour‟), etc.
What has been agreed by many authors ([5], [11], [12], etc)
is that a problem basically consists of three states: the
starting state, the goal state and the obstacles or a set of
available actions or strategies to move from the starting state
to the goal state. Matlin [12] states that the initial state
describes the situation at the beginning of the problem; the
goal state is reached when we solved the problem; and the
obstacles describe the restrictions that make it difficult to
proceed from the initial state to the goal state. The greatest
difference among problem solvers of the same problem tends
to lie in the third state, which might have infinite‟
possibilities, if the goal and the starting points are the same
for everyone.
Who is a Problem-Solver?
The person who has the problem or someone paid to solve
problems could be the problem solver. In the production
arena, a problem solver can/may be a manager, analyst, or
industrial engineer. Often, there are several problem solvers
working together to achieve or reach an optimal solution to a
case. And because problem solvers are people, they are not
infallible. Their personal beliefs, values, bias, and norms can
impact their judgment and disposition toward solving a
certain problem; And thus, affect the whole problem-solving
process. Whether a problem exists or not, is affected by a
person’s point of view, but recognizing that bias exists should
minimize its impact.
The knowledge and experience of a problem solver also

comes into play. If a person has more tools, that person has
a wider range of options for solving problems. Experience
teaches which tools to use in certain case and even helps in
inventing new ones or adopting old tools to new situations. If
a particular tool is not in a kit, you will not use it.
Problem Representation
A problem space or domain is best viewed or represented as
a directed graph. First, a graph is a structure that consists of
a series of nodes (vertices) existing in space such that each
node has relations with other nodes in the same space. The
relations details what binds or connects a node to another.
Thus, we have that the graph G consists of a set of vertices
V (or nodes) that are interconnected with a set of edges e
(arcs, links and relations) that allow these vertices to interact
and learn from each other. Thus, the graph is denoted as:
G = (v, e) (1)
In some cases, the relations are weighted. For example, the

relationship between a mother (Nkem) and her son (Eric)
as well as between a father (Arnold) and daughter (Elena),
which is based on dependence – cannot obviously not have
the same weight as that relationship between the son (Eric)
and his friend (Emma) as well as between the daughter
(Elena) and her friend (Elizabeth), which is based on respect.
Thus, such a graph G is denoted as:
G = (v, e, w) (2)
A graph is either be directed (noting that it depicts the flow

of data from one node as source to another as destination),
or undirected (when the flow can be in any direction). The
problem space is represented as a directed graph where
vertices represent search states, and the path represents
the operators that are applied to change the state(s). To
simplify the search – algorithms are modeled as logically and
programmatically convenient representation of the problem
space as a tree. This is often so, because the tree decreases
the complexity of a search at a cost through its capability of
duplicating some nodes on it that are linked numerous times
in the graph as in Figure 1.2(a). A tree is best be viewed as
a graph in which any two nodes are connected by exactly
one path such that there are no connection ends up as a
circle as in Figure 1.2(b).
Figure 1.1. (a) Graph (b) Trees
Formal Description to Problem Solving

Problem-solving is often characterized as a systemic search
through a range of possible actions to reach a predefined
goal or solution. The problem-solving methods can either be:
1. Special purpose are tailor-made solutions for a particular
task or problem as it often exploits very specific features
of the situation in which the problem is embedded.
2. General purpose is applicable to a wide range of tasks
and/or problems. An example is the means-end analysis
– a step-by-step, incremental reduction of the difference
between the current state and the final/goal state.
For Example: The Tower of Hanoi puzzle/game has the

story that there exist 1000-disks and three (3) pegs denoted
as A, B and C. The goal of which, is to move the rings/disks
from the pegs A-to-C such that no bigger disk-ring is placed
at any time on top of a smaller one as in Figure 1.3 below.
Solution:
- The puzzle involves a set of rings/disks of different sizes
that can be placed on 3-different pegs (A, B, C)
- Initial State: The puzzle starts with the rings arranged
as in Figure 1.3.
- Goal State: The goal is to move all the disk rings from
figure 1.3(a) to Figure 1.2(b)
- Condition: (a) Only the top-most ring on a peg can be
moved, (b) once moved, it can be placed on an empty
peg, and (c) no smaller ring shall be under a bigger one,
or no bigger ring shall be placed on a smaller one.
- States are all the possible situations encountered while
solving the task of moving the disks between the pegs.
- Problem Space are all the possible configurations of the
disk or ring on the pegs
Problem Description
A problem must consist of the following description as thus:
(a) its current state, (b) the actions that can transform one
state into another, and (c) the desired (goal) state that acts
as an acceptable final state of the problem. Thus, a problem
solver must be able to identify the following:
1. State space (can either be explicit or implicit) and should
describe everything that is needed to solve a problem.
2. Initial state is the state from which the problem starts.
3. Goal state is description of a desired, final state as either
be partial or complete conditions for which data/values
are assigned to states based on a variety of conditions.
Thus, the goal state has assigned to its variables, a set of
data values that fulfill the conditions of the desired state.
4. Operators are changes caused to the states. They are
simply actions that can transform one state to another.
Operators often consist: (a) pre-conditions that provide
or renders a partial description of the current state of the
task/problem that must be true in order to perform an
action, and (b) instructions tells us what to accomplish
as next state, when to act, and how to create that next
state. It is often advised that the operators should be as
general as possible to reduce their number(s).
5. Elements shows what is relevant to a task and it details
previous knowledge of the task as the starting point.
6. Restrictions are the quality of the solution(s) or ground-
truth as reached, which is either be optimal or complete.
This can thus, results to the following options: (a) finding
the shortest sequence, (b) finding the least expensive
sequence defining cost, and (c) finding any sequence as
quickly as possible.
7. Problem-Solving is finding the ordered sequence of
operators that transforms the current (start) state into a
goal (final) state that acts as an acceptable solution.
Problem Description of the 8-Queen Problem

It is a game of 8-queen puzzle as in Figure 1.4.
Figure 1.4. One solution of the 8-Queen Puzzle Problem
Solution:
- The puzzle involves placing 8-Queens on the chess-board
such that no Queen is found attacking another
- Problem/State Space: configuration N(Queens) = 8 on
chess board with only one queen per row and per column
- Initial State: configuration without queens on the board
- Goal State: configuration with N = 8 queens such that
no queen attacks any other on the chess board
- Operators or Actions
a. Condition: The new queen is not attacked by any
other queen that is already placed on the board.
b. Transformation: place a new queen in a particular
cell or square on the board
- Solution: one solution is as above in Figure 1.4 without
cost consideration.
The Tree Structure

A tree, simply put is a way of organizing related objects in a
hierarchical form. Objects are data, and data is anything that
we can manipulate. Thus, a tree is a type of data structure
where each element is attached to one or more elements
directly beneath it. The connections between these various
elements (or nodes) on a tree to describe the relationships
between the various elements is called branches. They are
often called inverted trees since their root is often expressed
at the top. The elements that have no other elements below
them are called leaves. A binary tree is also a special tree for
which each element has two-branches below it. A simple tree
is as expressed in Figure 1.5.
Properties of a tree is as thus:

a. A tree is a special case graph. Its topmost node is called
a root node, from which all operations on the tree begins.
b. A node has at most one parent. However, the topmost
root node has no parent.
c. Each node has zero or more child nodes below it
d. The node at the bottom-most level of the tree is called a
leaf node. The leaf node thus, has no child node.
e. A node that has a child node is called a parent node.
f. The depth of a node n is the length of the path from the
root node to the node. A root node is at a depth of zero.
g. All nodes have relationship with other nodes such that
the total number of connections going out from a node is
called an out-degree. Conversely, the total number of
connections coming into a node is called in-degree.
Figure 1.5. A simple unordered tree structure
The Stack Structure

Stacks are also a type of data structure in which the data or
objects are decked in a linear form. Thus, accessing such
data requires that we explore and maintain either the order
of last-in-first-out (LIFO) or the first-in-last-out (FILO)
respectively. In Computing Science, the orders are known as
linear linked list. The stack implements or maintains a LIFO
order with its object/data piled up in a sequence of one atop
the other as in Figure 1.6(a).
Figure 1.6(a) Stack

Properties of the stack are:
a. Insert and delete are made at only one end called the top
b. Any intermediate element a[i] is on the top of element
a[i+1] where 1 < i ≤ n.
c. All operations takes place at the top of the stack.
d. The Pop operation removes a data from the top of the
stack; while, the Push operation inserts or adds a data
item to the top of the stack as in Figure 1.6(b).
Figure 1.6(b) Insert / Delete
The Queue Structure

Queues just like stacks, are also a type of data in linear form,
and accessing it means to maintain the first-in-first-out
(FIFO) order as in Figure 1.7(a). A queue restricts how data
are added to and removed from the list as in Figure 1.7(b).
Figure 1.7(a) Queue
Properties of the queue are:

a. A queue has two-ends.
b. All insert (enqueue) takes place from one end called the
rear or back; While, all delete (dequeue) takes place from
the other end called the front
c. If a queue has a[n] as the rear element; then, a[i+1] is
behind a[i] where 1 < i ≤ n.
d. All operations takes place at one end of the queue or the
other end. A dequeue operation removes the data at the
front of the queue. An enqueue operation adds data to
the rear of the queue.
Figure 1.6(b) Dequeue / Enqueue
Searching Techniques
Searching is a process of locating a given data value, item or
object position in a linked list (or an array) or tree from a list
of known value(s). searching is the process of finding a value
in a list of values. A search is successful if the object value
being sought for or searched is found; else, it is said to be
unsuccessful. Typically, a search answers the True or False
as to whether the value search is present or not. Also, there
as scenarios where the search conditions may be modified to
return the position where the item or value can be found.
Thus, there are basically two (2) search techniques explored
namely linear search and binary search.
The Linear Search – is a simple search algorithm, that is
sequentially run to search over all available elements on a
list, one by one. It linearly searches through a tree or array
of elements till the desired element is not found in sequential
order. Each and every element of the list is checked against
the goal object; And, where it is found – the particular value
item is returned; Else, the search continues till the end of the
data collection. Its search begins from first element on the
tree/list, and continues until the desired element is found or
the end of the file is reached. Linear Search is often applied
to unordered list when there are fewer elements in a list.
Basic Working Idea of the Linear Search:

a. Read the goal (search) element to be searched
b. Initially compare, the search (goal) element with the first
element in the list. If both values are matched, then
display "element is found"; And, terminate function.
c. If both are unmatched, then compare search element
with the next element in the list.
d. Repeat steps until the search element is compared with
all the elements in the list.
e. Where the last element in the list has been searched and
no element in the list is matched with the search
element, then display "element is not found"’ And,
stop or terminate the function.
Algorithm Listing for the Linear Search Algorithm

Linear Search (A, x)
// Given an array A[i, x] and x represents the number of elements
Set found to false
Set position to -1 && Set index to 0
While found is false and index < x
if A[index] is equal to search value then
found = true
position = index
endif
Add 1 to index
end while
return position
Pseudocode Listing for the Linear Search Algorithm

Procedure linear_search (list, value, x)
int index = 0;
// Position for search
int position = -1;
// Indicate whether the value is found
bool found = 0;
while (index < x && !found)

{
if (list[index] == value
{
//The value is found
Position = index;
}
Index++;
}
return position;
}
end procedure
Example: Suppose in a list of 10-elements, we are to search

for the value 39. Our goal element is X = 39 (index A[4]).
Step 1: It compares the x with first element located at index

0. Element is not matched then it moves to the next element.
Step 2: It compares x with next element located at index 1.
Element is not matched then it moves to the next element.
Step 3: It compares x with next element located at index 2.

Step 4: It compares x with first element located at index 3.

Step 5: It compares x with first element located at index 4.

Element is matched – and the desired goal (search) element
is found at location 4. The process is then stopped, and the
function is terminated. Then, the function returns the
‘element is found’ information.
Note: If the function had gone through to the last element

or reached the end-of-file – and the search (goal) element
was not found or does not match any value in the array list,
then the function will display ‘element not found’ message.
And thereafter, it will terminate the function.
Complexity analysis: Time complexity of linear search in
best case is O(1) and in average and worst case is O(n).
Its merits are: (a) they are simple, easy to understand and
implement, (b) they are very resource efficient, (c) does not
require copying/partition of arrays, (d) they are memory
efficient, (e) can be used on both unsorted and sorted data,
(f) does not require the data in the array to be stored in any
particular order. Conversely, its demerits are: (a) has a very
poor O(n) general efficiency. That is, the performance of the
algorithm scales linearly with the size of the input, and (b)
they are very slow and time consuming.
Binary Search – is the most popular search as it is based

on the divide-and-conquer model technique. It first sorts
the array list either in ascending or descending order. In this
method firstly find the middle element and to search an
element compare the value with the elements in the middle
position of the array. If the value is matched, then search is
successful otherwise list is divided into two-halves (one from
the first element to the middle element i.e. first half or lower
half and second half or upper half from middle to last
element). If the value is less than the middle element, then it
must lie in the lower half of the array and if it's greater than
the element then it must lie in the upper half of the array.
We repeat this procedure on the lower (or upper) half of the
array. Binary Search is useful when there are large numbers
of elements in an array.
Basic Working Idea of the Linear Search:

Let X be the element to be searched in an array A[0 – (n-1)].
Thus, it proceeds as follows:
a. It selects the element to be searched
b. It finds the mid-value of an array list using the formula:
mid = (low + high)/2. Here, low refers to lower bounds
of an array (i.e. 0) and high refers to upper bounds of
the array (i.e. n-1).
c. If the element to be searched, is the middle element then
the search terminates’ Else, it continues.
d. If the element to be searched is less than the middle
element then the search is performed in left sub array
and high is set to mid-1.
e. Otherwise, if the element to be searched is greater than
the middle element then the search is performed in right
sub array and low is set to mid+1. In this way the
problem size is reduced to half after every comparison.
f. It repeats same process until we find the search element
in the list, or until the sub-list contains only one element.
g. If that element also does not match with search element,
then display ‘element not found in the list!’ and terminate
the function.
Pseudocode Listing for the Binary Search Algorithm

Procedure Binary_Search (a, i, n, x)
A  sorted array: n  size of array: x value to be search
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
exit: x does not exists.
set midpoint = lowerBound + (upperBound – lowerBound) / 2
if A[midpoint] < x
set lowerBound = midPoint + 1
if A[midpoint] > x
set lowerBound = midPoint – 1
if A[midpoint] = x
exit: x is found at location midPoint
end while
end Procedure
Algorithm Listing for the Binary Search Algorithm
BinarySearch (a, i, n, x)
//Given array a[i: n] of elements in nondecreasing order, 1 ≤ i ≤ J, determine whether
//x is present, and if so – return j such that x – a[j]; else return 0.
{
if (n = i) then // if small(P)
{
if (x = a[j]) then return n;
else return 0;
}
else
{ //reduce P into a smaller sub-problem
mid = [(i + n/2)];
if (x = a[mid]) then return mid;
else if (x < a[mid]) then
return BinarySearch(a, i, mid - 1, x);
else return BinarySearch(a, mid+1, n, x);
}
}
Complexity analysis: Time complexity in best case is O(1),

and in the average and/or the worst case is O(log(n)).
Its merits are: (a) they are more efficient than the linear
search, (b) every time it makes a comparison and fails to find
the desired item, it eliminates half of the remaining portion
of the array that must be searched, and (c) they use random
access to the data but linear search only requires sequential
access. Conversely, their major demerit is the binary search
process must only be performed on sorted list.
Example: Suppose in a list of 10-elements, we are to search

for the value 72. Our goal element is X = 72
Step 1: With X as 72 and because the list has been sorted –
it performs midpoint value computation. Note: the indexes
are low=0, and high=9. Thus, midpoint = (0+9)/2 = 4.
Step 2: As X > mid, so low become mid+1; and high remain

the same. So, next computation indexes low=5, and high=9.
Thus, midpoint = (5+9)/2 = 7.
Step 3: As X > mid, so low becomes mid+1 and high remain

the same. Thus, we have low=8 and high=9, mid=(8+9)/2
= 8. Element is matched, and search terminated at 3-steps.
QUESTIONS
Multi-Choice:
1. Which of the following is not a required condition for binary search algorithm?
a) The list must be sorted,
b) Direct access to the middle element in any sub list,
c) A mechanism to delete and/or insert elements in list.
d) Number values should only be present
2. The Average case occurs in linear search algorithm.

a) when item is somewhere in the middle of the array
b) when item is not the array at all
c) when item is the last element in the array
d) Item is the last element in the array or is not there
3. Binary search algorithm cannot be applied to.

a) Sorted list b) Sorted Binary tree c) Sorted Linear Array d) Pointer Array
4. Complexity of linear search algorithm is:

a) O(n) b) O(log n) c) O(n2) d) O(n log n)
5. To find the location of an item in a set of items is ___

a) Discovering b) Finding c) Searching d) Mining
6. Worst-case time complexity of linear search algorithm is?

a) O(1) b) O(n) c) O(log n) d) O(n2)
True/False Choice
1. Finding the location of a given data value in a set of items is called searching.
2. The binary search is much more efficient than the linear search.
3. A Linear search algorithm or function can be used for large array list elements.
4. Complexity of binary search algorithm in worst and average case is O(n).
5. Comparisons are necessary and sufficient for computing both the minimum and
the maximum is 3n-3/2.
Exercises
1. Given the array (24, 13, 56, 35, 46, 27, 78, 48)
a. Use the binary search algorithm
Write the BinarySearch program for the answer to Q1(a)
2. Given the array (24, 13, 56, 35, 46, 27, 78, 48)
a. Use the linear search algorithm
b. Write the LinearSearch program to answer to Q2(a)
3. Define searching. Explain different types of searching.

Chapter Two
LOGIC GATES
2.0 DATA REPRESENTATION

Digital computers recognize data as electrical pulses or
signals, represented as two-state conditions using 1 and 0
respectively. They are arranged in various combinations to
represent numbers, alphabets and symbols in the system.
The smallest unit of data that can be manipulated by the
computer is called a bit, seen as a single binary value 1 or 0.
Computers manipulate data as a group of eight bits called
byte. Gates allows digital systems to perform complex tasks
with the interconnection between its components designed to
carryout logic laws based on mathematical rules known as
Boolean Algebra, which has led an increased productions of
digital systems due to their reliability in the use of 1/0 states.
Data and instructions as manipulated by the computer can

either be numeric or non-numeric and are represented as
binary values of 0 and 1 called bits making the computer a
two-state machine. A good knowledge of number systems
helps us to understand how the computer is programmed.
Also, to know also how the system is made from two-state
components and used to manipulate other number schemes.
For example, if we have:
7 * 1000 + 3 * 10 + 4 * 0.1 + 3 * 0.001
Represented as: An * bn + An-1 * bn-1 + … where b is base

and A is the number system digit. The system’s advantage is
that only few different symbols are required to represent any
number no matter how large or small. Symbols 0, 1, 2, 3 are
represented by quantities zero, one, two, three etc.
NUMBER SYSTEMS: OVERVIEW
Number systems use a finite number of symbols, with each
symbol called a digit and is used to denote a quantity. The
numbers of these distinct symbols are known as the base or
Radix. To denote quantities larger than those associated with
the individual symbols, the digits are juxtaposed to form a
number. Hence the relative position of a digit within the
number is associated with a weighting factor. There are four
major number base systems namely Decimal, Binary, Octal
and Hexadecimal number systems.
Decimal system requires that data be represented with

symbols (0 – 9). It evolved from natural counting ability via
the use of fingers in which the symbols 0, 1, 2, 3 and so on
are represented with quantities one, two, three etc. Digital
systems convert these symbols into its binary equivalence to
aid data manipulation and storage. Its major advantage is
that it makes arithmetic tasks simple; while its disadvantage
is that systems constructed from it will find it hard to
differentiate correctly between ten levels of switch used to
represent the various bits, making the system unreliable.
Binary System is used in digital equipments for circuit

design to improve reliability – because it uses two-states “0
and 1” to represent data as voltage pulses of either a “low =
0” and “high = 1”. Its highest value is 1 and the lowest is 0;
hence, it is called a two-state system. A two-state system
represents characters, numbers and alphabets using logic
states 0 and 1 in that each state will be used to represent a
different digit and the system must have as many states as
there are digits in the number system.
Octal System is used in computer microprocessor and with
some computer-based controllers. One of the particularly
useful properties of this system is the simple conversion
technique from binary to octal system and vice versa,
because it has a base of 8, which is 23 = 8. The system has
its lowest character as 0 and highest as 7.
Hexadecimal System is used by microprocessors as their
design and internal construct today relies on this system.
Just like the octal system, their useful property is their
conversion from binary to hexadecimal and vice versa as
they are used in computers to represent alphanumeric
symbols and they have a base of 16, which is 24 = 16.
Table 1.1 shows the different number systems
Decimal Binary Octal Hexadecimal
1 1 1 1
2 10 2 2
3 11 3 3
4 100 4 4
5 101 5 5
6 110 6 6
7 111 7 7
8 1000 10 8
9 1001 11 9
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F
16 10000 20 10
17 10001 21 11
18 10010 22 12
19 10011 23 13
20 10100 24 14
For interaction between the number schemes, the computer

performs conversion between the various schemes as thus:
Decimal to Binary Conversion They are converted using

either to the power of 2 or divide by the number 2. For
example if we are to convert the number 6, which is in base
10 (written as 610) to binary, our solution is:
Divisor Number Remainder
2 6
2 3 0
2 1 1
0 1
Binary To Decimal Conversion is as thus:

Position 1st 2nd 3rd 4th 5th 6th 7th 8th 9th
Weight 20 21 22 23 24 25 26 27 28
Answer 1 2 4 8 16 32 64 128 256
Converting the value 11011012 to decimal is as follows
1. Space out the numbers indicating their positional weight
2. Place the answer to the various weights
3. Sum of all the weights together and write it out as follows
7th 6th 5th 4th 3rd 2nd 1st

1 1 0 1 1 0 1
1*2 + 1*2 + 0*2 + 1*2 + 1*2 + 0*2 + 1*20
6 5 4 3 2 1
64 + 32 + 0 + 8 + 4 + 0 + 1 =10910
Binary To Octal is the reverse of the former and step for its
conversion. Example 1011101 = 1,011,101 → 1, 3, 5 = 1358.
Octal To Binary It is easier to convert because we know

that octal is 23. Hence, we take the long sequence of binary
given to us and group them in bits of 3 such that each digit
is converted to its binary equivalent. The binary characters
then form the binary equivalent. For example:
Octal: 1: 5: 7: 6
Binary: 001: 101: 111: 110
Binary equivalent of 15768 is 11011111102

Hexadecimal to Binary Hexadecimal is 24 – so we take
long sequence of binary and group them in bits of 4 such
that each digit is converted to its binary equivalent. The
binary characters then form the binary equivalent.
Binary Hexadecimal
1: A 1A
01: 1010
8: 3 83
1011: 0011
Binary Addition There are four rules to binary addition:

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 and 1 + 1 = 2 but written as 0 carry 1
For example 109 + 92 = 201
11011012 = 10910
+10111002 = 9210
-------------------------
100010012 = 20110
----------------------------
Binary Subtraction For example, just like addition also

starts from the least significant bit (LSB) for example,
1 1 0 1 1 0 12 = 10910
- 1 0 1 1 1 0 02 = 9210
-----------------------------
0 0 1 0 0 0 12 = 1710
------------------------------
DIGITAL SYSTEMS
Digital systems are more reliable due to the ON-OFF states
and operation, accomplished via the aid of semiconductor
materials such as diode and transistor packages. These
elements are connected together to help perform diverse
tasks using logic laws known as Boolean Algebra. This
algebra was formulated in 1847 by George Boole based on
two-states “True/False” to aid mathematical method used for
systems containing two-state elements, based on two
possible values 0 and 1. It was later used for the design and
implementation of modern digital equipments. The algebra
allows any symbols such as A, B or C to have one of two-
allowable states namely “True/1 or False/0”.
Logic – is the science of arguments or is regarded as the

science of reasoning by formal method. Any statement in a
logical context is a declaration, verbal or written that is either
true or false, but never both.
Arguments – Any statement is regarded as an argument.

Example: (a) All girls are soft minded (b) All airplanes fly
Arguments are meant to help the thinker build reasonable
ways of arriving at conclusions, drawn from intelligent point
of view, devoid of rancour and prejudice. There are two
types of arguments namely inductive and deductive.
1. Inductive Reasoning – are methods of arriving at
conclusions that extracts and discovers general laws from
facts, allowing the thinker to start from a particular case
and extend the argument to a more general case. This
we refer to as forward chaining. For example, we can
state these arguments as follows:
a. Dupe is dirty. Hence, all girls called dupe are dirty.
b. Arnold is tall. Hence, those called Arnold are tall.
2. Deductive Reasoning – are methods of arriving at

conclusions drawn from the facts that the thinker starts
from the general laws to a more specific case. This is a
direct opposite of the inductive principle and can also be
referred to as backward chaining. For example: -
a. All express roads are dual carriage roads. Hence, the Benin –
Lagos road is a dual carriage road.
b. American countries are rich. Mexico is a rich country.
Propositions – any simple statement, which can either be
true or false. For example: -
a. Benin city is Edo State of Nigeria – True
b. Samuel’s father is pregnant – False
We must note that statements that propose questions and

those used to signify exclamations are not propositions
because they can neither return a true or false value. E.g. (a)
What is your name? (b) Are you crazy!
Compound Statements – Two or more statements can be

combined to form a compound statement. They are very
useful especially when we need to make the proper and
accurate decisions. These statements are combined using
negation, disjunction and conjunction.
a. Disjunction – is when two proposition are joined by the
OR operation (Union or addition) of the two statements.
If two statements Y and Z are as thus:
Y = The sun is too hot today and Z = It will rain today
Their disjunction/OR is given by the table 2.1:
Y Z G
True True True
True False True
False True True
False False False
Hence, the disjunction of Y and Z produces statement G:

“The sun is too hot or it will rain” such that G is True
when any of the statement is true – and False only when
both statements are false. Sometimes, the context in
which the OR statement differs. For example, a pregnant
woman can give birth to a single, twin etc. It can be a
girl, boy or both. This is called inclusive OR. But, if it is
used so that only one statement is correct, it is called
exclusive OR. For example, you are either a man or a
woman. You can never be both.
b. Conjunction – is when two statements are joined by an
AND operation. Like the OR, if we have two statements:
Y = The sun is too hot today and Z = It will rain today
Y Z G
True True True
True False False
False True False
False False False
Conjunction of Y and Z produces G, which states that:

“The sun is too hot and it will rain today”. G is True, only
when both statements are true; otherwise False when
any of the statement is false as in table 3.2:
c. Negation – If a statement Z is negated, it produces

another statement that is false when Z is True; or True
when Z is false and denoted by NOT Z as in table 3.3
Z = “I am singing and dancing right now”. Hence, NOT Z
= “I am not singing and dancing right now”
Z NOT Z
True False
False True
A A B
Disjunction Conjunction
Fig 2.1 (a) and (b) shows the disjunction and conjunction
2.1 BOOLEAN ALGEBRA THEOREM
Boolean postulates and its fundamental properties are seen
in table 3.4 below with its dual form.
Minterm Maxterm Postulate
A+B=B+A A.B = B.A COMMUTATIVE
A + (B+C) (A+B) + C (A.B) . C = A. (B .C) ASSOCIATIVE
A+(B.C)= (A+B).(A+C) A.(B+C) =(A.B) +(A.C) DISTRIBUTIVE
A+0= A A.1 = A IDENTITY
A + (A’) = 1 A. A’ = 0 COMPLEMENT
(A.B)’ = A’ + B’ (A.B) + (A + B)’ = 1 DE MORGAN
A+1=1 A+0=0 IDEMPOTENCE
Truth Tables provide a list of all possible input-states and

its corresponding output that can result from each state of a
logic gate. It specifies the circuit’s behaviour via the use of
Boolean theorems, applied to the gate since there are only
two possibilities about a statement: true or false. This is
because a statement can never be partly true or partly false.
If true, it has a 1 value, else 0 if false.
2.2 SEMICONDUCTOR GATES

Gates are two-state systems whose input and output takes
only one of two-allowable states representing binary voltages
0/Off and 1/On states. Systems constructed from such two-
state elements are known as logic circuits. These include
switches, decoders amongst others. Gates directly employ a
set of mathematical rules used to describe the logic circuit’s
behaviour, which either allows or not allow the flow of
electrical signals along the wire paths referred to as opening
or closing of logic gate paths. Its advantages are:
1. They are exceedingly small and require little power to operate
2. They are extremely cheap
3. They are much reliability because of their binary operability.
4. They are constructed from two-state materials and are combined into
a network to form systems such as flip-flops, registers etc
5. Operate at higher speed for a very long time without failure
The behaviour of a circuit is determined by the gates
implemented on that circuit, usually constructed from a truth
table that describes the output produced by the circuit. Each
circuit has its own unique truth table and the gates used for
their implementation are as follows:
OR GATE can have any number of inputs with just one

output, which produces a 1 output when any of the input is a
1; otherwise it produces a 0 output when all the inputs are 0
as seen in table below and figure 2.2.
Input A Input B Output
0 0 0
0 1 1
1 0 1
1 1 1
A C=A+B Figure 2.2

B
AND GATE just like the OR gate can have any number of
inputs with just one output. It produces a 0 output unless all
its inputs are 1. Hence, it gives an output of 0 unless all
inputs are 1 in which case the output is 1 as in figure 2.3.
A C = A . B = AB
Figure 2.3
B
Input A Input B Output

0 0 0
0 1 0
1 0 0
1 1 1
NOT GATE has a single input and output as its function is to
produce an output directly opposite of whatever input was
sent through it. Hence, there are only two states
Input Output
1 0
0 1
A A’ Figure 2.4
NAND GATE is same as an AND gate plus an Inverter so

that the gate performs an AND-NOT task on its inputs –
giving an output that is directly opposite to an AND output.
Figure 2.5
Input A Input B AND NOT = OUTPUT

0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0
NOR GATES performs a NOT-OR operation on any number

of inputs – giving an output opposite to that of the OR gate
as seen in figure 2.6 below.
Figure 2.6
Input A Input B AND NOT = OUTPUT

0 0 0 1
0 1 0 1
1 0 0 1
1 1 1 0
EXCLUSIVE-OR GATE (XOR) produces an output of 1
when either of the input is a 1. Such a circuit excludes the
case that both inputs are 1, as it is a two input circuit. The
XOR function is only defined by two inputs and its results are
same for whatever combinations as in figure 2.7.
C=AB
Figure 2.7
Input A Input B Output C

0 0 0
0 1 1
1 0 1
1 1 0
These gates are used for designing and manufacturing of

circuits and also in the development of diodes, transistors
and integrated circuits (IC) supplied with two or more input
gates. Circuits produced from such these are usually
classified into Combinational and Sequential.
A combinational logic is any logic circuit whose steady

state output values depends solely on its steady state input
so that the specific outputs obtained depends on the given
input. E.g. adders, decoder, encoder, multiplexers, etc. The
major characteristics for combinational Logic includes:
a. No output state depends on another output state.
b. Input states that have occurred have no influence on its behaviour.
c. The order of the input does not affect the final output.
d. Actual level of the particular output at any time depends on the Logic
State present at all of the inputs at that instant or time.
e. As input changes, output changes also immediately to the level which
corresponds to the new input.
Sequential circuit consists of the combinational logic and
storage elements. The state of the storage elements depends
on the present and its internal state. Hence, its output state
depends on current inputs and previous output. Examples
include flip-flops, multivibrators etc.
2.3 DESIGN AND IMPLEMENTATION

There are several ways employed in solving problems
associated with circuit design and implementation. Hence, it
becomes apparent that a logic designer must define some
parameters when faced with such design task. Hence, he
must determine the circuit’s specification or the output as
expected of the circuit. The best way to present this
specification is via truth table that attempts to reproduce the
detailed circuit design and the exact description of the
circuit’s behaviour.
To implement a circuit, we need basic steps such as:

▪ Development of a truth table
▪ Determine the circuit specifications
▪ Equivalent Circuits and design of the Logic circuit
Truth Table Development Gives designer a pictorial

representation of what is expected of the circuit behaviour.
Truth tables are the first systematic approach in designing a
circuit, with initial specifications represented, general rules
are formulated for the construction of the truth table to give
the designer an insight to the number of inputs and outputs
that must be obtained by the logic circuit clearly stating all
possible combination of the input states for the circuit.
Determine Specifications Suppose we have three simple

two-state switches connected to supply inputs to a logic
circuit with a single output, which controls a lamp and the
circuit operation is such that changing the position of any of
these switches changes the condition of the lamp by going
off and on, and vice versa. To design a truth table for this
logic circuit behaviour, we note that because the number of
input and output for the circuit have already been stated and
determined, many other features must be considered to
produce the desired outcome and they are:
✓ Input specifies current, properly labeled or the states of all inputs
conditions represented by a 0 or 1.
✓ Output specifies the outcome of the input states (as combined under
the stipulated gate, which having an output of 1 – causes the lamp to
be lit or an output of 0 – causing the lamp not to be lit.
✓ Starting Positions specification does not indicate the output of any
condition, although it states how the circuit must change when any
input changes are made. For this reason, it is best for the designer to
choose the output for a single set of input. The output results from
the gate in use.
Equivalent Circuit/Implementation It is appropriate for

the designer to know which gates to use in order to produce
the required circuit’s behaviour. Most integrated circuits are
constructed using NAND gate – because they are easier and
less costly to manufacture than other gates. Hence, any
circuit can be constructed from NAND gates if only we know
the equivalent gates that make up the circuit.
Fig 2.8a has that NAND gate gives same output as an Inverted OR gate
Figure 2.8b has that NOR gate gives same output as an Inverted AND gate
Implementation means to design a circuit as expressed in the

Boolean form. If we have: L = A + B’C as in Figure 2.9.
L = A + B’C
A
B B’C
L = B’C + ABC’ + A’C is shown figure 2.10.
B B’C
C L = B’C + ABC’ + A’C
ABC’
A
A’C
2.5 DUALITY
A network represents the interconnection of various gates,
which closely corresponds to the hardware components with
lines that connects the gates in the logic diagram seen as the
physical wires connecting the devices on the IC board. Each
Boolean expression is a corresponding operation with a gate
symbol. But most combinational networks are implemented
and designed using NAND and NOR gates, since they contain
more than one variable, combined together based on laws.
Thus, each expression there is a logic diagram that causes a
one-to-one relationship.
Duality simply means obtaining the same values for a

reverse operation. Take the AND operation as an example, if
we take all the 0s and change them into 1s and take the 1s
and change them into 0s, we get the output of the OR gate.
The same for the NOR and NAND operations. The postulates
that have so far been presented are both in dual forms (that
is, they are in pairs). They reflect the summitry of the “OR
and the AND” operations. Hence, expressions in dual form
are derived by simply replacing the occurrence of “.” by “+”,
“OR by AND” and 0 by 1 as in the postulate table.
With duality, we see that the AND circuit with a value logic 1,
becomes an OR circuit with logic 0 – and vice versa. Rules of
duality are often listed in the order that illustrates the duality
of the algebra, which allows the circuit designer to work with
two sets of values by listing the various states that the input
to the logical network can take, as well as the desired output
for each input condition. The logical expression is thus
divided up into two sets of standard values (minterm and
maxterm) known as the canonical forms, used to express
any combinational logic.
Minterms are obtained by performing the AND of several

OR operation based on the different variables given to obtain
a 1 output. By complementing those variable whose values in
the truth table is 0 so that it leaves the variable with a values
1 and uncomplementing those whose values are 1 such that
its logical product produces a 1 instead of a 0. For example,
such truth table for a 3-variable is shown below using Z:
Z = A’.B’.C + A’.B.C’ + A.B’.C’ + A.B.C
A, B and C are the variables. The fourth column represents
the minterm, which lists AND terms of the input variable to
give a 1 output. Variables with 0 values are complemented to
give 1; while those with a 1 are left uncomplemented. For
example, in row 1 – A, B and C are complemented so that
their AND gives us a 1 value. In row 2 – we have that A and
B are complemented with C not complemented to give 1. The
last column Z is the output, to indicate those minterms that
appear in the expression. Hence, the circuit behaves in such
a way that at places where the minterm is 1, Z is 1 and the
circuit is high; while at other places where the output is 0 –
the circuit is low. This is best understood as with the help of
Karnaugh’s map. We can also write the minterms as:
Value A B C ABC Minterm Output Z
0 0 0 0 000 A’.B’.C’ 0
1 0 0 1 001 A’.B’.C 1
2 0 1 0 010 A’.B.C’ 1
3 0 1 1 011 A’. B.C 0
4 1 0 0 100 A. B’. C’ 1
5 1 0 1 101 A. B’. C 0
6 1 1 0 110 A. B. C’ 0
7 1 1 1 111 A.B.C 1
Maxterm is same as product of all sum expressions. Since

an OR is the opposite of the AND, we simply change all the 0
outputs to 1 and changing the 1s to 0. Hence, using the
same table in our previous example as in the table below:
Value A B C ABC Maxterm Output Z
0 0 0 0 000 A+B+C 0
1 0 0 1 001 A+B+C’ 1
2 0 1 0 010 A+B’+C 1
3 0 1 1 011 A+B’+C’ 0
4 1 0 0 100 A’+B+C 1
5 1 0 1 101 A’+B+C’ 0
6 1 1 0 110 A’+B’+C 0
7 1 1 1 111 A’+B’+C’ 1
From the table, the Maxterm is as thus:

Maxterm (0, 3, 5, 6) = (A+B+C)(A+B’+C’)(A’+B+C’)(A’+B’+C)
2.6 KARNAUGH’S MAP

Algebraic simplification of logic expression can sometimes be
difficult and expertise is needed to effect the changes
properly in circuit design. Hence, Karnaugh’s map provides a
graphical method for simplifying Boolean expressions so that
it is arranged in boxes, each of which represents a Minterm
combination of the variables given by the truth table. The
number of boxes for each map depends on the number of
variables in the given expression. A two-variable expression
map will require four (2n), where n = 2, to give us four boxes
or cells. The steps are as follows:
a. Convert all terms into their Minterm forms and plot table.
b. Draw the map with appropriate number of boxes or cells and place 1
in the cells that correspond to each minterm in the expression and
leave the cells with no corresponding values.
For example, construct the map for L = A’B + A’B’ + AB

The truth table below shows Minterms obtained.
Value A B Minterm
0 0 0 A’B’ = 1*1 = 1
1 0 1 A’B = 1*1 = 1
2 1 0 AB’ = 1 * 1 = 1
3 1 1 AB = 1*1 = 1
A 0 1 A 0 1
B B
0 00 10 0 A’B’ AB’
1 01 11 1 A’B AB
Place 1 in boxes of L = A’B + A’B’ + AB as thus:

A 0 1 A 0 1
B B
0 A’B’ AB’ 0 1
1 A’. B AB 1 1 1
Adjacency: Karnaugh’s map has that the cells in each map

are assigned a minterm value. Each cell is arranged such that
their geographical location faces or is adjacent to other cells.
It helps with grouping minterms for finding a minimal circuit
as given by the expression.
A 0 1
B
Minterm A B Adjacent to
0 0 0 1, 2 0 0 2
00 10
1 0 1 0, 3
2 1 0 0, 3 1 1 3
3 1 1 1, 2 01 11
For a 3-variable, the table holds as thus:

Minterm A B C ABC together Adjacent to
0 0 0 0 000 1, 2, 4
1 0 0 1 001 0, 3, 5
2 0 1 0 010 0, 3, 6
3 0 1 1 011 1, 2, 7
4 1 0 0 100 0, 5, 6
5 1 0 1 101 1, 4, 7
6 1 1 0 110 2, 4, 7
7 1 1 1 111 3, 5, 6
AB
C 00 01 11 10
0 0 2 6 4
000 010 110 100
1 1 3 7 5
001 011 111 101
For a 4-variable, the table below holds:

Minterm A B C D ABCD Adjacent to
0 0 0 0 0 0000 1, 2, 4, 8
1 0 0 0 1 0001 0, 3, 5, 9
2 0 0 1 0 0010 0, 3, 6, 10
3 0 0 1 1 0011 1, 2, 7, 11
4 0 1 0 0 0100 0, 5, 6, 12
5 0 1 0 1 0101 1, 4, 7, 13
6 0 1 1 0 0110 2, 4, 7, 14
7 0 1 1 1 0111 3, 5, 6, 15
8 1 0 0 0 1000 0, 9, 10, 12
9 1 0 0 1 1001 1, 8, 11, 13
10 1 0 1 0 1010 2, 8, 11, 14
11 1 0 1 1 1011 3, 9, 10, 15
12 1 1 0 0 1100 5, 9, 12, 15
13 1 1 0 1 1101 5, 9, 12, 15
14 1 1 1 0 1110 6, 10, 12, 15
15 1 1 1 1 1111 7, 11, 13, 14
AB 00 01 11 10
CD
00 0 4 12 8
0000 0100 1100 1000
01 1 5 13 9
0001 0101 1101 1001
11 3 7 15 11
0011 0111 1111 1011
10 2 6 14 10
0010 0110 1110 1010
Example 1: Plot a map for L = ABC + A’B’C + A’B’C’

Value A B C Minterm
0 0 0 0 A’B’C’ = 1*1*1 = 1
1 0 0 1 A’B’C = 1*1*1 = 1
2 0 1 0 A’B C’ = 1*1*1 = 1
3 0 1 1 A’BC = 1*1*1 = 1
4 1 0 0 AB’C’ = 1*1*1 = 1
5 1 0 1 AB’C = 1*1*1 = 1
6 1 1 0 ABC’ = 1*1*1 = 1
7 1 1 1 ABC = 1*1*1 = 1
A
B 0 0 1 1
C 0 1 1 0
0 A’B’C’ A’BC’ ABC’ AB’C’

0 2 6 4
1 A’B’C A’BC ABC AB’C

1 3 7 5
A
B 0 0 1 1
C 0 1 1 0
0 1
1 1 1
Example 2: Plot L = ABC’ + AB’C’ + A’BC + AB’C
A A
B 0 0 1 1 0 0 1 1
C 0 1 1 0
B 0 1 1 0
C
0 A’B’C’ A’BC’ ABC’ AB’C’ 0 1 1
0 2 6 4
1 A’B’C A’BC ABC AB’C 1 1 1

1 3 7 5
Plot L = ABC’D + ABCD + A’BC’D’ + AB’C’D’ + A’B’C’D’

No A B C D Minterm L
0 0 0 0 0 A’ B’ C’ D’ = 1*1*1*1 = 1 1
1 0 0 0 1 A’ B’ C’ D = 1*1*1*1 = 1 0
2 0 0 1 0 A’ B’ C D’ = 1*1*1*1 = 1 0
3 0 0 1 1 A’ B’ C D = 1*1*1*1 = 1 0
4 0 1 0 0 A’ B C’ D’ = 1*1*1*1 = 1 1
5 0 1 0 1 A’ B C’ D = 1*1*1*1 = 1 0
6 0 1 1 0 A’ B C D’ = 1*1*1*1 = 1 0
7 0 1 1 1 A’ B C D = 1*1*1*1 = 1 0
8 1 0 0 0 A B’ C’ D’ = 1*1*1*1 = 1 1
9 1 0 0 1 A B’ C’ D = 1*1*1*1 = 1 0
10 1 0 1 0 A B’ C D’ = 1*1*1*1 = 1 0
11 1 0 1 1 A B’ C D = 1*1*1*1 = 1 0
12 1 1 0 0 A B C’ D’ = 1*1*1*1 = 1 0
13 1 1 0 1 A B C’ D = 1*1*1*1 = 1 1
14 1 1 1 0 A B C D’ = 1*1*1*1 = 1 0
15 1 1 1 1 A B C D = 1*1*1*1 = 1 1
AB 00 01 11 10
CD
00 0 4 12 8
0000 0100 1100 1000
01 1 5 13 9
0001 0101 1101 1001
11 3 7 15 11
0011 0111 1111 1011
10 2 6 14 10
0010 0110 1110 1010
AB 00 01 11 10
CD
00 1 1 1
01 1
11 1
10
Example 2: L = A’BCD + ABC’D + ABCD’ + AB’C’D’ + ABCD

As with the table above, we plot the map as thus:
AB 00 01 11 10
CD
00 1
01 1 1
11 1
10 1
2.7 CIRCUIT-MINIMIZATION
Every Boolean expression can be transformed into minterm
has important practical effects on the processing speed of
any combinational circuit network. As the circuit become
larger with more than 5 variables, it become important to
simplify the circuit to obtain a minimal circuit that behave in
just the same way as the initial circuit expression given. Due
to the string of gates, when there is a change in the input,
output does not respond to it immediately because of time
delay. This is the time it takes for the signal to propagate the
change made via the components that make up the network.
The time delay it takes for the output to respond to the input
change is known as gate delay and different manufacturer
use different gate delays because it is more expensive to
implement shorter gate delays than longer gate delays
because shorter gate delays require more power to operate.
These delays becomes noticed as the network contains more
gates that will require it to loop the signal in the circuit.
Typical gate delay is 10ns so that if we have three-level net,

an input signal change will require 10ns to propagate via the
first gate, another 10ns via the second gate and another
10ns to the last gate – a total of 30ns. In a two-level net, it
will require 10ns to propagate via the first gate and another
10ns via the second gate, total of 20ns for the input change
to be propagated through to its output. Hence, a two-level
network grants a reduced time propagation delay from 30ns
to 20ns, a 33% improvement in speed performance. Most
circuit networks are implemented as two-level networks.
Networks with more than two-levels require fewer gates than
their equivalent two-level network – since a gate requires
same amount of physical space in an IC board. Hence, a
two-level network achieves faster speed at the expense of
the extra space required for the additional gates (a tradeoff
between time and space).
The minimization methods are as follows:

▪ Boolean Postulates or Algebraic simplification
▪ Karnaugh’s map
▪ Tabulation and charting (Quine McCluskey method)
The Objectives of Minimization includes

a. It helps logic designers and engineers to produce a design that meets
the specification of the system required.
b. It allows lesser number of gates as well as lesser number of input
elements because the smaller the logic designs, the less complicated
and cheaper the production cost.
c. Circuits are produced at reduced production cost.
d. The smaller the number of gates used, the lower the gates chances of
malfunctioning when in use.
Minimization simply helps produce a minimal circuit form of

the Boolean expression giving, to minimize cost. However,
the use of Boolean algebra when minimizing is somehow
unreliable – because most times the minimum form of the
circuit achieved via it does not appear as the cheapest cost
of implementation. Boolean algebra minimization usually
produces a more expensive form of the circuit, at which
juncture, Karnaugh’s map and McCluskey’s tabulation and
charting method is employed. Tabulation method is most
appropriate for design involving more than five variable
inputs, where Karnaugh’s maps are not effective.
Karnaugh’s Map Minimization: The steps for obtaining

the minimal form of an expression using map method are:
a. Complete the table and map as required by entering a 1 value
into the boxes that have their minterm in the Boolean
expression given
b. Find minterms that differ from each others by a 1 variable and
construct the smallest, possible number of groups by grouping
those minterms that have 1 variable separating them.
c. All squares containing a 1 must be in atleast one group as well.
d. A minterms should not appear twice in the expression. But iif it
should, its inclusion must enable a smaller group to be
obtained from the larger group.
Minimize L = AB + AB’
Step 1: We construct the truth table and plot the map:
Value A B Minterm
0 0 0 A’B’ = 1*1 = 1
1 0 1 A’B = 1*1 = 1
2 1 0 AB’ = 1 * 1 = 1
3 1 1 AB = 1*1 = 1
A 0 1 A 0 1
B B
0 A’B’ AB’ 0 1
1 A’. B AB 1 1
Step 2: We group the minterms and minimize algebraically:

L = AB + AB
L = A (B’ + B) ------- Distributive Law
L = A (B’ + B) ------- B’ + B = 1 (Complement Law)
L = A.1 ➔ L = A
Example 1: L = A’B’C’ + A’BC’ + A’BC + ABC + AB’C

Construct table and plot the map gives us:
Value A B C L output Minterm
0 0 0 0 1 A’B’C’ = 1*1*1 = 1
1 0 0 1 0 A’B’C = 1*1*1 = 1
2 0 1 0 1 A’B C’ = 1*1*1 = 1
3 0 1 1 1 A’BC = 1*1*1 = 1
4 1 0 0 0 AB’C’ = 1*1*1 = 1
5 1 0 1 1 AB’C = 1*1*1 = 1
6 1 1 0 0 ABC’ = 1*1*1 = 1
7 1 1 1 1 ABC = 1*1*1 = 1
AB
C 00 01 11 10
0 1 1
1 1 1 1
L = A’B’C’ + A’BC’ + A’BC’ + A’BC + ABC + AB’C

L = (B’+B) A’C’ + (C’+C) A’B + (B’+B) AC -----Identity Law
L = A’C’ + A’B + AC ---- Minimal circuit
Crosscheck if L = F:
No A B C A’ B’ C’ A’C’ A’B AC F
0 0 0 0 1 1 1 1 0 0 1
1 0 0 1 1 1 0 0 0 0 0
2 0 1 0 1 0 1 1 1 0 1
3 0 1 1 1 0 0 0 1 0 1
4 1 0 0 0 1 1 0 0 0 0
5 1 0 1 0 1 0 0 0 1 1
6 1 1 0 0 0 1 0 0 0 0
7 1 1 1 0 0 0 0 0 1 1
We crosscheck if the circuit given is same as the initial circuit

as sometimes, we can have two solutions the best of which
depends on the circuit. Hence, L = F. We also minimize as:
A
B 0 0 1 1
C 0 1 1 0
0 1 1
1 1 1 1
The second grouping is minimized as thus:

L = A’B’C’ + A’B’C’ + A’BC + ABC + ABC + AB’C
L = (B’+B) A’C’ + (A’+A) BC + (B’+B) AC -----Identity Law
L = A’C’ + BC + AC ----- Minimal form
Crosschecking with the truth table shows that L = F.

A B C A’ B’ C’ A’C’ BC AC F
0 0 0 0 1 1 1 1 0 0 1
1 0 0 1 1 1 0 0 0 0 0
2 0 1 0 1 0 1 1 0 0 1
3 0 1 1 1 0 0 0 1 0 1
4 1 0 0 0 1 1 0 0 0 0
5 1 0 1 0 1 0 0 0 1 1
6 1 1 0 0 0 1 0 0 0 0
7 1 1 1 0 0 0 0 1 1 1
If L = A’BCD +ABCD + ABC’D’ + ABC’D + ABCD’
Solution: Construct table, plot map and group as thus:
AB
00 01 11 10
CD
00 1
01 1
11 1 1
10 1
L = A’BCD + ABCD + ABC’D’ + ABCD + ABC’D + ABCD’

L = BCD + AB (C’+C)(D’+D) + AB (C’+C)(D’+D) ------Identity
L = BCD + AB (1).(1) + AB (1) . (1) ----- (AB + AB = 1)
L = BCD + AB ➔ L = AB + BCD
Crosschecking with original truth table plotted will gives:

N0 A B C D AB BCD F = AB + BCD
0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0
2 0 0 1 0 0 0 0
3 0 0 1 1 0 0 0
4 0 1 0 0 0 0 0
5 0 1 0 1 0 0 0
6 0 1 1 0 0 0 0
7 0 1 1 1 0 1 1
8 1 0 0 0 0 0 0
9 1 0 0 1 0 0 0
10 1 0 1 0 0 0 0
11 1 0 1 1 0 0 0
12 1 1 0 0 1 0 1
13 1 1 0 1 1 0 1
14 1 1 1 0 1 0 1
15 1 1 1 1 1 1 1
Our minimal circuit yields same behaviour as the initial circuit.

Example 2: Plot the map and minimize L = A’B’CD’ +
AB’CD’ + AB’CD + A’BC’D’ + ABC’D’ + A’BC’D + ABC’D
No A B C D Minterm L
0 0 0 0 0 A’ B’ C’ D’ = 1*1*1*1 = 1 0
1 0 0 0 1 A’ B’ C’ D = 1*1*1*1 = 1 0
2 0 0 1 0 A’ B’ C D’ = 1*1*1*1 = 1 1
3 0 0 1 1 A’ B’ C D = 1*1*1*1 = 1 0
4 0 1 0 0 A’ B C’ D’ = 1*1*1*1 = 1 1
5 0 1 0 1 A’ B C’ D = 1*1*1*1 = 1 1
6 0 1 1 0 A’ B C D’ = 1*1*1*1 = 1 0
7 0 1 1 1 A’ B C D = 1*1*1*1 = 1 0
8 1 0 0 0 A B’ C’ D’ = 1*1*1*1 = 1 0
9 1 0 0 1 A B’ C’ D = 1*1*1*1 = 1 0
10 1 0 1 0 A B’ C D’ = 1*1*1*1 = 1 1
11 1 0 1 1 A B’ C D = 1*1*1*1 = 1 1
12 1 1 0 0 A B C’ D’ = 1*1*1*1 = 1 1
13 1 1 0 1 A B C’ D = 1*1*1*1 = 1 1
14 1 1 1 0 A B C D’ = 1*1*1*1 = 1 0
15 1 1 1 1 A B C D = 1*1*1*1 = 1 0
AB 00 01 11 10
CD
00 1 1
First group
01 1 1
11 1
Second
10 1 1 Third
L = A’BC’D’ + ABC’D’ + A’BC’D + ABC’D + A’B’CD’ + AB’CD + AB’CD’

First Quadruple – written in this order Minterms 4, 5, 12, 13 as
L = A’BC’D’ + ABC’D’ + A’BC’D + ABC’D
L = BC’ (A’+A)(D’+D) + BC’ (A’+A)(D’+D)
L = BC’ + BC’ ➔ L = BC’
Second group is written in this order Minterms 10, 11 as
L = AB’CD’ + AB’CD ➔ L = AB’C (D’+D) ➔ L = AB’C
Third grouping, we have the Minterms 2 and 10
L = A’B’CD’ + AB’CD’ ➔ L = B’CD’ (A’ + A) ➔ L = B’CD’
Hence, F = BC’ + B’CD’ + AB’C
Crosschecking to see if the output is same as thus
A B C D BC’ B’CD’ AB’C F =BC’+B’CD’ +ABC’
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 1 0 0 1 0 1
0 0 1 1 0 0 0 0
0 1 0 0 1 0 0 1
0 1 0 1 1 0 0 1
0 1 1 0 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0
1 0 1 0 0 1 1 1
1 0 1 1 0 0 1 1
1 1 0 0 1 0 0 1
1 1 0 1 1 0 0 1
1 1 1 0 0 0 0 0
1 1 1 1 0 0 0 0
Again L = F. Minimizing 4-variable is confusing and tricky.

Hence, it requires practice, reasoning and experimenting
using several minterm groups to find the true minimal circuit.
Hence, adjacency will help us know which Minterm groupings
to consider when we have complex maps because there can
be more than one true or valid minimal circuits.
Consider L = ∑ (0, 1, 2, 3, 5, 6, 7, 8, 9, 12, 13, 14) soled as:
Step 1 and 2 ends us up with the map below:
AB 00 01 11 10
CD
00 1 1 1 First
Second
01 1 1 1 1
11 1 1 Third
10 Fourth
1 1 1
Fifth
L = AB’C’D’ + AB’C’D + ABC’D + ABC’D’
L = AC’ (B’+B)(D’+D) + AC’ (B’+B)(D’+D)
L = AC’ + AC’ ➔ L = AC’
Second Quadruple written as 0, 3, 1, 2
L = A’B’C’D’ + A’B’CD + A’B’C’D + A’B’CD’
L = A’B’ (common terms)
Third Quadruple written as 3, 6, 2, 7
L = A’B’CD + A’BCD’ + A’B’CD’ + A’BCD
L = A’C(B’+B)(D’+D) + A’C (B’+B)(D’+D)
L = A’C + A’C ➔ L = A’C
Fourth Quadruple written as Minterm 1, 5, 13, 9
L = A’B’C’D + A’BC’D + ABC’D + AB’C’D
L = C’D (A’+A)(B’+B) + C’D (A’+A)(B’+B)
L = C’D + C’D ➔ L = C’D
Fifth couple written as Minterm 4, 6
L = A’BCD’ + ABCD’
L = BCD’ (A’+A) ➔ L = BCD’
Hence: F = AC’ + A’C + A’B’ + C’D + BCD’
This is a plausible solution, but is not correct since it does

not proffer the minimal solution. But again, consider this:
AB 00 01 11 10
CD
00 1 1 1 First
Second
01 1 1 1 1
11 1 1 Third
10 Fourth
1 1 1
The problem of the first solution was with our grouping of

the Minterms 13. In the second, it is grouped in the third
quadruple as Minterm 1, 5, 13 and 9. This second grouping
does not contain this third quadruple.
The solution is as:
L = AB’C’D’ + AB’C’D + ABC’D + ABC’D’
L = AC’ (B’+B)(D’+D) + AC’ (B’+B)(D’+D)
L = AC’ + AC’ ➔ L = AC’
Second Quadruple written as 0, 3, 1, 2
L = A’B’C’D’ + A’B’CD + A’B’C’D + A’B’CD’
L = A’B’ (common terms)
Third Quadruple written as 1, 3, 7, 5
L = A’B’C’D + A’BCD + A’B’CD + A’BC’D
L = A’D (B’+B)(C’+C) + A’D (B’+B)(C’+C)
L = A’D + A’D ➔ L = A’D
Fourth Quadruple written as Minterm 6, 14
L =A’BCD’ + ABCD’
L = BCD’ (A’+A) ➔ L = BCD’
F = AC’ + A’B’ + A’D + BCD’
Don’t Care Circuits: Any situation in which the circuit is

designed to process its inputs, not minding that some input
conditions may erupt as the circuit is in use, that were
initially not cared for. As these inputs occur, it means that
not all inputs states are represented by such an expression –
since some states were not expected. But if they occur – we
don’t care about the signal change. Hence, a circuit with
such ability that takes care of such inputs are called Don’t
care circuits because the circuit does not also care about
what output is obtained, if those inputs ever appear.
This feature gives designers extra flexibility in minimization

such that designers can design a circuit to give a 0 or 1 when
don’t care condition is present. By carefully selecting don’t
care states, to produce a 1 and 0 at some points, we improve
minimization. When representing don’t care conditions, we
are free to cover the cell with the symbol x, which acts as a
wildcard that it can be treated either as a 0 or a 1 value.
Consider the example below:
AB
C
Minimized as follows:
1 x(a,b,c) = ∑(1, 4, 5)
= A’B’C + AB’C + AB’C + AB’C’
1 1 = B’C (A’+A) + AB’ (C + C’)
= B’C + AB’
Consider adding don’t care and minimize the function as:

AB
C
Minimized as follows:
X 1 x(a,b,c) = ∑(1, 4, 5) + d(0, 7)
= A’B’C + AB’C’ + AB’C + ABC
1 X 1 = (A’+A)(B’+B)(C’+C) + AC (B’+B)
= AC
The function without a don’t care requires two AND gate

and one OR gate; while that with don’t care requires just
one AND gate – by simply allowing the minterm 0 to be
grouped and the minterm 7 to be a 0.
2.8 COMBINATIONAL DEVICES

Combinational circuits are most commonly used in the design
of computers, because even in sequential circuit designs,
combinational circuits are used but in addition to memory
elements that store bits sent through or to the device. Each
device can be specified as a black-box with its corresponding
truth table to help us know and define how the device’s
output depends on its input. Most of the devices as discussed
below are implemented using a two-level network, which
trades off less space for processing time.
These devices have an input line called enable, which acts

like an on/off switch for the device such that when the
enable is off or 0, the output lines all become 0 regardless of
what the input values are. Hence, the device is disabled or
turned-off. But when the enable line is 1/off, the output lines
at this instance will then depend according to what the input
lines specifies for the device and so, the device is turned-on
and enabled for the specified activity. Hence, an AND gate
with two inputs has one input as x and the other is the
enable alongside a corresponding output Y as in figure 2.20.
X Y Figure 2.20 shows the
logic diagram of an
enable gate
Enable
The truth table is shown below when the enable is 1:

Enable = 1
Enable X AND Output
1 0 1.0 = 0
1 1 1.1 = 1
Also, when the enable is 0, we have the table as thus:

Enable = 0
Enable X AND Output
0 0 0.0 = 0
0 0 0.1 =1
The enable gate does not require a new “enable” input but
requires that the AND gate be viewed differently such that
we see input X as data line; while the enable is the control
line. Hence, the enable controls the data either letting it to
pass through unchanged or prevents its passage to output.
Another useful gate used is the selective inverter having
inputs (a data line and an inverter). When the invert line is 1,
its output becomes the complement of the data line; while if
the invert line is 0, the data passes via to output unchanged
as seen in figure 2.21 with XOR gate viewed differently.
X Y
Figure 2.21 shows the logic

diagram for the selective
Invert Line inverter
When the invert line is 1, then we have that

Y = X  (invert)
= X’ . (Invert) + X. (Invert)’
= X’ . 1 + X . 1’ ➔ X’ . 1 + X . 0 = X’
Its output is complement of the data input. If invert line = 0:

Y = X  (invert)
= X’ . (Invert) + X. (Invert)’
= X’ . 0 + X . 0’ ➔ = X’ . 0 + X . 1 = X
The data passes via unchanged to output. Some of these

devices are discussed below as thus:
Multiplexers – is a device that simply selects one of the
several data inputs to be routed to a single data output, such
that a set of control lines determine which particular data
input is sent via to output as in figure 2.22 below.
D0
D0
S1
S0 D1
F
D1 D2
S1 D3
S0 S0
S1
D2
S1
S0
Fig 2.22 (a) abd (b) shows the
D3 block implementation and
block diagram of a four-input
S1 multiplexer
S0
S1 S0 F = Output
0 0 D0
0 1 D1
1 0 D2
1 1 D3
F is the single data output with the device having 6 inputs

namely S1, S2 and D0 to D3. Its complete table requires 26 =
64 entries as column 3 shows that D2 is selected when the
select lines are 10. Hence with D2 = 1 with F = 1. If D2 is 0,
then F is 0 regardless of other values of D0 via D3. With n
selects lines, which can choose one from 2n data lines. The
number of data inputs of a multiplexer is the power of 2.
Demultiplexer – This device routes a single input to several
output lines. Hence, it does nothing more than a decoder
with an enable such that the data input line D is connected
to the enable. If D = 0, the decoder is disabled and the data
output selected by S1 and S0 is 0. If D = 1, the decoder is
enabled and the data output line selected is 1. In either case
– the selected output line has same value as the data input
line as in table as thus:
S1 S0 D0 D1 D2 D3
0 0 D 0 0 0
0 1 0 D 0 0
1 0 0 0 D 0
1 1 0 0 0 D
D0
D1 Figure 2.23 shows

the four-output
D D2 demultiplexer
D3
S1 S0
Binary Adders – have two sets of input terminals such that
in parallel addition, series of bits corresponding to the two
binary numbers appear at these terminals while the output
terminals gives the sum of the two numbers. Adders are
grouped into half and full adder. The basic building block for
the half adder is an XOR gate with two inputs and two
outputs as in figure 2.24. The table shows that the S output
of a half-adder gives the sum of each digit while output C
gives the carryover of the digit represented as thus:
S=a b ➔ a’b’ + a’b’ and C = ab

X Y Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
X S (Sum)
X S
Half
Adder
C (Carry) Y C
Figure 2.24 shows the logic diagram for the binary adder
The half adder shows that the sum is identical to the XOR
function and the carry is identical to the AND gate function
as in the truth table and its implementation above. The full
adder is similar to half adder except for additional inputs that
receives carry-overs from the lower significant bit (LSB) as in
table below. Adding two numbers of such will exceed to the
next stage and requires a combinational net with three inputs
instead of two as with the half adder namely the Cin, X and Y.
Cin is carry input that comes with the carry made from the
addition of the LSB. X and Y are the binary numbers; while
the outputs are Sum and Cout is the carry output, which goes
to Cin of the full adder for the next column.
Cin Sn
X S
Xn
Y C
X S Cout
Yn
Y C
Figure 2.26 shows implementation of a full adder
X Y Cin Sum Cout

0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
1 0 0 1 0
0 1 1 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
The full adder sums from the second half adder such that if
any of the half adders have a carry, the full adder has a carry
because it is implemented on two half adder with an OR
gate. As with the truth table, to add two 4-bit numbers will
require an eight-input network as in figure 2.27.
X3
C Figure 2.27 shows
X2 the block diagram
of full adder.
X1
FOUR-
X0 BIT S3
ADDER S2
Y3
S1
Y2
S0
Y1
Y0
Xn defines 4-bit of the first LSB as Yn defines the second 4-
bits number; Sn is the 4-bit sum; while C is the carry.
Implementing a 4-bit adder uses one-half adder for the LSB
and three full adders, one for each of the remaining columns
in the addition – it becomes a ripple-carry adder, because a
carry from the LSB is propagated or rippled via the columns
to the left.
Binary Decoder – A decoder is a device that that takes a

binary number as input and sets one of the data output lines
to 1 while the rest becomes set to 0. The data line that is set
depends on what value of the binary number is sent as input.
As with the previous example, if we have an n-bit number –
it will have 2n values such that the number of data outputs of
the decoder is a power of 2.
S1 D0 D0
S0 S0 D1
S1 D1
D2
S1
S0
D3
S1 D2
S0
Enable
S1 D3
Fig 2.28 shows implementation and
S0 block diagram of a 2 x 4 binary
decoder.
Truth table for a 2 X 4 binary decoder is as below:

S1 S0 D0 D1 D2 D3 F = output
0 0 1 0 0 0 D0
0 1 0 1 0 0 D1
1 0 0 0 1 0 D2
1 1 0 0 0 1 D3
Arithmetic Logic Unit – Devices above perform operations
such as AND, ADD and OR. Unary addition is an arithmetic
operation, while AND and OR are logical operators and the
CPU perform these via the ALU. Table shows a 1-bit ALU.
S1 S0 F Cout
0 0 X.Y 0
0 1 X+Y 0
1 0 1 0
1 1 X plus C
Y plus Cin
Cin Cout
X Figure 2.29
ALU shows the block
Y
F diagram of a 1-
bit arithmetic
and logic unit
S1 S0
The truth table shows that if S1-S0 is 00, the output F is the
AND of X and Y. If S1-S0 is 01, it means that F is the OR of X
and Y. When it is 10 – F is simply X regardless of the value of
Y. In these three cases, F does not depend on the value of
Cin except when S1-S0 is 11. F is the sum of X, Y, Cin with Cout
being the carryover. The full adder contains an enable input
such that when E is 0, Cout and Sum are 0 regardless of Cin, X
and Y; Otherwise, if E is 1, the full adder operates normally.
D0, D1 and D2 are connected to the enable lines for X.Y, X+Y
and Y in the logic unit.
2.9 INTEGRATED CIRCUITS (ICs)

These are semiconductor materials that brought about third
generation computers allowing devices to be made from logic
gates, which are designed specifically for computer logical
and arithmetic operations. These transistors are packaged in
different scales to fit the purpose of the circuitry and help to
determine how many transistors make up one chip. Hence,
digital systems are constructed from such two-state element
in form of silicon chips known as ICs. Their arrangements
are usually as Dual In-Line Package, Straight Line and
Circular Line package as they are grouped into families based
on semiconductors that makeup their circuit design as thus:
Bipolar Logic uses bipolar junction transistor throughout
the circuit for a gate, which is the combination of the p-type
and n-type materials for the construction of the circuitry and
logic gate. The voltage 0v and 5v represent the logic gate
values 0 and 1 respectively. Examples are RTL, TTL, ECL.
MOS is based on Metal Oxide Semiconductor Field
Effect Transistor, devices with its resistance between the
two (2) terminals and is controlled by the voltage on the
third terminal. They are further subdivided into NMOS, PMOS
and CMOS
Logic family is described by characteristics as explained:
✓ Logic Level are voltage values assigned to the binary 0 and 1 states
for a given family. It is known as minimum voltage level at which the
circuit switches from one state to the other. The switching between
logic 1 and 0 values takes place only if the input level is above 2.5v or
below 0.8v. Hence, Logic 1 is between 2.5v and +5v while Logic 0 is
between 0v and 0.8v.
✓ Noise Margin and Immunity Any undesired voltage at the input
of a circuit is called noise. Generally gate circuits have the ability to
tolerate disturbances at their input – so that there is a margin
between its input and output voltage levels corresponding to each
logic value due to the noise disturbances. Hence, the degree to which
the gate suppresses the effects of undesired pulses is known as Noise
Immunity, because large noise pulses cause the circuit to switch
suddenly and give false information. Noise margin is the difference
between the circuits’ operating voltage and logic voltage; and the
probability of false switching due to noise is reduced if the noise
margin is high.
✓ Propagation Delay/Transition Time is the measure of the speed
of operation of the logic circuit or it can be simply viewed as the total
time delay between the time the input is applied and the time the
output state gets switched. That is the total time taken for the output
to respond and get switched due to the input signal applied. It is the
time taken for the circuit to respond to an input. A major determinant
of this feature is the load on the output line of the gate, particularly
the capacitive components.
✓ Fan-Out In sequential circuits, the output of a circuit can be used as
input for another circuit so that a logic gate acts as input to another
gate. This property describes the maximum number of allowable
output, each rated at a certain mA that a logic circuit may have and
still operate properly. Hence, the maximum number of logic gates that
can be connected to the output of another gate, while the logic gate
still maintains a nominal value describes.
✓ Fan-In describes the maximum number of allowable input, each
rated at a certain mA that an IC logic circuit may have and still
operate properly.
✓ Power Dissipation is one half the power that an integrated logic
circuit draws from the power supply. It is the amount of power
consumed by a logic gate while operating. Power consumption should
be minimized with applications that use batteries. Power consumed by
an integrated circuit is physically removed in form of heat – even if
the rate at which the heat is removed is limited, a limitation to
attainable density and number of the gates in an IC. Because power
consumption is different for the binary states – power dissipation
becomes the total power dissipation plus its average.
Table 2.3: Comparative analyses of IC families: Med for Medium

ICs Cost Propagati- Noise Fan Fan Power
on Delay Margin In Out Dissipate
DTL Med High Low High Med Med
RTL Med Med Low Low Low Low
TTL Med Low High High Med Med
ECL High Very low Med Med High High
CMOS Med High High High High Very Low
Med – Medium
CHAPTER QUESTION
2-1 Explain the concept of Data representation in your own term.
2-2 Convert 98, 543 and 2176 to their octal equivalence and convert these
binary numbers to decimal 10010 and 1000111
2-3 Express these in their hexadecimal equivalent 2E, 83D, and DF7
2-4 List and describe the features associated with the powers of a CPU
based on the Von Neumann’s stored program concept.
2-5 Convert these decimal numbers to binary: 37, 56, 89, and 1002
2-6 Perform the following binary additions
10100111 10101010 11111111
+ 1011101 +10111011 +11111111
----------------------- ----------------------- ----------------------
----------------------- ----------------------- ----------------------
2-7 Carry out the following binary additions
10100111 10101010 11111111
- 1011101 - 10111011 - 1111001
----------------------- ----------------------- ----------------------
----------------------- ----------------------- ----------------------
2-8 Define the following in your own term
(a) Logic, Argument, Proposition and negation
(b) Inductive and deductive arguments or reasoning
2-9 Define Karnaugh’s map? Draw the circuits and their maps for:
a. K = A’ B’ C’ D’ + A C’ D’ + A B’ C’ D’ + A’ B’ C D + A B C’
b. K = A’ B’ C + A C’ + A B’ C’ + A’ B’ C’ + A B C + AC
2-10 Define what you understand by the following with diagrams:

Multiplexer and Demultiplexer, Binary Decoder, Full and Half Adders,
Arithmetic and Logic Unit (ALU)
2-11 Given the map below, deduce the expressions
AB 00 01 11 10
CD
00
01 1 1
11 1 1 1
10 1 1
AB
C 00 01 11 10
0 1
1 1 1 1
2-12 Minimize the circuits given the map in 2-4(a) and (b) respectively.
2-13 In your own terms, define the following:
a. Logic level b. Propagation delay c. Fan in
d. Fan out e. Power dissipation f. Noise Margin
Chapter Three
THINKING PROBLEM – AIDING COMPUTERS!
INTRODUCTION
Computers are incredible devices. They extend what we can
traditionally, do with our brains. And with them as computing
devices, we can do things faster, explore their use in almost
every sphere of life, we can keep track of a vast amount of
data, we can effectively and efficiently use such processed
information as evidence to support our decisions, and we can
share our ideas and knowledge with other people no matter
where they are, when they need it and how they wish to get
it. Getting computers to help us to solve problems is a 2-step
process: (a) first, we think about all requisite steps needed to
solve a problem, and (b) then, we explore our technical skills
to get the computer working on the problem.
Even when it is something as simple as using a calculator to

solve a word problem in mathematics. First, it is a requisite
that we have to understand and interpret the problem before
the calculator can help out with the arithmetic bit. Similarly,
if we wish to make an animation, we start by planning the
story and on how to shoot it. Afterwards, we can then use
computer hardware and software to help you get the work
done. In both of these scenarios and examples, the thinking
that is undertaken before starting work on a computer is
known as computational thinking.
Computational thinking describes the science, processes and

approaches we draw on when thinking about problems or
systems in such a way that a computer can help us with
these. Computational thinking is not the same as thinking
about computers, or like computers. This is also true because
computers cannot or do not think for themselves, or of their
own accord (atleast, not yet) without the aid of programs to
help them as processing units accomplish such feat and task.
Computational thinking is simply, about looking at a task or
problem in a way that a computer can conveniently be used
to help us solve the task before us. To accomplish this type
of thinking (i.e. computational thinking), we use a variety of
computational thinking processes to tackle a problem. These
processes (concepts and approaches) include:
1. Logical Reasoning – predicting and analyzing
2. Algorithms – making steps and rules
3. Decomposition – breaking down the problem into smaller parts
4. Abstraction – removing all unnecessary details
5. Patterns Generalization – spot similar data/objects, and using
these similarities as evidence to make meaning of the process.
6. Evaluation – means making the right judgements based on the
conclusions reached that are backed up with evidence.
What to do with Computational Thinking

Computational thinking describes the type or sort of thinking
that computer scientists and software developers engage in.
Many people think this way too. This thinking processes and
approaches help with computing and informatics, and can be
useful in many other domains. A team of software engineers
to create a new game, team of instructors can plan together
to put up school play, or to organize an educational visit.
Whatever the case and task, we should be able to use some
tact and explore the following: (a) first, take a complex task
and break it down into smaller problems, (b) secondly, work
out the steps to get it done, (c) thirdly, we must manage
the complexity of the task by focusing on the key details, and
(d) fourthly, we must explore methods previously used for
similar projects, and see how they be of help here?
Concepts to Computational Thinking
Computational thinking is at the crux, pivot and epicenter of
computing education and ambition. This paradigm posits that
a high-quality computing education equips her graduates to
explore and exploit computational thinking and creativity to
understand and change the world. Whilst, programming is an
important and crucial feat to computing science, it is wrong
to see this as an end in itself. Rather, computational thinking
provides the requisite platform to propel practical experience
with programming with insights that can best be developed
and explored as thus. We should not just see computational
thinking as a new name for ‘problem-solving skill’. Rather, we
should see computational thinking as skills needed to solve
problems over a wide range of applications, and across other
disciplines. Though, it is most effectively learned via rigorous,
creative processes of writing codes as seen in Figure 3.1
Figure 3.1. Concept and Approach to Computational Thinking

Logical Reasoning
If you set up two computers in the same way, give them the
same instructions (the program) and the same input, you
can pretty much guarantee the same output. Computers do
not make things up as they go along or work differently
depending on how they happen to be feeling at the time.
This means that they are predictable. Because of this we can
use logical reasoning to work out exactly what a program
or computer system will do. Children quickly pick this up for
themselves: that is, the experience of watching others and
experimenting for themselves allows even very young
children to develop a mental model of how technology works.
A child learns that clicking the big round button pops up a list
of different games to play, or that tapping here or stroking
there on the screen produces a reliably predictable response.
The process of using existing knowledge of a system to make

reliable predictions about its future behaviour is one part of
logical reasoning. At its crux, logical reasoning is being able
to explain why something is the way it is – while, seeking to
work out if there is a better way as to how that something
should be. Logic is the fundamental to how computers work:
deep inside a computer’s central processing unit (CPU), every
operation the computer performs is reduced to logical
operations carried out using electrical signals. It is because
everything a computer does is controlled by logic, that is why
we can use logic to reason about program behaviour.
Software engineers use logical reasoning all the time in their

work. They draw on their internal mental models of how
computer hardware, the operating system (like Windows,
Macintosh, X etc) and the programming language they are
using all work, in order to develop new code that will work as
they intend. They will also rely on logical reasoning when
testing new software and when searching for and fixing the
‘bugs’ (mistakes) in their thinking (known as debugging) or
their coding when these tests fail.
There are many ways that we already use logical reasoning

across various curriculum as we proceed in life namely:
1. In English, students may explain what they think about
any character in a novel they just read, or to predict what
they feel and think a character will do next based on the
character’s action so far.
2. In Mathematics or other Science subjects, a learner or
student should explain how they have arrived at their
conclusions from the results of their experiments.
3. In history, a student should discuss those logical
connections between cause-and-effect overtime in
history; And, they should be able to understand how
historical knowledge is constructed from a variety of
sources.
4. In Computing – a stage-1 learner is expected to use
logical reasoning to predict the behaviour of simple
programs. It may also include those they themselves
have written, and may also include them predicting what
happens when they play a game; while, a stage-2
learner is expected to use logical reasoning to explain
how some simple algorithms work and to detect and
correct errors in algorithms and programs.
Classroom Activity
1. Provide students with a robot. They should make predictions of where
the robot will end up when the go button is pressed. And they should
explain why they think of that. Being able to give a reason for their
thinking is what using logical reasoning is all about.
2. In their own coding, logical reasoning is key to debugging (finding and
fixing the mistakes in their programs). Ask them to look at each
other’s codes/programs and spot bugs. Encourage them to test the
programs to see if they can isolate exactly which bit of code is causing
a problem. If their codes fail to work, get them to explain their code
to a friend or even an inanimate object.
3. Give them a program of your own samples and ask them to work
backwards from the code to work out what it will do.
4. Ask pupils to think carefully about some school rules, for example
those in the school’s computer Acceptable Use Policy. Can they use
logical reasoning to explain why the rules are as they are?
5. There are many games, both computer-based and more traditional,
that draw directly on the ability to make logical predictions. Organize
for the pupils to play noughts and crosses using pencil and paper. As
they are playing, ask them to predict their opponent’s next move. Let
them play computer games such as Minesweeper, SimCity, etc. Ask
them to pause at certain points and tell you what they think will
happen when they move next. Consider starting a chess club if your
school does not already have one.
Algorithm
An algorithm is a finite sequence of instructions or rule to get
something done. Your fastest route to home from school may
be → turn left, walk for 2-miles, turn right, etc). That, is an
‘algorithm’. A finite, logically ordered number of instructions
(or steps) that effectively yields a solution to a problem.
There are many algorithms (i.e. routes) that will accomplish
the same goal as getting you to your destination from any
one point. Even the Google-Map algorithm for working out
the shortest/fastest route. Search engines like Google and
Bing use algorithms to put a set of search results into order,
so that more often than not, the result we are looking for is
at the top of the front page.
Your Facebook news-feed is derived from your friends’ status

updates and other activity. It only shows that activity which
the algorithm (EdgeRank) thinks you will be most interested
in seeing. So also, the recommended views you get on eBay
Netflix, Twitter, and other social networking sites. All these
are algorithmically generated, based in part on what other
people are interested in. Given the extent to which so much
of their lives is affected by algorithms, students should grasp
and understand what an algorithm is. A simple algorithm can
be seen in Figure 3.2 to help student get an idea of what an
algorithm is.
Figure 3.2. Schematic diagram of an Algorithm
Students have been tasked to and will already use algorithms

in many different ways across the school as thus: (a) lesson
plan or course compact of curriculum is regarded as an
algorithm for teaching a course, (b) a cooking recipe can be
thought of, as an algorithm, (c) we can think of instructional
writing as a form of algorithm in English; while for science –
we may talk about method of an experiment as an algorithm,
and (d) for Mathematics, your approach to mental arithmetic
(or many computer-based educational games) might be an
implementation of a simple algorithm.
We expect students to have: (a) first, an understanding of
what algorithms are, and how they are used in programs of
digital devices. There can be many algorithms to solve the
same problem, and each of these can be implemented using
different programming languages of choice on the different
computer systems, and (b) secondly, students must build on
this to design programs with particular goals in mind, which
will draw on their being able to think algorithmically as well
as using logical reasoning to explain algorithms and to detect
and correct errors in them.
To practice this, encourage pupils to carry out the steps for

an algorithm: to follow the instructions themselves rather
than writing these as code for the computer. Errors and
inconsistencies should become apparent with time. While,
some programming languages like BASIC, Java, Python can
make it seem unnecessary to go through the planning stage
of writing a program, it is good practice for pupils to write
down the algorithm for a program, perhaps as rough jottings,
a storyboard, pseudocode (a written description of how a
program will operate) or even as a flow chart. This makes it
far easier for them to get feedback from you or their peers
on their algorithms before implementing these as code on
their computers.
Classroom Activity
1. A GSM company just arrived and wishes to make investment in Delta
State by citing their Base-Transceiver Stations (BTS) around the State.
- Predict how, where and which places (urban, semi-urban and rural)
areas that will be connected to the network the GSM company
intends to develop in the State.
- What components and factors should be considered when citing
these connection provider site(s).
- Explain why and where will be your initial cum pivot connection
point (if you are Head of Operations for the said GSM company)
- Draw the network showing all sites for Delta State of towns and
villages to be connected, and state the reasons for your choice.
2. Generate a list of numbers by asking the students to guess as many
numbers between 1-100. Recall the BinarySearch and LinearSearch.
The students are to perform both search types and generate their
answers. They are to generate the algorithm(s) (in steps 1-to-N) to
resolving the task for the BinarySearch and LinearSearch
Decomposition
The process of breaking down a problem into smaller
manageable parts is known as decomposition. Decomposition
helps us solve complex problems and manage large projects.
This approach has many advantages. It makes the process a
manageable and achievable one – large problems are
daunting, but a set of smaller, related tasks are much easier
to take on. It also means that the task can be tackled by a
team working together, each bringing their own insights,
experience and skills to the task. Decomposing problems into
their smaller parts is not unique to computing: it’s pretty
standard in engineering, design and project management.
Software development is a complex process, and so being
able to break down a large project into its component parts
is essential – think of all the different elements that need to
be combined to produce a program, like PowerPoint.
The same is true of computer hardware: a smartphone or a

laptop computer is itself composed of many components,
often produced independently by specialist manufacturers
and assembled to make the finished product, each under the
control of the operating system and applications. You must
use decomposition to tackle big projects at school, just as
programmers do in the software industry. Our Computer
Science curriculum is typically decomposed into a 4-Years
programme with courses at the various Years (called Levels).
Courses are further decomposed into topics with units of
work and individual lessons/activities. Notice how the project
is tackled by a team working together (your colleagues), and
how important it is for the parts to integrate properly.
Figure 3.3. Decomposition of a School Trip
We already use decomposition in many different ways across

the curriculum. In science, we label diagrams to show the
different parts of a plant, or the different nations which make
up Africa. In English, we plan the different parts of a story.
In general project planning, planning a research project for
any subject or working collaboratively to deliver a group
presentation. Technology can help with collaborative group
work, or can even be a focus for it, and great collaborative
tools are available in Office and other ‘cloud’-based software.
In Mathematics, we break-down a problem to solve it.
Students are expected to learn to ‘decompose problems into

smaller parts first, in a bid to solve them, through design and
creation of a range of systems (and sub-systems) that have a
particular goal in mind (a system is something with a number
of interconnected components).
Students must plan to execute programs or systems using

the features of decomposition to achieve it as thus: (a) first,
work out what the different parts of the program or system
must do, and (b) second, we must think about how these
inter-relate. For example, a simple educational game is going
to need some way of generating questions, a way to check if
the answer is right, some mechanism for recording progress
such as a score and some sort of user interface, which in
turn might include graphics, animation, interactivity and
sound effects.
Classroom Activity
1. Plan out opportunities for students to experience team-work through
their collaboration on a software development project to build small
apps or even challenging programming project such as making a
computer game or even a mobile phone app.
2. The process of even having them develop a term-paper for submission
requires the task of writing and filling up the agreed number of pages
with words that can be further decomposed via planning, research,
drafting, reviewing and publishing (typing) phases.
Patterns and Generalization

The method of looking for a general approach to a class of
problems is called generalization. By identifying patterns, we
can make predictions, create rules and solve more general
problems. To learn about the area of a rectangle, students
can be asked to find the area of a particular rectangle by
counting the centimeter squares on the grid on which itis
drawn. But a better solution would be to multiply the length
by the width. This method is both quicker and is a method
that will work on all rectangles, including really small ones
and really large ones. Although it takes a while for students
to understand this formula, once they do it’s so much faster
than counting squares. Students are likely to encounter the
idea of generalizing patterns in many disciplines and areas of
their primary focus and endeavors as in Figure 3.4.
Figure 3.4. Patterns Matched
From an early age, we must become familiar with repeated

phrases in nursery rhymes and stories. We should later then
notice the repeated narrative structures in traditional tales.
In music, we must recognize repeating the melodies or bass
lines in many musical formats. In Maths, we must typically
aim to undertake investigations in which we spot patterns in
a problem as well as deduce generalized results. In English,
we might notice and identify common rules for spellings and
grammar, and also note their exceptions.
Abstraction
The process of deciding those details to be highlighted and
those details we can ignore. Abstraction is about simplifying
things; identifying what is important without worrying too
much about the detail. Abstraction allows us to manage
complexity. We use abstractions to manage the complexity of
life in schools. School timetable is also an abstraction of what
typically happens weekly in a citadel of learning as it aims to
capture key information and knowledge of: (a) who teaches
what course, (b) what courses is to be taught or undertaken
for a specific time-slot, (c) to whom is the course taught, and
(d) which venue and time is the said course to be taught. We
must also realize that it leaves out that angle of further layer
of complexity, such as the learning objectives and activities
planned in any individual lesson as in Figure 3.5.
Fifgure 3.5. Schematic diagram of point A to B abstracted
Abstraction is such a powerful way of thinking about systems

and problems that it seems worth introducing pupils to this
whilst they’re still at primary school. Word problem in Maths
involves identifying key data, and establish means on how to
represent the task (in arithmetic, algebra or geometry). Maps
are an abstract complexity of the environ with various scales
providing a layered nature of the chosen site. Histories are
an abstraction of detail present in local histories or individual
biographies as abstractions of actual events. The piano score
of a pop song is also an abstraction for that piece of music.
Our curriculum hopes that students (although, as part of the
overarching aims of this course/subject) – must understand
and apply the fundamental principles and concepts of
computer science, including abstraction, logic, algorithms and
data representation. Students must learn about the process
of abstraction from playing interactive games that involves
real-world simulations. We encourage students to be curious
about how things work, and to think of what happens inside
the computer, or online as they surf the web. Students must
put together a presentation on a topic they know about, they
will need to focus on the key information, and think about
how this can be represented, whilst leaving to one side much
of the detail of the subject: this too involves abstraction.
Classroom Activity
Encourage students learning to program – to create their own games that
can either be based on real world systems or otherwise. They will need to
use some abstraction to manage the complexity of their game system.
They can simulate a table tennis game (i.e. ping-pong) such that the
simulation can include the ball’s motion in 2D, and how it bounces off the
bat. Ask them to think carefully about what detail they need to include,
and what can be left out when programming a similar game.
Evaluation
This is often the most underemphasized feat – even when it
is the most crucial step in problem solving. It is the reason
and crux of why researches are conducted. The reason why
people do not embark on evaluations includes time, cost, the
unease with evaluation, and the fear of being challenged in
their decisions reached with evidence. Evaluation is essential
because it seeks to determine how effective the proposed
solution is. Evaluation can take many forms, and it can be as
simple cum brief as a conversation with key individuals and
members; Or, it can be as elaborate as sophisticated surveys
and in-depth record analysis. Evaluation seek to determine
how well the solution works/fits or why the solution
does not work. We must or can decide how comprehensive
evaluation should be, based on the complexity of the task or
problem and the decided solution.
Evaluation must be poised towards reaching the cost-benefit

analysis. It must be capable to address 4-critical features in
the search for solution. It must seek to address the following
strengths, weaknesses, opportunities, and threats,
which must also become and form the basis to ensure that a
proposed solution complies with. Measuring a solution based
on these – will help ensure that whatever solution is put
forward will always outperform the existing/current system
as seen in Figure 3.6 that details difference in method.
Figure 3.6. Difference in Evaluation of the Used Methods
First, to decide how to execute a solution, we must uncover

possible weaknesses. What often sounds and looks as a good
decision in our mind or on paper, may in practice prove to be
inoperable and non-functioning. We often end up here when
we try to initiate an action of the plan. Where the solution is
unworkable, it can be abandoned in favor of one that is more
likely to work. Depending on the severity of the problem and
the quality of solution desired, objectives and approaches for
problem solving will vary. For minor tasks, we can focus on
quickly reaching a solution as the main goal. But, where we
seek or are primarily concerned with finding quality solution
as a main objective – we will always factor in more time for
the problem-solving process.
For effectiveness, problem solving must reach or arrive at a

solution that both gets the job done, efficiently use available
resources, promote cooperation among team members, and
fosters competence. Problem solving is an ongoing process
that is an integral part of everyday life either at home or at
work. A problem must first be felt as clear, understood, and
alternate choices created; Before, we consider its solution,
implement the decision, and evaluate how well the solution
works. Evaluation should also call for a back-trace and review
of each step advanced where they seem unclear.
Classroom Activity
Plan a traditional ‘design, code and evaluate task such as plan the process
for building a house. Break this complex problem down into smaller stages,
such as: (a) planning the design (abstraction to capture key elements of
building), (b) sourcing of the materials (decomposition to identify the
different components), (c) assemble the materials to create the instrument
(algorithm – systematic, step-by-step approach to put the house together),
and evaluate and test how the solution works.
Approaches to Computational Thinking

As with the processes, there are a number of approaches
that characterize computational thinking. If students are to
start thinking computationally, then they must develop these
approaches to their work, so they can be more effective in
putting their thoughts into action.
Tinkering is that willingness to experiment and explore with

work. An element of learning a new programming language
or exploring a new system look quite similar to this sort of
purposeful play. It is often an effective approach to learning.
Open-source software makes it easy to take someone else’s
code, look at how it is written, see all the comments on how
the codes fit together, and then adapt it to your own task or
particular purpose. Many platforms like TouchDevelop and
Scratch can positively encourage users to practice this by
looking at other programmers’ work and use it as a basis for
their own creative coding. We must encourage pupils to play
with a new piece of software, sharing what they discover
about it with one another; Rather, than just teach or explain
to them exactly how it works. Students must look for ways to
use other experienced coders’ code as a pivot/pilot starting
point for their own programming projects.
Figure
Creating: Programming is a creative process, which involves
both originality, making something of value and something
that typically is useful or fits a specific purpose. Students
must approach tasks with a creative spirit, and look for those
programming tasks that allow them express such creativity
also; Rather, than merely arriving at a right answer. Students
must reflect on the quality of the work they produce – simply
by critiquing their own against others. The process of always
looking for ways to improve on a task is becoming common
practice in software development. Look for projects in which
artistic creativity is emphasized such as working with images,
animation, virtual environments or even 3D printing.
Figure
Debugging: Due to the nature and complexity of coding,

many programs often do not work at first impulse. And even
when it does, it does not often work as intended. So, getting
users to take responsibility of thinking through the algorithms
and code, to identify and fix errors is an important part of
learning to think, and work like a scientist and programmer.
Get students to check through their Maths work, to proofread
their English writings and debug another programmer’s code
by looking for mistakes and suggesting improvements. There
is always evidence that learning from mistakes – is continued
to particularly be an effective approach. Allowing students to
embark therein this process of debugging their own and/or
other users’ code is one way to achieve this. Teachers must
learn also to keep an eye on the bugs his/her students often
encounter, as this can sometimes reveal misconceptions that
s(he) may need to address.
Figure
Persevering: Coding can be quite hard, tedious and often

mind-bending. It requires patience as a crucial part and facet
to its appeal of writing elegant, effective code often comes
with its intellectual challenge. This requires not only the apt
understanding of the ideas of the algorithms being coded;
But, also of the programming language being used and the
willingness to persevere with something that is quite difficult
and frankly, very frustrating. The ‘growth mind-sets’ suggests
that hard work and a willingness to persevere in the face of
difficulties are key factors to achieving the set educational
outcomes. Students must have commitment to the cause of
coding, and be consistent in their resolve never to give up.
These are great strategies they can imbue and imbibe when
they encounter difficulties with their programming work, such
as working out exactly what the problem is, searching for the
solution on Bing or Google, or asking a friend for help.
Collaborating: Software has/is often developed by teams of

programmers working together on project. Many see pair
programming and collaboration as an effective development
method, with two/more programmers sharing a screen and a
keyboard, working together to write software. Typically one
programmer acts as the driver, dealing with the detail of the
programming, whilst the other takes on a navigator role,
looking at the bigger picture. The two programmers regularly
swap roles, so as to grasp both granular details of the
program and the big picture. Working in a larger group can
help us develop a number of additional skills where each
student contributes their own particular talents to the shared
project. It is important to remember that all students should
develop their understanding of each part of the process;
Thus, they must share and exchange roles and peer-tutoring
should be incorporated into such activities.
Question
Classroom Activities
1. Ask your pupils to write a recipe for a sandwich, thinking carefully
about each step that needs to be carried out.
- Please, detail step-by-step instruction sequence (i.e. algorithm).
- Ask them to share each other’s recipes – so they can efficiently spot
patterns in them (i.e. generalization).
- Read out a range of other related recipes, and discuss the layers of
simplification (abstraction) present relatively simple recipes.
2. Break them into groups and also challenge them to work individually
or collaboratively on more complex projects, for example researching
and writing up aspects of a curriculum topic such as the Viking
invasion, or putting together an assembly or a class play. In each case
ask them to note down the individual steps needed for the task and to
think about what they have left out to make the subject fit their brief.
Term Paper 1
A GSM company just arrived and wishes to make investment in Delta State
by citing their Base-Transceiver Stations (BTS) around the State. Using the
various computational thinking concepts of: logical reasoning, algorithm,
decomposition, abstraction, patterns/generalization and evaluation – write
up a report with a detailed map of the area where you are assigned of the
road network and why you feel optimistic about the GSM network provision
and tele-penetration Project in Nigeria. (15-pages)
REFERENCES
Ojugo, A. A., Oyemade, D. A., & Allenotor, D. (2016). Solving For
Computational Intelligence the Timetable-Problem Advances in.
Advances in Multidisciplinary and Scientific Research Journal, 2(2),
67–84.
1. Barefoot Computing, available at [web]: barefootcas.org.uk/barefoot-

primarycomputing-resources/concepts/abstraction/
2. BBC Bitesize, ‘Abstraction’, available at: www.
bbc.co.uk/education/guides/zttrcdm/revision.
3. BBC Cracking the Code, ‘Simulating the Experience of F1 Racing
Through Realistic Computer Models’, available at: www.bbc.co.uk/
programmes/p016612j.
4. Google for Education, ‘Solving Problems at Google Using
Computational Thinking’, available at:
www.youtube.com/watch?v=SVVB5RQfYxk.
5. The Art of Abstraction – Computerphile’, available at:
www.youtube.com/watch?v=p7nGcY73epw.
All Correspondence:
Ojugo Arnold P.A.C
College of Sports and Science Education
Department of Computer Science
Mosogar, Delta State
Tel: 08050331178, 08034072248
We value your opinion – Please share it with us to help us improve.

1. Please Rate this text by ticking the ones that apply S for Superior,
BTM for Better than Most, A for Average and P for Poor.
Items Stated S BTM A P
Author’s Writing Style
Readability and Organisation
Layout And Design
Understandability And Clarity
Illustration And Photos
Examples, Problems & Exercises
Topic Selection
Explanation Of Difficult Concepts
Application To Real Life
How Current is Text Coverage
2. List the chapter(s) you were not taught properly due to textbook
____________________________________________________
3. State the chapters you do not liked to be in this textbook_______
______________________________________________________
4. State the chapters you liked least __________________________
5. State the chapters that you liked best_______________________
_____________________________________________________
6. What topics do you think should be covered, make it concise.___
_________________________________________________________
_________________________________________________________
7. Do you plan to sell the text after usage? ____Yes _____No
8. Why? ____________________________________________________
9.

Problem Solving Chapter1!3!115749

Uploaded by

Copyright:

Available Formats

Problem Solving Chapter1!3!115749

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Problem Solving Chapter1!3!115749

Uploaded by

Copyright:

Available Formats

Chapter One

LET THERE BE – JUST…PROBLEMS!

Problem Solving is the science, art and process of generating

Many concepts for problem solving apply to both kinds/types

There are four (4) approaches to a problem namely:

To solve a problem, five (5) conditions should exist namely:

If one or more of these conditions is found to be missing, our

Thus, every problem/task is defined by its elements and their

Thus, a problem can be solved simply by using the rules, in

No wonder the Nigerian Universities Commission (NUC) has

Even graduates today – experience great difficulty in solving

Higher-order thinking can be conceptualized as a complex

The complexities and dynamics of critical thinking is evident

Living in a knowledge-based, digital revolution era with the

Discovering Knowledge Data

The KDD process typically consists of the following steps:

Figure 1.1. Knowledge Discovery in Database (Data Mining)

The Many Definitions of PS

b. 1980‟s: A framework describing the PS process, and

c. 2000‟s: While early work on PS focused mainly on

The knowledge and experience of a problem solver also

In some cases, the relations are weighted. For example, the

A graph is either be directed (noting that it depicts the flow

Figure 1.1. (a) Graph (b) Trees

Formal Description to Problem Solving

For Example: The Tower of Hanoi puzzle/game has the

Problem Description of the 8-Queen Problem

The Tree Structure

Properties of a tree is as thus:

The Stack Structure

Figure 1.6(a) Stack

Figure 1.6(b) Insert / Delete

The Queue Structure

Figure 1.7(a) Queue

Properties of the queue are:

Figure 1.6(b) Dequeue / Enqueue

Basic Working Idea of the Linear Search:

Algorithm Listing for the Linear Search Algorithm

Pseudocode Listing for the Linear Search Algorithm

while (index < x && !found)

Example: Suppose in a list of 10-elements, we are to search

Step 1: It compares the x with first element located at index

Step 3: It compares x with next element located at index 2.

Step 4: It compares x with first element located at index 3.

Step 5: It compares x with first element located at index 4.

Note: If the function had gone through to the last element

Binary Search – is the most popular search as it is based

Basic Working Idea of the Linear Search:

Pseudocode Listing for the Binary Search Algorithm

Complexity analysis: Time complexity in best case is O(1),

Example: Suppose in a list of 10-elements, we are to search

Step 2: As X > mid, so low become mid+1; and high remain

Step 3: As X > mid, so low becomes mid+1 and high remain

2. The Average case occurs in linear search algorithm.

3. Binary search algorithm cannot be applied to.

4. Complexity of linear search algorithm is:

5. To find the location of an item in a set of items is ___

6. Worst-case time complexity of linear search algorithm is?

3. Define searching. Explain different types of searching.

2.0 DATA REPRESENTATION