Data Structures Chapter-2

mathematical notations and functions, algorithmic notations, control structures, complexity of algorithms, other asymptotic notations for complexity of algorithms, subalgorithms, variables, data types.

1. Preliminaries
Chapter-2
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

2. Mathematical Notations and Functions
•The following mathematical functions appear very
often in the analysis of algorithms and in computer
science.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

3. Floor & Ceiling Functions
•Let x be any real number.
•Then x lies between two integers called the floor and the ceiling of x.
•Լx┘called the floor of x, denotes the greatest integer that does not exceed x.
•Floor(3.14)=3
•Floor(-8.5)=-9
•ΓxꞀcalled the ceiling of x, denotes the least integer that is not less than x.
•Example
•Ceiling(3.14)=4
•Ceiling(-8.5)=-8
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

4. Remainder Function; Modular Arithmetic
•Let k be any integer and let M be a positive integer, then
•K Mod M
•Will denote the integer remainder when k is divided by M.
•More exactly, k Mod M is the unique integer r such that
•k = Mq+ r where 0 ≤ r < M
•Example:
•25 Mod 7 = 4 (25 = 7*3 + 4)
•35 Mod 11 = 2 (35 = 11*3 + 2)
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

5. Integer Function
•Let x be any real number.
•The integer value of x, written as INT(x) converts x into an
integer by deleting the fractional part of the number.
•INT(3.14)=3
•INT(-8.5)=-8
•OBSERVE:
•INT(x) = Floor(x)
•Or
•INT(x) = Ceiling(x)
oaccording to whether x is positive or negative.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

6. Absolute Value Function
•The absolute value of the real number x, written as ABS(x) or |x|
is defined as the greater of x or –x.
•ABS(0) = 0
•|-15| = 15
•|4.44| = 4.44
•Note that |x| = |-x|
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

7. Summation
•The summation symbol is ∑ (sigma).
•Consider the sequence a
1,a
2,a
3,… then the sums
•a
1+a
2+a
3…+a
n
and
•a
m+a
m+1+…+a
n
•Will be denoted respectively by
•σ
??????=??????
&#3627408527;
????????????
•σ
??????=&#3627408526;
&#3627408527;
????????????
•Here j is called as the dummy index or dummy variable.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

8. Factorial Function
•The product of the positive integers from 1 to n, inclusive, is
denoted by n!
•That is
•n! = 1 x 2 x . . . X (n-2) x (n-1) x n
•Example:
•4 ! = 1 x 2 x 3 x 4 = 24
•5 ! = 5 x 4! = 5 x 24 = 120
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

9. Permutations
❖A permutation of a set of n elements is an arrangement of
the elements in a given order.
❖For example, the permutations of the set consisting of the
elements a, b and c are as follows:
❖Abc
❖Acb
❖Bac
❖Bca
❖Cab
❖Cba
❖There are n! permutations of a set of n elements.M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

10. Exponents & Logarithms:
•Recall for any integer m,
•a
m
= a . a. . . . a (m times)
•a
0
= 1
•a
-m
=
1
&#3627408462;
??????
•Exponents are extended to include all rational numbers by
defining, for any rational number m/n,
•a
m/n
=
??????
??????
??????
= (
??????
??????)
m
•Exponents are extended to include all real numbers by
defining for any real number x,
•a
x
= lim
??????→??????
??????
??????
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

11. •Logarithms are related to exponents as follows.
•Let b be a positive number the logarithm of any positive
number x to the base b written as
•log
&#3627408463;??????
•Represents the exponent to which b must be raised to
obtain x. that is
•Y = log
&#3627408463;??????
and
•b
y
= x
•The logarithm of 0 and the logarithm of negative number
are NOT DEFINED.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

12. Algorithmic Notations.
1. Identifying Number
✓Each algorithm is assigned an identifying number.
✓Example Algorithm 4.3 refers to the 3
rd
algorithm in chapter 4.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

13. Algorithmic Notations.
2. Steps, Control, Exit
✓Each steps of the algorithm are executed one after the other, beginning
with step-1.
✓Control may be transferred to step n of the algorithm by the statement
“Go to Step n”.
✓These “goto” statements may be eliminated by using certain control
structures.
✓If several statements appear in the same step like SET K:=1, LOC:=1,
then they are executed from left to right.
✓The algorithm is completed with the statement EXIT.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

14. Algorithmic Notations.
3. Comments
✓Each step may contain a comment in brackets which indicates the
main purpose of the step.
✓The comment will usually appear at the beginning or at the end of
the step.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

15. Algorithmic Notations.
4. Variable Names
✓Variable names will use capital letters (Eg.MAX, DATA)
✓Single letter names of variables used as counters or subscripts will
also be capitalized in the algorithms.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

16. Algorithmic Notations.
5. Assignment statement
✓Assignment statements will use the dots-equal notation :=
✓Example MAX := DATA[1]
✓Will assign the value in DATA[1] to MAX.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

