G.

PULLA REDDY ENGINEERING COLLEGE (AUTONOMOUS)

DEPARTMENT OF ECS

SUBJECT: Advanced Data Structures and Algorithm Analysis

III SEM

By
Dr. K. Srinivasa Rao
Professor
Department of ECS
 SYLLABUS
UNIT – I
Introduction to Algorithm Analysis, Space and Time Complexity analysis,
Asymptotic Notations.

AVL Trees – Creation, Insertion, Deletion operations and Applications.

B-Trees – Creation, Insertion, Deletion operations and Applications.

Heap Trees (Priority Queues) – Min and Max Heaps, Operations and
Applications.
UNIT – II
Graphs – Terminology, Representations, Basic Search and Traversals - BFS,
DFS, Biconnected Components & DFS.

String Searching Algorithms: Brute-Force algorithm, Robin-Karp algorithm,

Boyer-Moore algorithm.
 UNIT - III
Divide and Conquer – The General Method, Quick Sort, Merge Sort,
MaxMin problem, Strassen’s matrix multiplication.

Greedy Method – General Method, Job Sequencing with deadlines,

Knapsack Problem, Minimum cost spanning trees, Single Source Shortest
Paths.

UNIT – IV
Dynamic Programming – General Method, Multistage Graph – Forward
approach and Backward approach, All pairs shortest paths, Optimal Binary
Search Trees, 0/1 Knapsack, String Editing, Travelling Salesperson
problem.
 UNIT - V
Backtracking – General Method, 8-Queens Problem, Sum of Subsets
problem, Graph Coloring, Hamiltonian Cycle problem

Branch and Bound – The General Method, Job Sequencing with deadlines
problem, 15 Puzzle problem, Travelling Salesperson problem.
 Text Books

 1. Fundamentals of Computer Algorithms by Ellis Horowitz, Sartaj Sahni

& Sanguthevar , Rajasekaran Universities Press, 2nd Edition or Galgotia.
 2. Data Structures and Algorithm Analysis in C, Mark Allen Weiss,

Pearson, Second Edition 2005.

 3. Algorithms in C, Robert Sedge wick, Addison-Wesley Publishing

Company, 2016

07/21/25
 References

1 . Data Structures and program design in C, Robert Kruse, Pearson

Education Asia.
 2. Introduction to Data Structures with applications, Trembley &

Sorenson, McGraw Hill

 3. The Art of Computer Programming, Vol.1: Fundamental Algorithms,

Donald E Knuth, Addison-Wesley, 1997.

 4. Algorithms + Data Structures & Programs:, [Link], PHI.

07/21/25
 Introduction:
• About ADSA

• Data

• Data structure

• Operations

• Algorithm

• Characteristics / Properties

• Steps/ phases involved in studying the

algorithm or to solve the problem

 INTRODUCTION

Algorithm is a set of steps to complete a task.

For example,

Task: to make a cup of tea.

Algorithm:
• add water and milk to the kettle,
• boil it, add tea leaves,
• add sugar, and then serve it in cup.

07/21/25
Characteristics / Properties
Algorithm should contain a finite number of steps
and each step may involve one or more
operations.
Definiteness: each instruction must be clear and
unambiguous;
 Effectiveness: Every instruction must be
sufficiently basic that it can in principle be carried
out by a person using only pencil and paper.
Input: there are zero or more quantities, which are
externally supplied;
Output: at least one quantity is produced;
Algorithm will terminate after a finite number of
steps or operations.
 How To Write an Algorithm
Step-1:start Step-1: start
Step-2:Read a,b,c Step-2: Read a,b,c
Step-3:if a>b Step-3:if a>b then go to step 4
if a>c otherwise go to step 5
print a is largest Step-4:if a>c then
else print a is largest otherwise
if b>c print c is largest
print b is largest Step-5: if b>c then
else print b is largest otherwise
print c is largest print c is largest
Step-4 : stop step-6: stop
 Differences

Algorithm Program
1. At design phase 1. At Implementation phase
2. Natural language 2. written in any programming
language

3. Person should have

domain knowledge 3. Programmer
4. Analyze 4. Testing
Phases or steps to solve the
Problem:

How to devise an algorithm ? – Choose the right strategy

How to express algorithm ? – writing algorithm

How to validate algorithm ? – Once an algorithm is created

it is necessary to show that it computes the correct output for all

possible legal input.
How to analyze algorithm ? - Analysis of an algorithm

or performance analysis refers to task of determining how

much computing time & storage algorithms required.

How to test a program - Testing a program really

consists of two phases: Debugging and Profiling.

Pseudocode:

It is a simplified, human-readable representation of

an algorithm or program, using a mix of natural
language and programming-like syntax.
Pseudo Code Constructs:
• Comments //
• Only Structured data types

