Lesson 3 - Program Design using Algorithms
Computer problem solving is the use of computers to solve problems. Most of
the problems that the computers can solve will involve collection, storage
and manipulation of information.
To a developer, the problem is viewed from a developmental perspective.
The problem is to develop a computer based system or write a computer
program.
Steps in computer based problem solving
i. Identify the problem – decide on what the program should do.
ii. Formulate and represent a procedure for solving the problem without the
use of a computer (algorithm).
iii. Represent the algorithm using any acceptable convention (flowcharts or
pseudo codes).
iv. Check that the algorithm works.
v. Write a computer code from the algorithm.
vi. Test the computer code and complete its documentation (written
material explaining the code and the program).
[Link] the final program.
viii. Run or use the computer program.
An algorithm is the series of steps that are used to solve a programming
problem.
It may also be considered as a plan for solving a programming problem that
specifies the sequence of steps used in the solution.
The following are mandatory features that an algorithm must have:
i. An algorithm must have a start and an end point.
ii. Every step must be doable or performable:-
iii. using a finite amount of effort;
iv. in a finite amount of time.
PAGE \* MERGEFORMAT 12 | Page
In summary an algorithm will consist of a series of steps solving a problem.
There must be a starting point and an ending point and each step is
something the computer can do and finish. So the format of an algorithm is:
start, step1, step2, , , , , stepn, stop. Generally the steps are numbered or
labeled from start to stop.
Representing algorithms
The most common means of representing algorithms is by the use of
flowcharts or pseudo code.
Flowcharts
Flowcharts consist of a set of conventional symbols that are given below:-
Start/Stop
Startand
Top-down Stop
Input/Output
Process box/Calculations
Use not more than two statements in each box.
PAGE \* MERGEFORMAT 12 | Page
Decision/Selection box
Direction line (next step)
i. Natural left to right (no arrow indicator)
ii. Natural top to down ( no arrow indicator)
iii. Other directions are indicated:
Preparation box and Connection circle
Pseudocode
Pseudo codes are mixture of English statements and terms that are used in
programming. The programming terms may include: START, BEGIN, END,
STOP, IF, THEN, WHILE, ENDWHILE, REPEAT, FOR, UNTIL, DISPLAY, WRITE,
READ, etc.
Main programming constructs
Programming constructs are the building blocks that are used to in parts of a
program.
There are only three programming constructs. These are
PAGE \* MERGEFORMAT 12 | Page
i. sequence
ii. repetition
iii. selection
Algorithms Practical Examples
Pseudocode
Algorithm to read in, display and exchange two integer values
Save Variable_A = 500 while Variable_B = 300.
iv. Start
v. Set up variables
vi. Initialize variables
vii. Read in value of Variable_A
[Link] in value of Variable_B
ix. Display value of Variable_A
x. Display value of Variable_B
xi. Copy value of Variable_A into Temporary
xii. Copy value of Variable_B into Variable_A
[Link] value of Temporary into Variable_B
xiv. Display value of Variable_A
xv. Display value of Variable_B
xvi. Stop
Flowchart
PAGE \* MERGEFORMAT 12 | Page
An algorithm that reads & displays a set of 6 numbers
Track the number of times reading is done by setting up a counter. When 6
numbers have been read, stop.
Algorithm
i. Start
ii. Setup variables: Number, Count
iii. Initialize variables: Number:=0; Count:=0;
iv. Read Number
v. Display Number
vi. Increase Count by 1
PAGE \* MERGEFORMAT 12 | Page
vii. If Count<6 Repeat from 4
[Link]
Pseudocode
START START
Variables: Number, Count Variables: Number, Count
Number=0 Number=0
Count=0 Count=0
REPEAT DO WHILE Count<6
Read Number Read Number
Display Number Display Number
Increase Count by 1 Count=Count + 1
UNTIL Count<6 ENDWHILE
STOP STOP
Flowchart
PAGE \* MERGEFORMAT 12 | Page
An algorithm to compute and display the sum of n numbers
Let the numbers be 5,3,4,5,10,30 but they could be any numbers.
ALGORITHM
i. Start
ii. Set up variables: Sum, Count, Number, Number_of_items
iii. Initialize variables (Sum:=0; Count:=0; Number:=0)
PAGE \* MERGEFORMAT 12 | Page
iv. Read Number_of_items
v. Read a Number
vi. Add 1 to count
vii. Add Number to Sum
[Link] Count<Number_of_items then repeat from 5
ix. Display Sum
x. Stop
Flowchart
PAGE \* MERGEFORMAT 12 | Page
Pseudocode
i. START
ii. Setup variables: Sum, Count, Number, Number_of_items
PAGE \* MERGEFORMAT 12 | Page
iii. Initialize Variables to 0
iv. READ Number_of_items
v. REPEAT
vi. READ Number
vii. Add 1 to Count
[Link] Number to Sum
ix. UNTIL Number_of_items=6
x. DISPLAY Sum
xi. END
Top-down and Bottom-up Decomposition
Introduction
The algorithms are designed using two approaches that are the top-down
and bottom-up approach. In the top-down approach, the complex module is
divided into submodules. On the other hand, bottom-up approach begins
with elementary modules and then combine them further. The prior purpose
of an algorithm is to operate the data comprised in the data structure. In
other words, an algorithm is used to perform the operations on the data
inside the data structures.
A complicated algorithm is split into small parts called modules, and the
process of splitting is known as modularization. Modularization significantly
reduces the complications of designing an algorithm and make its process
easier to design and implement. Modular programming is the technique of
designing and writing a program in the form of the functions where each
function is distinct from each other and works independently. The content in
the functions are cohesive in manner, and there exists a low coupling
between the modules.
Definition of Top-down Approach
The top-down approach basically divides a complex problem or algorithm
into multiple smaller parts (modules). These modules are further
decomposed until the resulting module is the fundamental program
essentially be understood and cannot be further decomposed. After
achieving a certain level of modularity, the decomposition of modules is
ceased. The top-down approach is the stepwise process of breaking of the
PAGE \* MERGEFORMAT 12 | Page
large program module into simpler and smaller modules to organize and
code program in an efficient way. The flow of control in this approach is
always in the downward direction. The top-down approach is implemented in
the “C” programming language by using functions.
Thus, the top-down method begins with abstract design and then
sequentially this design is refined to create more concrete levels until there
is no requirement of additional refinement.
Definition of Bottom-up Approach
The bottom-up approach works in just opposite manner to the top-down
approach. Initially, it includes the designing of the most fundamental parts
which are then combined to make the higher level module. This integration
of submodules and modules into the higher level module is repeatedly
performed until the required complete algorithm is obtained.
Bottom-up approach functions with layers of abstraction. The primary
application of the bottom-up approach is testing as each fundamental
module is first tested before merging it to the bigger one. The testing is
accomplished using the certain low-level functions.
Top-down Approach Vs Bottom-up Approach
Comparison Chart
PAGE \* MERGEFORMAT 12 | Page
BASIS FOR
TOP-DOWN APPROACH BOTTOM-UP APPROACH
COMPARISON
Basic Breaks the massive problem Solves the fundamental
into smaller subproblems. low-level problem and
integrates them into a
larger one.
Process Submodules are solitarily Examine what data is to
analysed. be encapsulated, and
implies the concept of
information hiding.
Communication Not required in the top-down Needs a specific amount
approach. of communication.
Redundancy Contain redundant Redundancy can be
information. eliminated.
Programming Structure/procedural oriented Object-oriented
languages programming languages (i.e. programming languages
C) follows the top-down (like C++, Java, etc.)
approach. follows the bottom-up
PAGE \* MERGEFORMAT 12 | Page
BASIS FOR
TOP-DOWN APPROACH BOTTOM-UP APPROACH
COMPARISON
approach.
Mainly used in Module documentation, test Testing
case creation, code
implementation and
debugging.
Key Differences Between Top-down and Bottom-up Approach
1. Top-down approach decomposes the large task into smaller subtasks
whereas bottom-up approach first chooses to solve the different
fundamental parts of the task directly then combine those parts into a
whole program.
2. Each submodule is separately processed in a top-down approach. As
against, bottom-up approach implements the concept of the information
hiding by examining the data to be encapsulated.
3. The different modules in top-down approach don’t require much
communication. On the contrary, the bottom-up approach needs
interaction between the separate fundamental modules to combine
them later.
4. Top-down approach can produce redundancy while bottom-up approach
does not include redundant information.
5. The procedural programming languages such as Fortran, COBOL and C
follows a top-down approach. In contrast, object-oriented programming
languages like C++, Java, C#, Perl, Python abides the bottom-up
approach.
6. Bottom-up approach is priorly used in testing. Conversely, the top-down
approach is utilized in module documentation, test case creation,
debugging, etcetera.
Conclusion
PAGE \* MERGEFORMAT 12 | Page
The top-down approach and bottom-up approach are the algorithm design
methods where top-down is a conventional approach which decomposes the
system from high-level specification to low-level specification. On the other
hand, the bottom-up approach is more efficient and works in an inverse
manner where the primitive components are designed at first then
proceeded to the higher level.
The top-down approach emphasizes on the isolation of the submodules
(signifies the low coupling between the modules) while ignores the
identification of communication and reusability concept. While in the bottom-
up approach, information hiding and reusability are the prominent factors.
PAGE \* MERGEFORMAT 12 | Page