Unit-7 Algorithm Design and Problem
Solving
The Program Development
Life Cycle
When creating any new program, developers follow a
process called the program development life cycle.
It is a cycle and not a linear process because after
developing the software it is often necessary to go
back to the start of the process again if something
has been discovered during development
Four stages: Analysis, Design, Coding and Testing.
Analysis
Before any problem can be solved, it
needs to be clearly defined and set out
so anyone working on the solution
understands what is needed. This is
called the ‘requirements specification’
for the program.
The analysis stage uses Abstraction
and Decomposition tools to identify
exactly what is required from the
program.
Abstraction
Abstraction keeps the key elements
required for the solution to the problem and
discards any unnecessary details and
information that is not required
. For example,
a google map only shows what is required for
travelling from one place to another. Other parts
won’t be highlighted.
Decomposition
Decomposition breaks down a complex
problem into smaller parts, which can
then be subdivided into even smaller
parts, that can be solved easily. Any
daily task can be divided into its
constituent parts.
For example, getting dressed:
Select items to wear
Remove any clothes being worn
Put selected items on in order
Design
When the design stage is complete, the
programmer should know what is to be
done, i.e. all the tasks that need to be
completed, how each task is to be
performed and how the tasks work
together. This can be formally
documented.
All these tasks comprised up Design
phase.
Methods used to design and construct a solution to a problem
structure diagrams
flowcharts
pseudocode.
CODING
The program or set of programs is
developed. Each module of the program
is written using a suitable programming
language and then tested to see if it
works.
TESTING
The completed program or set of
programs is running many times with
different sets of test data.
This ensures that all the tasks
completed work together as specified in
the program design.
Iterative testing means that modular
tests are conducted, code amended,
and tests repeated until the module
performs as required.
Computer systems, sub-
systems
A computer system is made up of
software, data, hardware,
communications and people; each
computer system can be divided up into
a set of sub-systems.
Each sub-system can be further divided
into sub-systems and so on until each
sub-system just performs a single
action.
TOP DOWN DESIGN
Top-down design is the decomposition of a
computer system into a set of sub-systems, then
breaking each sub-system down into a set of
smaller sub-systems, until each sub-system just
performs a single action.
The process of breaking down into smaller sub-
systems is called STEPWISE REFINEMENT.
DECOMPOSING A PROBLEM
Any problem that uses a computer system for its
solution needs to be decomposed into its
component parts.
The component parts of any computer system are:
INPUTS
PROCESSES
OUTPUTS
STORAGE
Structure diagrams
Structure diagrams can be used to show top-
down design in a diagrammatic form.
Structure diagrams are hierarchical, showing
how a computer system solution can be divided
into sub-systems with each level giving a more
detailed breakdown.
Format of structure
diagram
Alarm app for a smart
phone
Consider the alarm app computer
system for a smart phone;
This could be divided into three sub -
systems,
1) setting the alarm,
2) checking for the alarm time,
3) sounding the alarm.
These sub-systems could then be further
sub-divided;
Flowcharts
A flowchart is a diagrammatic way of
displaying the steps required to
complete a task and the order that they
are to be performed.
Symbols used in flowchart
Example
How to make a cup of tea using a
flowchart.
Pseudocode
Pseudocode is a useful way of
designing solutions as it can be written
in a way that doesn’t require exact use
of the same syntax as any particular
programming language.
It only uses few programming construct
to show the logic.
Example
A 10
B 20
IF A<B
THEN
OUTPUT ”A is smaller number”
ELSE
OUTPUT ”B is smaller number”
ENDIF
Pseudocode for Selection Statement
Conditional statements are used to decide
which action should be taken.
It is used when to make decisions.
There are two types of conditional statement:
1. IF … THEN … ELSE … ENDIF
:a condition that can be true or false
2. CASE OF …OTHERWISE … ENDCASE
:a choice between several different values
IF … THEN … ELSE … ENDIF statement
For an IF condition the THEN path is
followed if the condition is true and the
ELSE path is followed if the condition is
false.
There may or may not be an ELSE path.
The end of the statement is shown by
ENDIF.
Example: if…then…else…
endif
Comparison operators
Example-2
CASE OF … OTHERWISE … ENDCASE
statement
For a CASE statement the value of the
variable decides the path to be taken.
Several values are usually specified.
OTHERWISE is the path taken for all other
values. The end of the statement is shown
by ENDCASE.
Example-1: CASE OF …OTHERWISE …
ENDCASE
Example-2
pseudocode for iteration(Loops)
When some actions performed as part of an
algorithm need repeating this is called iteration.
Loop structures are used to perform the
iteration.
1. FOR … TO … NEXT(Count Controlled Loop)
2. REPEAT … UNTIL(Pre-Condition Loop)
3. WHILE … DO … ENDWHILE
(Post-Condition Loop)
FOR … TO … NEXT
This loop is used if we know a set number of
repetitions to be done.
REPEAT … UNTIL
A repetition, where the number of
repeats is not known, that is completed
at least once. Loop will work until the
condition becomes TRUE.
WHILE … DO …
ENDWHILE
A repetition, where the number of
repeats is not known. Loop will work
until the condition becomes FALSE.
NOTE:
FOR … TO … NEXT loop is the most
efficient way for a programmer to write this
type of task as the loop counter is
automatically managed.
ALGORITHM
The steps, together with an order, are
called as an algorithm.
It is used to show the solution of a problem.
Example:
1) Take vessel
2) Add water and boil it
3) Add sugar and milk to it.
4) Then, add tea leaves to it.
5) Boil it for few more minutes, then serve it.
Solution Methods using
Algorithm
Algorithms can search and sort data,
find totals and count data, and also carry
out functional operations such as finding
the maximum, minimum and average
values.
LINEAR SEARCH
BINARY SEARCH
BUBBLE SORT etc.
LINEAR SEARCH
This type of search means that all items
of data in a set are looked at until the
program matches the piece of data it is
looking for. Once this match is obtained,
the search is completed.
Bubble Sort
A bubble sort is another standard solution
algorithm to make a data set in
order(Ascending/Descending).
A bubble sort is based upon the idea of
swapping adjacent items in a data set until the
set is in the desired order.
Totalling and
Counting
Totalling: a common algorithm used to
add one number to an existing stored
number.
Total←Total+Marks
Counting: keeping a check on how
many times a program has repeated a
procedure in a loop.
Count←Count+1
Data Validation
Validation is the automated checking by
a program that data is reasonable
before it is accepted into a computer
system.
If the data does not follow the rules set
by the checks, the data will be rejected
by the program.
Types of validation check
Verification
Verification is checking that data has
been accurately copied from one source
to another –
for instance, input into a computer or
transferred from one part of a computer
system to another.
There are two methods of verifying data that has
been entered:
• Double entry: The same data is entered twice and
the first entry is checked against the second
one. For example, a system requires a password
and asks the user to enter it a second time to
ensure it is an absolute match.
• Visual check: A human check for erroneous data
that has been entered into a system and trying
to spot obvious errors or mistyping
Testing
It is the method of check and assessing
how the software/system/program
behaves and gives the expected results
or not using test data.
Testing also test the program whether
the test data is following validation rules
or not.
Testing data
There are four types of testing data:
• normal data
• extreme data
• abnormal / erroneous data
• boundary data
Trace Tables
A trace table is set up with a column for
each variable and a column for any output.
A trace table can be used to record the
results from each step in an
algorithm/pseudocode/flowchart
It is used to record the value of an item
(variable) each time that it changes.
The manual exercise of working through an
algorithm/pseudocode/flowchart step by
step is called a DRY RUN.
During a dry run:
every time the value of a variable is
changed, the new value is entered in
that column of the trace table
every time a value is output, the value is
shown in the output column.
Error Checking and Correction
• Syntax error: Some of the code goes against the
rules/ grammar of the language that has been
written for the program. This can be a misspelling of
a common word, omitting brackets etc..
Example:
A 10
20 B
OUTPUT B
OUTPUT A
Logic error: A program behaves unexpectedly
and produces unusual results. This type of error
can occur when logic of the program is wrongly
written.
Eg. Wrong placement of loops, doing addition
instead of subtraction etc.
1 INPUT(“How old are you: “, Age)
2 IF Age >= 13
3 OUTPUT(“Child fare”)
4 ELSE
5 IF Age <=12
6 OUTPUT(“Adult fare”)