eg: int A[size]

• Compound data types can be formed with
“record”
node = record
{ datatype1 variable1, 2 etc;
datatype2 variable1, 2, etc;
node *link;
}
Assignment :-
variable := expression or value
Loops:

 Repeat

statement 1

statement 2

…………

until < condition>

 The statements are executed as long as <Condition> is false
• for index := initial value TO final value
step by 1 do

}
• while <condition> do

}
• Conditional statements:

• if <condition> then

statement / statements
• if <condition> then

statement / statements

else

statement / statements
• case

{ : <condition 1> : statement 1

: <condition 2> : statement 2

: <condition n> : statement n

: else: statement n+1

}
Structures of the Algorithm:
Algorithm Name(parameter list)

declarations;

statements;

}
• To call a function

call Name();
 ADSA Lab Experiments (Turbo C)
Cycle-1
1. Write a C Program to merge two sorted arrays into a single sorted array.

2. Write a C Program to merge two sorted Double Linked list into one sorted
resultant Double Linked List.

3. Write a Program to Implement a binary Search using sorted array. (Find

multiple occurrence of a key if any)

4. Write a C Program to implement Binary Search Tree and perform the

following operations.

Menu
1. Insert
2. Delete
3. Prorder Traversal
4. In order Traversal
5. Post order Traversal
6. Exit
 Analysis of Algorithm
• Estimating the space and time Complexity

a) To determine what operations to be

performed and what are its relative cost

b) Study the behaviour of the algorithm by

using various data sets

Analysis is performed in one of the two

phases:
a) Posterior Analysis
– Machine, plat form, Language
b) Priori Analysis
- Based on Datasets and operations
PRIORI POSTERIORI
[Link] priori to run algorithm [Link]
after running it on a on system.
specific system
[Link] independent [Link]
on hardware
[Link] analysis [Link]
statistics of an algorithm
[Link] on [Link] do not depend
number of times statements
are executed
• The efficiency is mainly to find out Space and Time.

• Space Complexity: It is defined as the amount of

memory needed to run the completion of the
algorithm.
• Fixed Part : Memory needed to store Programs,

variables, functions etc.

• Variable Part: Memory required for reference
variables, stack space, dynamic allocation etc. It
depends on the instance.
• Eg:- Stack (Factorial)n, linked list , function calls etc
Space requirement S(P) of any algorithm P
is equal to—
S(P) = C + Sp
Where C is a constant.
• Space Complexity: Fixed part

• Example 1:
Statement

Algorithm evalu( a,b,c) 1) Space to store the

instructions
{ 2) Space for variables :
3
Return (a+b+c)/3 3) Variable part is 0
} So,
• Since, the space needed by ‘evalu’ is independent
SP=0 (Since we are not string 3 values)
of the instance characteristics.
• Space Complexity: Fixed part

• Example 2:
Statement
Algorithm Sum( a, n)
{ Space is fixed size only
S := 0.0 1) Space to store the
instructions
for i:=1 To n do 2) Space for variables :
n+3
S:= S + a[i] 3) Variable part is 0
return S
}
1. Space needed by ‘n’ is one word and space needed
by ‘a’ is the space needed by variables of type of
floating-point numbers.
2. ‘a’ must be large enough to hold ‘n’ elements.

Therefore, S P >= (n+3) ( n for a[], one each for n, i ,

• Space Complexity: Variable part

• Example 3:

Statement
Algorithm Rsum( a, n)
{ Space is variable size
only
If (n<=0) then 1) Space to store the
instructions
return 0.0 2) Space for variables
based on instance : n
else return ( Rsum(a,n- Stack space is space for
1) + a[n]) formal parameters, local
variables and the return
addresses etc
} In recursive call uses 3
spaces
One Space Pointer
refer for value to a
• Time Complexity: The time complexity of the
program is sum of compilation time and run time.
• Compilation time: It is fixed time.

• Run time : It depends on instance characteristics as

well as the time required for operations.

T(P) = C + tp(n)

• tp(n) = Ca Add(n) + Cs Sub(n) + Cm Mul(n) + Cd Div(n)

+ etc

• Ca, Cs are the cost or time required to perform

respective operations.
• Add(n), Sub(n) etc are the no of additions,
• Time Complexity:

• Input size, operations to be performed and frequency of

execution of statements.
• Step table . i.e S/e – Steps per execution

• Example 1:

Statement S/e Frequen Total

cy steps
Algorithm Sum( a, n) 0 0 0
{ 0 0 0
S := 0.0 1 1 1
for i:=1 To n do 1 n+1 n+1
S:= S + a[i] 1 n n
return S 1 1 1
} 0 0 0
Total Steps : 2n+3
For each step one unit of time, so total time is 2n +3
• Time Complexity:

