Algorithm Specification and Data Abstraction

1. Algorithm and characteristics of an algorithm.
2. Rules to be followed for design and analysis of an algorithm.
3. The differentiation of data structures, file structures, and storage structures.
4. Top-down and bottom-up design approaches through examples.
5. Rules to be followed while writing the pseudo code of an algorithm.
6. Abstract data type and its necessity in a program.

1. Algorithm Specification and Data Abstraction
Dr. Ashutosh Satapathy
Assistant Professor, Department of CSE
VR Siddhartha Engineering College
Kanuru, Vijayawada
September 22, 2022
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

2. Outline
1
Algorithm Specification
Introduction to Algorithm
Algorithm Design and Data Structure
Analyzing an Algorithm
Algorithm Design Approaches
Pseudocode Conventions
2
Data Abstraction
Data Types
Abstract Data Types
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

3. Outline
1
Algorithm Specification
Introduction to Algorithm
Algorithm Design and Data Structure
Analyzing an Algorithm
Algorithm Design Approaches
Pseudocode Conventions
2
Data Abstraction
Data Types
Abstract Data Types
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

4. Introduction to Algorithm
Analgorithmis a well defined computational procedure that takes
some value, or set of values, as input and produces some value, or set
of values as output.
It is thus a sequence of computational steps that transform the input
into the output.
The algorithm describes a computational procedure for achieving that
input/output relationship.
An algorithm is a finite set of instructions which accomplish a
particular task.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

5. Introduction to Algorithm
Every algorithm must satisfy the following criteria.
1
Input:There are some (possibly empty) input data which are
externally supplied to the algorithm.
2
Output:There will be at least one output.
3
Definiteness:Each instruction/step of the algorithm must be clear
and unambiguous.
4
Finiteness:If we trace out the instruction/step of an algorithm, then
for all cases, the algorithm will terminate after a finite number of
steps.
5
Effectiveness:The steps of an algorithm must be sufficiently basic
that it can be carried out by a person mechanically using pen and
paper.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

6. Introduction to Algorithm
Algorithm 1Swap two numbers using third variable
1:start
2:readtwo values into two variables a, b
3:declarethird variable, temp
4:temp = a
5:a = b
6:b = temp
7:writea, b ▷Display a and b values
8:stop
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

7. Outline
1
Algorithm Specification
Introduction to Algorithm
Algorithm Design and Data Structure
Analyzing an Algorithm
Algorithm Design Approaches
Pseudocode Conventions
2
Data Abstraction
Data Types
Abstract Data Types
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

8. Algorithm Design and Data Structure
To write a computer program for solving a problem we must start with the
following four tasks:
Identify the data items and their relationship.
Find the operations that must be performed on these data items.
Determine the best method to represent these data items in
computer’s memory.
Select a suitable programming language which can efficiently code the
identified data representation.
Note
These data items can be arranged in different ways depending on the
logical relationship between them. Arrangement of these data items is
calleddata structures. E.g., arrays, records, lists, and files
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

9. Algorithm Design and Data Structure
Important
The storage of data in primary memory is called asdata structure
where as the storage of data in secondary memory is calledfile
structure.
The representation or the data structure in computer’s memory which
is known asstorage structure.
Selection of a programming language best suited to represent the
data structure.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

10. Outline
1
Algorithm Specification
Introduction to Algorithm
Algorithm Design and Data Structure
Analyzing an Algorithm
Algorithm Design Approaches
Pseudocode Conventions
2
Data Abstraction
Data Types
Abstract Data Types
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

11. Analyzing an Algorithm
Algorithms are designed using basic program constructs like sequence,
selection or branching, repetition, etc.
We need methods to separate bad algorithm from good ones and to
choose the most effective approach for our problem.
Inanalyzing an algorithm, the first approach is to check the
correctness of the algorithm.
Tracing the algorithm.
Checking the algorithm for logical correctness.
Implementing the algorithm.
Testing the algorithm, which can yield correct output for all possible
combinations of input values. This is calledprogram provingor
program verification.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