17. Algorithmic Notations.
6. Input and output
✓Data may be input and assigned to variables by means of Read
statement with the following form.
✓Read: Variable_names
✓Message placed in quotation marks and data in variables may be
output by means of a Write or Print statement with the following
form.
✓Write: Message and/or variable_names
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

18. Algorithmic Notations.
7. Procedures
✓This term is used for an independent algorithmic module which
solves a particular problem.
✓The use of the word Procedure or Module denotes it.
✓It is used to describe a certain type of sub-algorithm.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

19. 2.4 CONTROL STRUCTURES
Three types of logic or flow-of-control are used:
Sequence Logic (or) Sequential Flow
Selection Logic (or) Conditional Flow
Iteration Logic (or) RepratitiveFlow
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

20. Sequence Logic
•Unlessinstructionsgiventothe
contrary,themodulesareexecutedin
theobvioussequence.
•Thesequencemaybepreseted
explicitly,bymeansofnumbered
steps,orimplicitly,bytheorderin
whichthemodulesarewritten.
•Mostprocessingwillgenerallyfollow
thiselementaryflowpattern.
Module A
Module B
Module C
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

21. Selection Logic
•Employsanumberofconditionswhichleadtoaselectionofoneoutof
severalalternativemodules.
•Thestructureswhichimplementthislogicarecalledconditionalstructures
orIFstructures.
•Mostprocessingwillgenerallyfollowthiselementaryflowpattern.
•Theseconditionstructuresfallintothreecategories.
•Singlealternative
•Doublealternative
•Multiplealternatives
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

22. Selection Logic –Single Alternative.
•Ifthegivenconditionholds,thenModule-A,
whichmayconsistofoneormorestatements,
isexecuted;
•OtherwiseModule-Aisskippedandcontrol
transferstothenextstepofthealgorithm.
Structure
Ifconditionthen:
[Module-A]
[EndofIfStructure]
Condition?
Module -A
Yes
No
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

23. Selection Logic –Double Alternative.
•Ifthegivenconditionholds,thenModule-A,
getsexecuted;
•OtherwiseModule-Bisisexecuted.
Structure
Ifconditionthen:
[Module-A]
Else:
[Module-B]
[EndofIfStructure]
Condition?
Module -A
Yes
No
Module -B
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

24. Selection Logic –Multiple Alternatives.
•Thelogicofthisstructureallowsonlyoneofthemodulestobeexecuted.
•Eitherthemodulewhichfollowsthefirstconditionwhichholdsisexecuted,orthe
modulewhichfollowsthefinalElsestatementisexecuted.
Structure
Ifcondition-1then:
[Module-A1]
ElseIfcondition-2then:
[Module-A2]
…
Else:
[Module-B]
[EndofIfStructure]
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

25. Iteration Logic (Repetitive Flow)
•Refers to either of 2 types of structures involving loops.
•Each type begins with a Repeat statement and is followed by a
module, called the body of the loop.
•2 Types:
•Repeat-for loop
•Repeat-while loop.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

26. Iteration Logic –Repeat-for Loop
•Uses an index variable to control the loop (such
as I,jor k).
•Format:
Repeat for K = R to S by T:
[Module]
[End of loop]
•Here R is called the initial value, S the end
value or test value and T the increment.
•The body of the loop is executed first with K=R,
then with K=R+T, then with K=R+2T and so on.
•The cycling ends when K>s.
Is K > S ?
Module
[ body of loop]
No
Yes
K = K + T
K = R
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

27. Iteration Logic –Repeat-while Loop
•Uses a ocnditionto control the loop.
•Format:
Repeat while condition:
[Module]
[End of loop]
•The cycling continues until the condition si
false.
•Theremustbeastatementbeforethestructure
thatinitializestheconditioncontrollingthe
loop.
•There must be a statement in the body of the
loop that changes the condition.
Yes
condition?
Module
[ body of loop]
No
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

28. 2.5 COMPLEXITY OF ALGORITHMS
•Inorderto compare algorithms, we must have some criteria to
measure the efficiency of out algorithm.
•Suppose
•M is an algorithm, and
•n is he size of input data
•The time & space used by the algorithm M are the two main measures for
the efficiency of M.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

29. 2.5 COMPLEXITY OF ALGORITHMS
•ThecomplexityofanalgorithmMisthefunctionf(x)whichgives
therunningtimeand/orstoragespacerequirementofthe
algorithmintermsofthesizenoftheinputdata.
•Thestoragespacerequiredbyanalgorithmissimplyamultipleof
thedatasizen.
•Somostlytheterm“complexity”refertotherunningtimeofthe
algorithm.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