• Example 2:

Statement Frequenc Total

S/e y steps
n<= n> n<= n>
0 0 0 0
Algorithm Rsum( a, n) 0 0 0 0 0
{ 0 0 0 0 0
If (n<=0) then 1 1 1 1 1
return 0.0 1 1 0 1 0
else return ( Rsum(a,n-1) 1 0 1 0 1+
+ a[n]) +x x
} 0 0 0 0 0
Total Steps : 2 2+
x
Where X=t Rsum(a,n-1)
• Time Complexity:

• Example 3:

Statement Frequenc Total

S/e y steps
Algorithm Add( a,b,c,m, n) 0 0 0
{ 0 0 0
for i:=1 To m do 1 m+1 m+1
for j:=1 To n do 1 m(n+1) mn+m
c[i,j]:=a[i,j]+b[i,j] 1 mn mn
} 0 0 0
Total Steps : 2mn+2m
+1
 KINDS OF ANALYSIS

[Link]-case: (usually)
• T(n) = maximum time of algorithm on any input of size n.

[Link]-case: (sometimes)
• T(n) = expected time of algorithm over all inputs of
size n.
• Need assumption of statistical distribution of inputs.

[Link]-case:
• T(n) = minimum time of algorithm on any input of size n.

COMPLEXITY:
Complexity refers to the rate at which the storage time grows as a
function of the problem size
• Asymptotic Notation:

An algorithm may not have the same performance for different types of inputs.

With the increase in the input size, the performance will change.
Asymptotic analysis accomplishes the study of change in performance of the

algorithm with the change in the order of the input size.

Using Asymptotic analysis, we can very well define the best case, average case,

and worst case scenario of an algorithm.

• Asymptotic Notation:

• It is represented by the symbols O, Ω and θ .

• Order of magnitude: It is the frequency of execution of
statements. The order of magnitude of algorithm is sum of
frequencies of all the statements. The running time of an
algorithm is the sum of input and number of operations to
be performed.
• It is represented by T(n) where n is the input or output..
• Asymptotic Notation:

• Time complexity: Y axis is growth of a function f

and X axis is n values

0(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3)
< 0(2•)
 Example
Example : f(n)=3n +2 & g(n)= n
Formula : f(n)<=c g(n) n>=n0 , c>0 ,n0
>=1
f(n)=3n+2 & g(n)=n
Now 3n+2<=c.n
3n+2<=4.n
Put the value of n =1
5<=4 false
n=2 8<=8 true now n0>2 For all value of n>2 & c=4
now f(n)<= c.g(n)
3n+2<=4n for all value of n>2
Above condition is satisfied this notation takes maximum amount of
time to execute .so that it is called worst case complexity.

Therefore, f(n) = O(g(n))

 Example
Example :
f(n)=3n +2 and g(n)=n
Formula : f(n)>=c g(n) n>=n0 , c>0 ,n0
>=1
f(n)=3n+2
3n+2>=1*n, c=1 put the value of n=1
n=1 5>=1 true n0>=1 for all value
of n
It means that f(n)= Ω g(n).
 Example
Example :
f(n)=3n+2 & g(n)=n
Formula : c1 g(n)<=f(n)<=c2 g(n)
f(n)=3n+2 , g(n)=n
1*n<=3n+2<=4*n now put
the value of n=1 we get 1<=5<=4 false
n=2 we get 2<=8<=8 true
n=3 we get 3<=11<=12 true
Now all value of n>=2 it is true above condition is satisfied.

Therefore, f(n) = Ø(g(n))

1 1 2
2 4 4
3 9 8
4 16 16
5 25 32
6 36 64
7 49 126
 [Link] oh notation
Little o notation is used to describe an upper
bound that cannot be tight. In other words,
loose upper bound of f(n).
Slower growth rate
f(n) grows slower than g(n)
Let f(n) and g(n) are the functions that map
positive real numbers. We can say that the
function f(n) is o(g(n)) if for any real positive
constant c, there exists an integer constant n0
≤ 1 such that f(n) > 0.
 Using mathematical relation, we can say that f(n)
= o(g(n)) means,
if

 Example on little o asymptotic

notation:

[Link] f(n) = n2 and g(n) = n3 then check

whether
f(n) = o(g(n)) or not.
Sol:

The result is 0, and it satisfies the equation

mentioned above. So we can say that f(n)
= o(g(n)).
 [Link] omega(ω) notation
Another asymptotic notation is little omega
notation. it is denoted by (ω).
Little omega (ω) notation is used to describe a
loose lower bound of f(n).
Faster growth rate
F(n) grows faster than g(n)

If

Formally stated as f(n)=ωg(n)