12. Analyzing an Algorithm
Another approach of analysis is to check the simplicity of the
algorithm.
The simplest way of solving the problem is not always the best one.
It is necessary to evaluate thecomplexityof the algorithm.
The complexity of the algorithm is determined in terms oftimeand
space.
These determine the amount of time and storage an algorithm may
require for execution.
Finally, predict the performance of the algorithm in thebest,worst,
andaveragecases.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

13. Outline
1
Algorithm Specification
Introduction to Algorithm
Algorithm Design and Data Structure
Analyzing an Algorithm
Algorithm Design Approaches
Pseudocode Conventions
2
Data Abstraction
Data Types
Abstract Data Types
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

14. Algorithm Design Approaches
Figure 1.1:
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

15. Algorithm Design Approaches
A complicated algorithm is split into small parts called modules, and
the process of splitting is known asmodularization.
Modularization significantly reduces the complications of designing an
algorithm and make its process more easier to design and implement.
It is necessary to evaluate thecomplexityof the algorithm.
In thetop-down approach, the complex module is divided into
submodules.
Inbottom-up approachbegins with elementary modules and then
combine them further.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

16. Algorithm Design Approaches
Basis for
Comparison
Top-down
Approach
Bottom-up
Approach
Basic
- Break the massive
problem into multiple
subproblems.
- Solves the low-level
problems and integrate
them into a larger one.
Process
- Submodules are
solitarily analyzed.
- Examine what data is
to be encapsulated, and
implies the concept of
information hiding.
Communication
- The communications
is less among modules.
- In this, modules must
have communication.
Redundancy
- Contain redundant
information.
- Redundancy can be
eliminated.
Table 1.1:
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

17. Algorithm Design Approaches
Algorithm 2Top-down approach: n
th
number in the Fibonacci sequence
Require:non-negative integer n
Ensure:F(n); n
th
number in the Fibonacci sequence.
1:functionF(n)
2:ifn≤1then
3: returnn
4:else
5: returnF(n−1) + F(n−2)
6:end if
7:end function
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

18. Algorithm Design Approaches
Algorithm 3Bottom-up approach: n
th
number in the Fibonacci sequence
Require:non-negative integer n
Ensure:n
th
number in the Fibonacci sequence.
1:ifn= 0 orn= 1then
2:printn
3:else
4:A←0
5:B←1
6:forI←2 tondo
7: Temp←A+B
8: A←B
9: B←Temp
10:end for
11:writeB
12:end if
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

19. Algorithm Design Approaches
Algorithm 4Top-down approach: Multiplication of 1 to n numbers
Require:non-negative integer n
Ensure:PRODUCT(n); Multiplication of 1 to n numbers.
1:functionPRODUCT (n)
2:ifn= 1then
3: return1
4:else
5: returnn∗PRODUCT(n−1)
6:end if
7:end function
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

20. Algorithm Design Approaches
Algorithm 5Bottom-up approach: Multiplication of 1 to n numbers
Require:non-negative integer n
Ensure:Multiplication of 1 to n numbers.
1:Result←1
2:forI←1 tondo
3:Result←Result∗I
4:end for
5:writeResult
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

21. Outline
1
Algorithm Specification
Introduction to Algorithm
Algorithm Design and Data Structure
Analyzing an Algorithm
Algorithm Design Approaches
Pseudocode Conventions
2
Data Abstraction
Data Types
Abstract Data Types
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

22. Pseudocode Conventions
Till now, we have described each step of an algorithm using natural
language like English. Here, we present most of our algorithms using
pseudocodesthat resembleCandPascal.
1
Comments begin with // and continue until the end of line.
2
Blocks are indicated with matching braces:{and}. The body of a
procedure also forms a block. Statements are delimited by ;
3
An identifier begins with a letter. The data types of variables are not
explicitly declared. The types will be clear from the context. Whether
it is global or local to a procedure will also be evident from context.
4
Compound data types can be formed with records.
node=record
{datatype1data1;
datatype2data2;
node∗link;}
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