30. 2.5 COMPLEXITY OF ALGORITHMS
•Findingthecomplexityfunctionf(x)dealswith3casesin
complexitytheory.
•Worstcase:themaximumvalueoff(n)foranypossibleinput.
•Averagecase:theexpectedvalueoff(n)
•Bestcase:theminimumvalueoff(n).
Example–SearchinganelementinLinearsearchfashion:
•Worstcase:TheITEMisattheLASTpositionorNOTPRESENTinthelist.
•Averagecase:TheITEMappearsinthelist.
•Bestcase:TheITEMappearsattheFIRSTpositioninthelist.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

31. Rate of Growth; Big O Notation
•Suppose M is an algorithm with the size of input n, the complexity
f(n) of M increases as n increases.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

32. Rate of Growth; Big O Notation
•The rate of increase of f(n) is done by comparing f(n) with some
standard function such as log
2n, n log
2n, n
2
, n
3
, 2
n
•The rate of growth of these standard functions are indicated in
the below table
G(n)
Log n N N log n n
2
n
3
2
n
N
5 3 5 15 25 125 32
10 4 10 40 100 10
3
10
3
3100 7 100 700 10
4
10
6
10
30
1000 10 10
3
10
4
10
6
10
9
10
300
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

33. Rate of Growth; Big O Notation
•Supposef(n) and g(n) are functions with property that f(n) is
bounded by some multiple of g(n) for almost all n,
•Then we may write as
•F(n) = O(g(n))
•This is called as the “big O” notation.
•Example complexity functions of well-known searching and sorting
algorithms:
•Linear search : O(n)
•Binary search : O(log n)
•Bubble sort : O(n
2
)
•Merge sort : O(n log n)
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

34. 2.6 OTHER ASYMPTOTIC NOTATIONS FOR COMPLEXITY
OF ALGORITHMS Ω, ??????,??????
Omega Notation (Ω)
•The omega notation is used when the function g(n) defines a lower
bound for the function f(n).
•F(n) = Ω(g(n) ), iffthere exists a positive integer n
0and a positive
integer M such that |f(n)| >= M|g(n)|, for all n>= n
0
•For f(n)=18n+9, f(n)>18n for all n, hence f(n)= Ω(n)
•For f(n)=90n
2
+18n+6, f(n)>90n
2
for n
2
=0 and therefore f(n)= Ω(n
2)
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

35. 2.6 OTHER ASYMPTOTIC NOTATIONS FOR COMPLEXITY
OF ALGORITHMS Ω, ??????,??????
Theta Notation (??????)
•The theta notation is used when the function f(n) is bounded both
from the above and below by the function g(n).
•It implies that the function g(n) is both an upper bound and a
lower bound for the function f(n) for all values of n, n>= n
0.
•That is f(n) is such that f(n) = O(g(n)) and f(n) = Ω(g(n))
•F(n) = ??????(g(n) ), iffthere exists two positive constants c
1and c
2
and a positive integer n
0 such that c
1|g(n)| <= c
2 |g(n)|, for all
n>= n
0.
•For f(n)=18n+9, f(n)>18n for all n, hence f(n)= Ω(n)
•For f(n)=90n
2
+18n+6, f(n)>90n
2
for n
2
=0 and therefore f(n)= Ω(n
2)
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

36. 2.6 OTHER ASYMPTOTIC NOTATIONS FOR COMPLEXITY
OF ALGORITHMS Ω, ??????,??????
LittleOhNotation (o)
•F(n) = ??????(g(n) ), ifff(n)=O(g(n)) and f(n) ≠Ω(g(n))
.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

37. 2.7 SUBALGORITHMS
•A subalgorithmis a complete and independently defined
algorithmic module which is used by some main module or by
some other subalgorithm.
•A subalgorithm
•receives values called arguments, from an originating algorithm,
•performs calculations, and then
•sends back the result to the calling algorithm.
•The subalgorithmis defined independently so that it may be
called by many different algorithms or called at different times in
the same algorithm.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

38. 2.7 SUBALGORITHMS
•The subalgorithmwill have a RETURN statement instead of EXIT
statement. It implies that the control is transferred back to the
calling program when execution of the subalgorithmis completed.
•Subalgorithmsfall into 2 basic categories:
•Function subalgorithms–return only a single value to the calling algorithm.
•Procedure subalgorithms–can send back more than one value to the calling
algorithm.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

39. 2.8 VARIABLES, DATA TYPES
•Each variable in any of our algorithms has a data type which
determines the code that is used for storing its value. Four such
data types are:
•Character
•Real (floating point)
•Integer (fixed point)
•Logical
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

40. Local & Global Variables
•The organization of a computer program into a main program and
various subprograms has led to the notion of localand global
variables.
•Each program module contains its own lisof variables called local
variables, which can be accessed only by the particular module.
•Variables that can be accessed by all program modules are called
global variables.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.

41. Local & Global Variables
•There are 2 basic ways for modules to communicate with each
other:
•Directly, by means of well-defined parameters.
•Indirectly, by means of non-local and global variables.
M.Priyavani,MCA,DCHN,M.Phil, V.V.V.College for Women, Virudhunagar.