23. Pseudocode Conventions
5
linkis a pointer to the record typenode. For example, ifppoints to
a record of typenode,p←data1stands for the value of the first
field. Ifqis a record of type node,q.data1denotes its first field.
6
Assignment of values to variables is done using theassignment
operatororleftwards arrow symbol.
variable:=expression; orvariable←expression;
7
There are two boolean valuestrueandfalse. In order to produce
these values, the logical operatorsand,orandnotand the relational
operators<,≤, =,̸=,≥and>are provided.
8
Elements of multidimensional arrays are accessed using [ and ]. E.g.,
ifAis a two dimensional array, the (i,j)
th
element of the array is
denoted asA[i,j]. Array indices start at zero.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

24. Pseudocode Conventions
9
The following statements are employed forwhile,foranddo...while.
while<condition>do
Statement1
Statement2
Statement n
end while
while<condition>do{
Statement1;
Statement2;
Statement n;}
10
The general form of aforloop is
forI←ltomstepsdo
Statement1
Statement2
Statement n
end for
forI:=ltomstepsdo{
Statement1;
Statement2;
Statement n;}
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

25. Pseudocode Conventions
11
The general form of ado...whileloop is
do
Statement1
Statement2
Statement n
while<condition>
do{
Statement1;
Statement2;
Statement n;}
while<condition>
12
Aconditional statementhas the following forms.
if<condition>then<statement>
if<condition>then<statement1>else<statement2>=0
13
We also employ the followingcasestatement.
case{
:<condition1>:<statement1>
:<condition2>:<statement2>
:else:<statement n>}
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

26. Pseudocode Conventions
14
Input and output are done using the instructionsreadandwrite.
15
There is only one type of procedure:AlgorithmorProcedure. An
algorithm consists of a heading and a body. The heading takes the
form.
AlgorithmName(<P1,P2, ...,P3>)
Algorithm 6Maximum of n given numbers
1:procedureMAX(A,n)
2:Result←A[1]
3:fori←2 tondo
4: ifA[i]>ResultthenResult←A[i]
5: end if
6:end for
7:returnResult
8:end procedure
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

27. Pseudocode Conventions
Algorithm 7Selection Sort
1:procedureSelectionSort(a,n)
2://Sort the array a[1 :n]into ascending order.
3:fori←1 tondo
4: j←i
5: fork←i+ 1 tondo
6: ifa[k]<a[j]thenj←k
7: end if
8: end for
9: t←a[i]
10: a[i]←a[j]
11: a[j]←t
12:end for
13:end procedure
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

28. Pseudocode Conventions
Algorithm 8Towers of Hanoi
1:procedureTowerOfHanoi(n,x,y,z)
2:{
3://Move the top n disks from tower x to tower y.
4:ifn≥1then{
5: TOWEROFHANOI(n−1,x,y,z);
6: write(”move top disk from tower”, x, ”to top of tower”, y);
7: TOWEROFHANOI(n−1,z,y,x);
8:}
9:}
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

29. Outline
1
Algorithm Specification
Introduction to Algorithm
Algorithm Design and Data Structure
Analyzing an Algorithm
Algorithm Design Approaches
Pseudocode Conventions
2
Data Abstraction
Data Types
Abstract Data Types
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

30. Data Types
We are familiar with the basic data types of C. These includechar,
int,float, anddouble. Some of these data types may be modified by
the keywordsshort,long, andunsigned.
In addition to these basic types, C helps us by providing two
mechanisms for grouping data together. These are thearrayand the
structure.
For example, An array is a collection of elements of the same basic
data type.
They are declared implicitly, for example,int list[5]defines a
five-element array of integers whose legitimate subscripts are in the
range0 ... 4.
Structuresare collections of elements whose data types need not be
the same.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

31. Data Types
Data types are declarations for variables. This determines the type
and size of data associated with variables, and a set ofoperations
that act on thoseobjects.
Whether your program is dealing withpredefined data typesor
user-defined data types, these two aspects must be considered:
objectsandoperations.
For example, the data typeintconsists of the objects{0,+1,-1,
+2,-2, ...,INTMAX,INTMIN}, whereINTMAXand
INTMINare the largest and smallest integers that can be
represented on your machine.
The operations on integers are many, and would certainly include the
arithmetic operators+,-,*,/, and%.
There is also testing for equality/inequality and the operation that
assigns an integer to a variable.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

32. Data Types
Knowing all of the facts about the operations on a data type, we
might also want to know about how the objects of the data type are
represented.
E.g., acharis represented as a bit string occupying1 byteof
memory on most computers, where as anintmight occupy2or
possibly4 bytesof memory. If2 eight-bit bytesare used, then
INTMAXis215 -1=32,767.
Knowing the representation of the objects of a data type can be
usefulanddangerous.
It has been observed by many software designers that hiding the
representation of objects of a data type from its users is a good
design strategy.
In that case, the user is constrained to manipulate the objects solely
through the functions that are provided.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

33. Outline
1
Algorithm Specification
Introduction to Algorithm
Algorithm Design and Data Structure
Analyzing an Algorithm
Algorithm Design Approaches
Pseudocode Conventions
2
Data Abstraction
Data Types
Abstract Data Types
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

34. Abstract Data Types
AnAbstract Data Type (ADT)is a data type that is organized in
such a way that thespecificationof theobjectsand theoperations
on the objects is separated from therepresentationof the objects
and theimplementationof the operations.
Thespecificationconsists of thenamesof every function, thetype
of itsargumentsandresult.
There should also be a description of what the function does, but
without appealing to internal representation or implementation
details.
This requirement is quite important, and it implies that an abstract
data type isimplementation-independent.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

35. Abstract Data Types
ADT NaturalNumberis
Objects:An ordered sub-range of the integers starting at zero and ending
at the maximum integer(INT-MAX)on the computer.
Functions:for allx,y∈NaturalNumber;TRUE,FALSE∈Boolean,
where+,-,<, and==are the usual integer operations.
Functions Operations
NaturalNumberZero() 0
BooleanIsZero(x)
if (x) return FALSE
else return TRUE
BooleanEqual(x, y)
if (x == y) return TRUE
else return FALSE
NaturalNumberSuccessor(x)
if (x == INTMAX) return x
else return x+1
Table 2.1: NautralNumber
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

36. Abstract Data Types
Functions Operations
NaturalNumberAdd(x, y)
if (x+y<= INTMAX) return x+y
else return INTMAX
NaturalNumberSubtract(x, y)
if(x<y) return 0
else return x-y
Table 2.2: NautralNumber
TheADTdefinition begins with the name of the ADT. There are two
main sections in the definition: the objects and the functions.
The objects are defined in terms of the integers, but we make no
explicit reference to their representation.
For each function, we place the result type to the left of the function
name and a definition of the function to the right.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

37. Abstract Data Types
ADTis a type (or class) for objects whose behavior is defined by a
set of value and a set of operations.
The definition of ADT only mentions what operations are to be
performed but not how these operations will be implemented.
It does not specify how data will be organized in memory and what
algorithms will be used for implementing the operations.
It is calledabstractbecause it gives an implementation-independent
view. The process ofprovidingonly theessentialsandhiding the
detailsis known asabstraction.
A user only needs to know what a data type can do, but not how it
will be implemented. Think ofADTas ablack boxwhich hides the
inner structure and design of the data type.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

38. Abstract Data Types
Figure 2.1:
IfStack,QueueandLinked Listare theADTs, then{push(),
pop(), peep()},{enque(), dequeqe()},{insert(), delete()}are
the few operations performed on these data structures.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

39. Summary
Here, we have discussed
Algorithm and characteristics of an algorithm.
Rules to be followed for design and analysis of an algorithm.
The differentiation of data structures, file structures, and storage
structures.
Top-down and bottom-up design approaches through examples.
Rules to be followed while writing the pseudo code of an algorithm.
Abstract data type and its necessity in a program.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022

40. For Further Reading
H. Sahni and A. Freed.
Fundamentals of Data Structures in C (2
nd
edition).
Universities Press, 2008.
A. K. Rath and A. K. Jagadev.
Data Structures Using C (2
nd
edition).
Scitech Publications, 2011.
Dr. Ashutosh Satapathy Algorithm Specification and Data Abstraction September 22, 2022