Syllabus

Data Structures with Algorithms

[As per Choice Based Credit System (CBCS) scheme]
Subject Code: MMC103
CIE Marks: 50 SEE Marks: 50 SEE Hours: 03
Course learning objectives:
This course (MMC103) will enable student to
[Link] understand and implement fundamental data structures.
[Link] develop efficient algorithms for solving problems.
[Link] analyze the time and space complexity of algorithms.
[Link] gain practical experience in applying data structures and algorithms to real-
world problems.
[Link] prepare students for industry roles requiring strong foundations in data
structures and algorithmic thinking.
 Syllabu
s MODULE 1
Introduction to Data Structures and Algorithms: Basic Concepts:
Definition and importance of data structures, Abstract Data Types (ADTs),
Algorithm analysis: Time and space complexity, Asymptotic notations.
Arrays: Definition and operations, Multidimensional arrays, Applications of
arrays.

Linked Lists: Singly linked list: Creation, insertion, deletion, traversal,

Introduction to Doubly linked list and circular linked list, Applications of
linked lists.

Industry Applications: Real-world applications and group activity.

 Lab Syllabus
MODULE 1
4. Write a C program to simulate the working of a singly linked list
providing the following operations:
a. Display& Insert
b. Delete from the beginning/end
c. Delete a given element
 Syllabus
MODULE 2
Stacks, Queues, and Recursion:
Stacks: Definition and operations: Push, pop and display. Applications:
Infix to postfix and expression evaluation.
Recursion: Definition and principles of recursion, Recursive algorithms:
Factorial, Fibonacci series, Tower of Hanoi, Analysis of recursive algorithms.
Queues: Definition and operations: Enqueue, dequeue, front, rear,
Introduction to types of queues: Circular queue, priority queue, double-
ended queue (deque), Applications of queues.
Industry Applications: Real-world applications and group activity.
Lab Syllabus
MODULE 2
[Link] a Program in C for converting an Infix Expression to
Postfix Expression.

2. Design, develop, and execute a program in C to evaluate a valid

postfix expression using stack. Assume that the postfix expression is
read as a single line consisting of non-negative single digit operands
and binary arithmetic operators. The arithmetic operators are +
(add), - (subtract), * (multiply) and / (divide).

3. Design, develop, and execute a program in C to simulate the working

of a queue of integers using an array.
Provide the following operations: a. Insert b. Delete c. Display
 Syllabu
s MODULE 3
Trees and Graphs:

Trees: Definition and terminology: Root, leaf, internal node, height,

depth, Binary trees: Traversal (preorder, inorder, postorder), creation,
insertion, Binary search trees (BST), AVL trees – Creation and
Rotations.

Graphs: Definition and terminology: Vertices, edges, adjacency list,

adjacency matrix, Graph traversal
algorithms: Depth-first search (DFS), breadth-first search (BFS),
 Syllabu
s MODULE 4
Sorting and Searching Algorithms:
Sorting Algorithms: Basic concepts and classification,
Comparison-based sorting: Bubble sort, selection sort,
insertion sort, non-comparison-based sorting: Radix sort,
Address calculation sort.
Searching Algorithms: Linear search and binary search.
Hashing: Hash functions, collision resolution
techniques (chaining, open addressing).
Industry Applications: Real-world applications and
group activity.
Lab Syllabus
MODULE 4

5. Write a C program to Implement the following searching techniques

a. Linear Search b. Binary Search.

6. Write a C program to implement the following sorting algorithms

using user defined functions:
a. Bubble sort (Ascending order)
b. Selection sort (Descending order).
 Syllabu
s Module-5:
Advanced Data Structures, Applications and Algorithm Design Techniques
Tries: Definition, operations, applications in dictionary and spell-checking,
Industry Applications: Real-world applications of data structures and
algorithms.
Algorithm Design Techniques:
Divide and conquer - quicksort, merge sort
Transform and conquer – heapsort
Greedy algorithms - Dijkstra’s algorithm.
Dynamic programming - Floyd-Warshall algorithm
Industry Applications: Real-world applications and group activity.
Lab Syllabus
MODULE 5

7. Find Minimum Cost Spanning Tree of a given undirected graph using

Kruskal's algorithm ( C programming)

8. From a given vertex in a weighted connected graph, find shortest

paths to other vertices Using Dijkstra’s algorithm (C
programming)
 Syllabu
s
Suggested Learning Resources:
Text Books:
[Link] Horowitz and Sartaj Sahni, Fundamentals of Data
Structures in C, 2nd Ed, Universities Press, 2014.

[Link] Lipschutz, Data Structures Schaum's Outlines,

Revised 1st Ed, McGraw Hill, 2014.

[Link] to the Design and Analysis of Algorithms, Anany

Levitin: 2nd Edition, 2009. Pearson.
 Syllabus
Reference books:

[Link] & Forouzan, Data Structures: A Pseudo-code approach with C, 2nd

Ed, Cengage Learning,2014.

[Link] Thareja, Data Structures using C, 3rd Ed, Oxford press, 2012.

[Link]-Paul Tremblay & Paul G. Sorenson, An Introduction to Data

Structures with Applications, 2nd Ed, McGraw Hill, 2013
 Course
CO Outcomes(COs)
Statement Bloom’ POs
No. s Levels
1 Demonstrate and understanding the concepts of fundamental L2 PO1,PO2

data structures and algorithms.

2 Implement and Manipulate the concepts Data Structures such L4 PO1,PO2,PO3

as arrays, linked lists, stacks, queues, trees, and graphs.

3 L3 PO1,PO2,PO3
Apply the algorithms for Searching, Sorting and Optimization
problems.
4 L4 PO1,PO2,PO3
Analyze the efficiency and correctness of algorithms and Apply
Data Structures and algorithms to solve complex problems in
various domains.
5 L6 PO1,PO2,PO3
Create a real-time application using the concepts of Data
Structure and Algorithms.
CO-PO Mapping
P PO PO PO PO PO PO PO1 PO1 PO1
PO PO PO O 5 6 6 7 8 9 0 1 2
1 2 3 4

CO1 3 3
CO2 3 3 3
CO3 3 3 3

CO4 3 3 3

CO5 3 3 3
 STACKS

Def:
A stack is a special type of data structure, where
elements are inserted from one end and elements
are deleted from the same end.

The position from where elements are inserted

and from where elements are deleted is called top
of the stack.

Stack is also called as Last In First Out(LIFO)

data structures.
Stack operations:

1. Push( Inserting an element on top of the stack)

2. Pop(Deleting an element from top of the stack)

3. Display(Display contents of stack).

Push Operation:

Inserting an element into the stack is called push

operation.

Only one item is inserted at a time & item has to

be inserted only from top of the stack.

Empty Stack Stack With elements

4 4
3 3 12 top
2 2
05
1 1 15
0 0
24
top = -1
 Inserting an element to stack : (push operation
)

4 4 4
4 30

3 320 203
3 10 10 10
2 2 2
top 2
1 2 top 1
1 50
40 0 top 0 40 0
0 30 30
top=-1 20 20
10 10
4 top 4
top 3 3
// C function for Push Operation.

void push() //function ---1

{
/* check for overflow of stack */
if (top == stack_size-1)
{
printf(“ stack overflow);
return;
}
top = top+1;
S[top] = item;
}
Pop operation:

Deleting an element from the stack is called “ Pop

operation”.

Only one item is deleted from the stack and the item
has to be deleted only from top of the stack.
Deleting an element to stack : (pop operation )

top 50 4 4 4
440 40

30
3 top
30 3 30 3
3
20 20 20 20
2 2 top 2
10 10 10
210
1 2 1 top
1
0 0 0
0

10 4 4
3 3
2 2
// C function to delete an item from stack.

int pop() //function----2

{
int item_deleted;
if (top == -1)
{
printf(“ Stack Underflow “);
return 0;
}
item_deleted = S[top--];
return item_deleted;
}
 Display stack items:
The contents of the stack are displayed from the
bottom to top.
// C function to display the contents of stack/

Void display() //function----3

{
int i;
if ( top == -1 )
{ Printf(“ stack is empty”); }
for( i=0; i<=top; i++ )
{
printf(“%d”, S[i]);
}
}
// C program to implement stack using arrays;

#include <stdio.h>
#include < process.h>
#define STACK_SIZE 5;

int top;
int s[10];
int item;

//function ---1
//function----2
//function----3
Void main()
{
int item;
int item_deleted;
int choice;

top = -1;
for( ; ; )
{
printf(“1. push, 2. pop, 3. Display, 4. Exit”);
printf(“enter the choice”);
Scanf(“%d”,&choice);
 Switch(choice)
{
Case 1:
printf(“ Enter the item to be inserted”);
Scanf( “%d”, &item);
push();
break;
Case 2:
item_deleted = pop();
if (item_deleted == 0)
printf(“stack is empty”);
else
printf(“Item deleted= %d”,
item_deleted);
break;
 Case 3:
display();
break;
default:
exit(0);
}
}
}
Applications of stack:

The various applications in which stacks are

used are :

[Link] of expressions
2. Evaluation of expressions
[Link]
Conversion of expressions

The sequence of operators and operands that

reduces to a single value after evaluation is called an
expression.

There are three different types of expressions:

Prefix Expression:
Postfix expression:
Infix expression:
 Infix expression:
In an expression, if an operator is in the b/w
two
operands, the expression is called an infix expression.
Ex: a+b, (a-b), (a+b*c-(d*f))
Postfix expression:
In an expression, if an operator follows the
two operands ( operator comes after the two
operands ) , the expression is called “postfix
expression”. It is also called as “Suffix
expression”.
Ex: ab+, ab-, (a+b*c) ab*c+
Prefix Expression:
In an expression, if an operator precede the
two
operands(i.e., operator comes before the two
operands), the
expression is called “Prefix Expression”.
Precedence and Associativity of the operator :

•While evaluating the expressions, some expressions

are given precedence over other expression and are
evaluated first and some are evaluated later.

“ The rules that determines the order in which

the different operators are evaluated are called
precedence rules Or precedence operators”.

Ex : 6 * (2 + 3) – 5 6 * (2 + 3) – 5
6*5–5 6*5–5
30 – 5 6*0
25 0
 The below table shows arithmetic operators along
with priority values,

Description Operator Priority

Exponentiation $ 6
Multiplication * 4
Division / 4
Mod % 4
Addition + 2
Substraction - 2
Associativity of the operator :

“ The order in which the operators with same

precedence are evaluated in an expression is called
associativity of the operator”.

In such cases the precedence rules are considered

with associativity.

The associativity can be classified into two types,

left to right associative ( left associative)

right to left associative (right associative).
left to right associative ( left associative) :

In an expression, if there are two or more

operators having the same priority and are evaluated
from left to right , then the operators are called left
associative operators.

Right to left associative (right associative) :

In an expression, if there are two or more

operators having the same priority and are evaluated
from right to left , then the operators are called right
associative operators.
 The below table shows arithmetic operators along
with priority values and there associativity.

Description Operator Priority Associativi

ty
Exponentiati $ 6 Right to left
on
Multiplication * 4 Left to right
Division / 4 Left to right
Mod % 4 Left to right
Addition + 2 Left to right
Subtraction - 2 Left to right
Conversion from Infix to Postfix expression :
Manual method:
Ex: 1) (( A+(B-C)*D)^E+F)
Sol: (( A+(B-C)*D)^E+F) T1 = B-C  BC-
T1
(( A+T1*D)^E+F) T2 = T1*D T1D*
T2
(( A+T2)^E+F) T3 =
A+T2 AT2+
T3
T3^E+F T4 = T3^E T3E^
T4
T4+F
T4F+
 Now substitute the values of T4,T3,T2,T1 we get
postfix expression,
 T4F+ T4 = T3E^

 T3E^F + T3 = AT2+

 AT2 + E^F + T2 = T1D*

 A T1 D * +E^F + T1 = BC-

 ABC-D*+E^F+

(( A+(B-C)*D)^E+F) = ABC-D*+E^F+
2. X ^ Y ^ Z-M +N+P/Q
 By substituting the values of T5,T4,T3,T2,T1 we
get postfix expression,
 T5T3+ T5 = T4N+ and T3 = PQ/

T4N +PQ/+ T4 = T2M-

T2M-N+PQ/+ T2 = XT1^

XT1^M-N+PQ/+ T1 = YZ^

 XYZ^^M-N+PQ/+

X ^ Y ^ Z-M +N+P/Q = XYZ^^M-N+PQ/+

•To write a program by using stack data
structure,
Let us use two precedence function F and G.
The function F contains the precedence values of
symbols on top of the stack and function G contains
the precedence values of symbols in the input string.
Shown in below table, ( infix to postfix )
Symbol Stack Input Associativi
s precedence precedence ty
“F” “G”
+,- 2 1 Left
*,/ 4 3 Left
$ or ^ 5 6 Right
Operand 8 7 Left
s
( 0 9 Left
) - 0 -
General procedure to convert from infix to postfix form
:
Step 1 :
initialize top and stack of top
top = -1
s[++top] = ‘#’
j=0
Step 2 :
As long as the precedence value of the symbol on
top of the stack is greater than the precedence value
of the current input symbol, pop an item from the
stack and place it in the postfix expression.
while ( F(s[top]) > G(symbol) )
{
postfix[ j++ ] = s[ top-- ]
}
Step 3 :
Once the condition in while loop is failed, if the
precedence of the symbol on top of the stack is not
equal to the precedence value of the current input
symbol, push the current symbol on to the stack.
Otherwise , delete an item from the stack but do not
place in the postfix expression.
if ( F(s[top]) != G(symbol) )
s[++top] = symbol
else
top--;
Step 4 :
After the complete execution of step 2 and step 3,
pop remaining symbols from stack to postfix
expression.
while ( s[top] != ‘#’ )
postfix[j++] = s[top--]
* complete trace of the algorithm :
(A+(B–C)*D)
Stack S[top Symbol F(s[top]) > Postfix
] G(symbol)
# #
# # ( ( -1 > 9 ) (-1!=9) push
(
#( ( A ( 0 > 7 ) push A
#(A A + ( 8 > 1 ) pop A A
#( ( ( 0 > 1 ) push +
#(+ + ( ( 2 > 9 ) push ( A
#(+( ( B ( 0 > 7 ) push B A
#(+(B B - ( 8 > 1 ) pop B AB
#(+( ( ( 0 > 1 ) push -
#(+(- - C ( 2 > 7 ) push C AB
#(+(-C C ) ( 8 > 0 ) pop C ABC
#(+(- - ( 2 > 0 ) pop – ABC-
#(+( ( ( 0 = 0 ) pop (
Don’t place in postfix
* complete trace of the algorithm :
(A+(B–C)*D)
Stack S[top] Symbol F(s[top]) > G(symbol) Postfix

#(+ + * ( 2 > 3 ) push * ABC-

#(+* * D (4 > 7) push D ABC-

#(+*D D ) ( 8 > 0 ) pop D ABC-D

#(+* * ( 4 > 0 ) pop * ABC-D*
#(+ + ( 2 > 0 ) pop + ABC-D*+
#( ( ( 0 = 0 ) pop (
Don’t place in postfix expr

# # ABC-D*+
/* C function for stack precedence
int F (char symbol) //function 1
{
Switch (symbol)
{
Case ‘+’ :
Case ‘-‘ : return 2;
Case ‘*’ :
Case ‘/’ : return 4;
Case ‘^’ :
Case ‘$’ : return 5;
Case ‘(‘ : return 0;
Case ‘#’: return -1;
default : return 8;
}
}
/* C function for input precedence
int G (char symbol) //function 2
{
Switch (symbol)
{
Case ‘+’ :
Case ‘-’ : return 1;
Case ‘*’ :
Case ‘/’ : return 3;
Case ‘^’ :
Case ‘$’ : return 6;
Case ‘(’ : return 9;
Case ‘)’ : return 0;
default : return 7;
}
}
/* C function to convert from infix into postfix
expression.

void infix_postfix(char infix[], char postfix[])

{ //function 3
int top; int j; int I;
char s[30]; char symbol;

top=-1; Step : 1
S[++top]= ‘#’;
j=0;

for(i=0; i<strlen(infix); i++)

{
Symbol=infix[i];
 /* if stack precedence greater , remove symbol
from stack and place into postfix. */

while ( F(s[top]) > G(symbol) ) step : 2

{
postfix[j] = s[top--];
j++;
}

if ( F(s[top]) != G(symbol) ) step : 3

S[++top] = symbol;
else
top--;
}
 /* pop remaining symbols and place them in
postfix expression

while ( s[top] != ’#’ ) step : 4

{
postfix[j++] = s[top--];
}

postfix[j]=’\0’;
}
// C program to convert an infix expression to postfix
expression
# include < stdio.h>
# include < string.h >
/* include function 1, function 2, function 3. */
void main ()
{
char infix[20];
char postfix[20];
printf (“ Enter the valid infix expression”);
scanf (“ %s ”, infix );
infix_postfix ( infix, postfix);
printf (“ The postfix expression is “ );
printf (“%s”,postfix);
}
// Algorithm to convert an INFIX expression to POSTFIX
expression.

Step 1: Scan the Input symbol from left to right.

Step 2: If the scanned symbol is “ ( “ , push the symbol to
stack.
Step 3: If the scanned symbol is “ ) “ , pop the stack
elements
and add to postfix expression until “ ( “ encounters.

Remove “ ( “ from stack, don’t add to

postfix.
Step 4: If the scanned symbol is OPERATOR,
a) pop the elements from the stack and add to
postfix
until precedence of stack of top is greater than
precedence of scanned symbol.
ie., while(precedence(stack[top]) >=
precedence(symbol))
•To write a program by using stack data structure,
Let us use two precedence function F and G.
The function F contains the precedence values of
symbols on top of the stack and function G contains
the precedence values of symbols in the input string.
Shown in below table, ( infix to prefix )

Symbol Stack Input Associativi

s precedence precedence ty
“F” “G”
+,- 1 2 Left
*,/ 3 4 Left
$ or ^ 6 5 Right
Operand 8 7 Left
s
( - 0 Left
) 0 9 -
General procedure to convert from infix to postfix form
:
Step 1 :
initialize top and stack of top
top = -1
s[++top] = ‘#’
j = 0. ( reverse the infix expression )
Step 2 :
As long as the precedence value of the symbol on
top of the stack is greater than the precedence value
of the current input symbol, pop an item from the
stack and place it in the postfix expression.
while ( F(s[top]) > G(symbol) )
{
postfix[ j++ ] = s[ top-- ]
}
Step 3 :
Once the condition in while loop is failed, if the
precedence of the symbol on top of the stack is not
equal to the precedence value of the current input
symbol, push the current symbol on to the stack.
Otherwise , delete an item from the stack but do not
place in the postfix expression.
if ( F(s[top]) != G(symbol) )
s[++top] = symbol
else
top--;
Step 4 :
After the execution of step 2 and step 3, pop
remaining symbols from stack to postfix expression.
while ( s[top] != ‘#’ )
postfix[j++] = s[top--]
* complete trace of the algorithm :
( A + ( B – C )) = ))C–B(+A(
Stack S[top Symbol F(s[top]) > Postfix
] G(symbol)
# # ) -1 > 9 push ‘)’
#) ) ) 0 > 9 push ‘)’
#)) ) C 0 > 7 push ‘C’
#))C C - 8 > 2 pop ‘C’ C
#)) ) 0 > 2 push ‘-’
#))- - B 1 > 7 push ‘B’ C
#))-B B ( 8 > 0 pop ‘B’ CB
#))- - 1 > 0 pop ‘-’ CB-
#)) ) 0 > 0 pop ‘)’
#) ) + 0 > 2 push ‘+’ CB-
#)+ + A 1 > 7 push ‘+’ CB-
#)+A A ( 8 > 0 pop ‘A’ CB-A
#)+ + 1 > 0 pop ‘+’ CB-A+
#) ) 0 > 0 pop ‘)’
i.e., CB-A+ = +A-BC
/* C function for stack precedence
int F (char symbol) function 1
{
Switch (symbol)
{
Case ‘+’ :
Case ‘-‘ : return 1;
Case ‘*’ :
Case ‘/’ : return 3;
Case ‘^’ :
Case ‘$’ : return 6;
Case ‘)‘ : return 0;
Case ‘#’: return -1;
default : return 8;
}
}
/* C function for input precedence
int G (char symbol) function 2
{
Switch (symbol)
{
Case ‘+’ :
Case ‘-’ : return 2;
Case ‘*’ :
Case ‘/’ : return 4;
Case ‘^’ :
Case ‘$’ : return 5;
Case ‘(’ : return 0;
Case ‘)’ : return 9;
default : return 7;
}
}
/* C function to convert from infix into prefix
expression.

void infix_prefix(char infix[], char prefix[])

{ function 3
int top; int j; int I;
char s[30]; char symbol;

top=-1; Step : 1
S[++top]= ‘#’;
j=0;
strrev ( infix );
for(i=0; I < strlen (infix); i++)
{
Symbol=infix[i];
 /* if stack precedence greater , remove symbol
from stack and place into postfix. */

while ( F(s[top]) > G(symbol) ) step : 2

{
prefix[j] = s[top--];
j++;
}

if ( F(s[top]) != G(symbol) ) step : 3

S[++top] = symbol;
else
top--;
}
 /* pop remaining symbols and place them in
postfix expression

while ( s[top] != ’#’ ) step : 4

{
prefix[j++] = s[top--];
}

prefix[j]=’\0’;

strrev (prefix );
}
// C program to convert an infix expression to prefix
expression
# include < stdio.h>
# include < string.h >
/* include function 1, function 2, function 3. */
void main ()
{
char infix[20];
char prefix[20];
printf (“ Enter the valid infix expression”);
scanf (“ %s ”, infix );
infix_prefix ( infix, prefix);
printf (“ The postfix expression is “ );
printf (“%s”, prefix);
}
Evaluation of postfix expression :
Algorithm:
Step 1 : Scan the symbol from left to right.

Step 2: If the scanned symbol is an operand,

push it on to the stack.

Step 3: If the scanned symbol is an operator, pop

two elements from the stack

The first popped element is operand 2 and the

second popped element is operand1
Op2 = s[top--];
Op1 = s[top--];
 Step 4: perform the indicated operation.
res = op1 op op2.

Step 5: push the result on to the stack.

Step 6: Repeat the above procedure till the end

of the i/p is encountered.
Ex: Evaluate the following postfix expression.

ABC-D*+E$F+ infix((A+(B-C)*D)$E+F)

with the values,

A=6, B=3, C=2, D=5, E=1, F=7.

Solution:
After substituting the values

632-5*+1$7+
Ex: Evaluate the following postfix expression.

Postfix symbol op2 op1 res = op1 Stack

Expression scanned op op2 conten
ts
632-5*+1$7+ 6 6
32-5*+1$7+ 3 63
2-5*+1$7+ 2 632
-5*+1$7+ - 2 3 3–2= 61
1
5*+1$7+ 5 615
*+1$7+ * 5 1 1*5= 65
5
+1$7+ + 5 6 6+5= 11
11
1$7+ 1 11 1
// c program to evaluate the postfix expression:
#include < stdio.h >
#include < math.h >
#include < string.h >
double compute(char symbol, double op1, double
op2)
{
switch ( symbol)
{
Case ‘+’ : return op1+op2;
Case ‘-’ : return op1-op2;
Case ‘*’ : return op1*op2;
Case ‘/’ : return op1/op2;
Case ‘$’:
Case ‘^’: return pow(op1,op2);
} }
void main()
{
double s[20] , res , op1 , op2 ;
int top, i ;
char postfix[20] , symbol ;
top = -1;
Printf(“ enter the postfix expression”);
Scanf(“%s”, postfix);

for ( i=0; i<strlen(postfix); i++ )

{

Symbol = postfix[i];
 if ( isdigit(symbol))
s[top]=(symbol) // Wont work
s[top++]= (symbol-48);
else
{
op2 = s[top--];
op1 = s[top--];
res = compute(symbol, op1,op2);
S[++top] = res;
}
}
res = s[top--];
printf(“ the result is %f\n”, res);
}
Ex; to check whether a give string is palindrome or not
using stack.
# include <stdio.h>
# include <string.h>

int is_palindrome( char str[])

{
int i, top = -1;
char s[30], stk_item;
/* push all the characters of the given string
for( i=0; i<strlen(str); i++ )
{
S[++top]= str[i];
}
/* check whether the string is palindrome or not.

for (i=0; i<strlen(str);i++)

{
Stk_item = s[top--];
if (str[i] != stk_item)
return 0;
}
return 1;
}
void main()
{
Char str[20];
printf(“enter string”);
Scanf(“%s”, str);
if (is_palindrome(str))
printf(“ the string is palindrome”);
else
printf(“ the string is not a palindrome”);
}
Recursion
 Mathematical Analysis of Recursive
algorithms:
• A recursive function is a function that is defined in
terms of itself.

• An algorithm is said to be recursive if the same

algorithm is invoked in the body.

• An algorithm that calls itself is direct recursive.

• Algorithm A is said to be indirect recursive if it calls

another algorithm which in turn calls A.

• In recursive the calling function and called function are

same.
 Iterative version to compute factorial of n:

Iterative version to compute factorial of n:

The factorial of a number n is the product of

integer
values from 1 to n. The iterative definition to compute
n! is
shown below,

Fact(n) = 1 if n =
0
n * (n-1) * (n-2)*……*3*2*1. if
n>0.

Based on the above definition the algorithm can be

designed as follows,
 Iterative version to compute factorial of n:

Initial: fact = 1
Step1 : fact = fact *1
Step2:fact = fact *2
Step3 : fact = fact *3
.
.
.
Step n : fact = fact *n

From above steps we can write,

fact = fact * i where, i = 1,2,…….n.

Iterative version to compute factorial of n:

Algorithm factorial (int n)

{
int fact, i;
fact:= 1;
for (i=1; i<=n; i++)
{
fact = fact * i;
}
return fact;
}
Recursive version to compute factorial of n:

Algorithm fact(int n)
{
if (n==0)
return 1;
return n * fact (n-1);
}
 Recursive version to compute factorial of n:
The recursive definition to compute n! is show below,

fact (n) = 1 if n=0

n*fact(n-1) if n>0
5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1
1! = 1 * 0! = 1
2! = 2*1!=2
3! = 3 * 2!=6
4!= 4* 3!= 24
5!= 5* 4!= 120
 Recursive version to compute factorial of n:
#1nc1ude‹std1o. h›
#1nc1ude‹con1o.h›
long int fact (int n)
{
if( n == 0 )
return 1;
return (n * fact(n -1));
}
void main( )
{
int n;
long int result; clrscr();
printf (“Enter a n! Number:“);
scanf ( “%d“, &n);
result = fact(n);
printf (“%d! = %1d“, n, result);
getch();
}
 Properties of recursive definition :
The recursive function must satisfy following properties,

The function must have stopping condition. i.e., it

should not continue to call indefinitely.

Each time the function calls itself, it must be in the

recursive form, i.e., it must be nearer to a solution.

Ex: result = fact(n);

long int fact (int n)

{
if( n == 0 )
return 1;
return (n * fact(n -1));
}
 Advantage of recursion :

Recursion reduces the complexity of the problem.

Recursion allows users to write much simpler programs.

Program implemented by recursion will be smaller in length.

Recursion programs can have any no of nesting levels.

Recursion is a top-down programming tool, where the given

problem is divided into smaller modules, each module are then
individually attached.
 How it works :

The recursive function calls are initially pushed on to the

stack until the condition is encountered.

After the termination condition is encountered, the

recursive functions that were pushed onto the stack are
popped from the stack one-by-one.

So, stack data structure plays the major role in

executing recursive functions.
To compute greatest common divisor (GCD) of 2
integers

To compute greatest common divisor (GCD) of

2 integers

GCD of 2 non-negative, not both zero integers

m & n, denoted as gcd(m,n), is defined as the
largest integer that divides both m & n evenly i.e.
with a remainder of 0.

gcd (m,n) = gcd (n, m mod n)

where (m mod n) is the remainder of the division of

m by n.
Euclid’s Algorithm for computing gcd(m,n)

Step 1 : If n=0, return the value of m as the answer &

stop; otherwise go to Step 2.

Step 2 : Divide m by n and assign the value of

remainder to r.

Step 3 : Assign the value of n to m and the value of r

to n.
Go to Step 1.
ALGORITHM Euclid(m,n)

ALGORITHM Euclid(m,n)
// Computes gcd(m,n) by Euclid’s algorithm
// Input: 2 non-negative, not both zero integers m &
n
// Output: GCD of m & n

while n # 0 do
r = m mod n
m=n
n=r
return m
C Program for GCD of two numbers

#include‹std1o.h›
int getGCD (int, int) ;
void main( )
{
int m,n, gcd;
pr1ntf( "\nEnter two numbers: ") ;
scant( “%d %d", &m, &n) ;
gcd = getGCD (n, m%n) ;
printf(“\nGCD of %d and %d is: %d“, m, n, gcd);
}
int getGCD(int a, int b)
{
if ( b == 0)
return a;
else
return getGCD( b, a % b );
}
 Fibonacci series :

The Fibonacci numbers are a series of

numbers such that each number is the sum of the
previous two numbers except the first and the
second number.

Ex : 0,1,1,2,3,5,8,13,21,34,………………..

To write a recursive definition we should know

the base case and general case.

Base case : Fib (0) = 0 and Fib (1) = 1

General case : Fib (n) = Fib (n-1) + Fib (n-2)

C program to display n Fibonacci numbers :

int fib( int n )

{
if ( n==0 ) return 0;
if ( n==1 ) return 1;
return (fib( n-1 ) + fib ( n-2 ));
}
C program to display n Fibonacci numbers :

void main()
{
int i, n;
printf(“Enter the value of n”);
scanf(“%d”, &n);
printf (“Fibonacci numbers are”);
for ( i=0; i<n,i++ )
{
printf (“fib %d = %d”,i,fib(i));
}
}
 Tower of Hanoi :

Here there are 3 needles A, B, & C & ‘n’ discs, of

different diameters in the needle A, & are placed one
above the other such that always a smaller disc is
placed above the larger disc. The two needles B & C
are empty.
All the discs from needle A are to be
transferred to needle C using needle B as temporary
storage.

The following rules to be followed while transferring the

discs,

Only one disc is moved at a time from one needle to

another needle.
Smaller disc is on top of the larger disc at any time.
Only one needle can be used to for storing intermediate
 Tower of Hanoi :
Solution:
If n = 2, there will be 2n – 1 moves,
here it is 3.

A -> B , A –> C, B ->C.

i.e., A -> B tower(n-1, source, dest, temp);

A -> C printf(“Move the disc from %c to %c”,

source, dest);
B -> C tower(n-1, temp, source, dest);

i.e., The base condition is, if n == 1 in source then

 // C function for tower of Hanoi

#include < stdio.h >

int count = 0;
void tower(int n, int source, int temp, int dest)
{
if( n == 1)
{
printf(“\n move the disc from %c to %c
“, source, dest);
count++;
return;
}
tower (n-1, source, dest, temp);
printf(“\n Move the disk from %c to %c “,
source, dest);
 // C function for tower of Hanoi

void main()
{
int n;
printf(“Enter no. of discs”);
scanf(“%d”, &n);
tower(n, ‘A’, ‘B’, ‘C’);
printf(“The total no. of moves = %d”,
count);
}
The general set of procedures to analyze
recursive algorithms :

What is the input size? Get that parameter.

Find out the basic operation(s).

What is the number of times the basic operation is

executed? Set up the recurrence relation with the escape
hatch.

Using the formulas or backward substitution, solve

the recurrence relation to find its order of growth or the
complexity.
QUEUES
 QUEUES
“ A queue is defined as a special type of data
structure where elements are inserted from one end
and elements are deleted from the other end”.

The end from where the elements are inserted

is called “rear end”.

The end from where the elements are deleted is

called “front end”.

“queue is also called as First In First Out (FIFO)

data structure.”
Example :
empty queue
f=0,r=-1
0 1 2 3 4

queue with elements

0 1 2 3
4
10 20 30

f r
Different types of queues:-

Queue (ordinary queue)

Circular queue

Double ended queue

Priority queue
Queues(ordinary queues):
Insert at the rear end:
Before insert :
0 1 2 3 4
10 20 30 40
f r
After insert :
0 1 2 3 4
10 20 30 40 50
f r
r=r+1
q[r] = item.
// c function to insert an item

Void insert_rear ()
{
if ( r == QUEUE_SIZE – 1 )
{
printf(“queue overflow”);
return;
}
r = r+1;
q[r] = item;
}
Queues(ordinary queues):
Delete at the front end:
Before delete :
0 1 2 3 4
10 20 30 40
f r
After delete :
0 1 2 3 4
20 30 40 50
f r
cout<<“ the element deleted is “ << q[f++];
// c function to delete an item
Void delete_front ()
{
if ( f > r)
{
printf(“queue underflow”);
return;
}
printf(“the element deleted is%d”,q[f++]);
if ( f > r )
{
f = 0; r = -1 ;
}
}
Display queue contents:
0 1 2 3 4
20 30 40 50
f r

The contents of the queue is always displayed

from front to rear.

for ( i=f; i<=r; i++ )

printf(“%d”,q[i]);
// c++ function to display the contents of queue

void display ()
{
int i;
if(f>r)
{
printf(“queue is empty”);
return;
}

for (i=f; i<=r; i++)

{
printf(“%d”,q[i]);
}
}
Double ended queue ( dequeue ) :

A dequeue is a special type of data structure in

which insertions are done from both ends and
deletions are done at both ends.

Operations performed on Queues :

* Insert on item from front end.
* Insert an item from rear end.
* Delete an item from rear end.
* Delete an item from front end.
* Display the contents of queue.
Insert at the front end:
Case1 :
Queue Empty : Here, an item can be inserted at the
front end first by incrementing r by 1 and then insert an
item.
Before insert
0 1 2 3 4

r=-1 f=0
After insert
0 1 2 3 4
10

f,r if ( f == 0 && r == -1 )
{ q[++r] = item; return ; }
Case 2: Some items are deleted :
Assume,
0 1 2 3 4
10 20 30

f r
After deleting two elements
0 1 2 3 4
30

fr
Now, insert at front end,
0 1 20 2 30 3 4

f r
if ( f != 0 )
{ q[--f] = item; return; }
Case 3 : Some items are inserted (not deleted) :

0 1 2 3 4
10 20 30

f r

Now, it is not possible to insert an item

cout<< “front insertion is not possible”;

// function to insert an item at the front end.

void insert_front ()
{
if ( f==0 && r==-1 ) // case 1
{
Q[++r] = item;
return;
}
if ( f != 0 ) // case 2
{
q[--f] = item; return;
}
printf(“ front insertion is not possible”); //case 3.
}
Delete from the rear end :
Before deleting
0 1 2 3 4
10 20 30
f r
After delete
0 1 2 3 4
10 20
f r

Here if we keep on deleting, we will arise condition

that
f>r,
Then the stack is “underflow”.
//C function to delete an item from the rear end.

void delete_rear()
{
if (f > r)
{
printf(“Queue Underflow”);
return;
}
printf(“The element deleted is %d“, q[r--]);
if ( f > r)
{
f = 0;
r = -1;
}
}
Disadvantages of queue:

0 1 2 3 4
30 40 50
f r

The above situation will arise when 5 elements are

inserted & then deleting first two items.

Now, if we try to insert an item we get the

message “Queue overflow”.

i.e., even if memory is available, we can not

access these memory locations.
Circular Queues:
In circular queue, the elements of a given
queue can be stored efficiently in an array , so that
end of the queue is followed by the front of the
queue.
The pictorial representation of a circular
queue & its equivalent representation using an array
is shown below.
100 1 2 3 4

f,r
After inserting 20 and 30
0 1 2 3 4

10
f 20 30
r
After inserting 40 and 50
0 1 2 3
4
10 20 30 40 50
f r
After deleting 10 and 20
0 1 2 3
4 30 40 50

f r
After inserting 60
0 1 2 3
60 30 40 50
4

r f
Operations on circular queue:

*Insert rear

*Delete front

*Display
*To insert from the rear end :
Step1 : Check for Overflow;
if (count == Queue_size)
{
cout<<“Queue is full”;
return;
}
Step2 : Insert Item :
This is achieved by incrementing r by 1 & then
inserting as shown below,
r = (r+1) % QUEUE _SIZE;
Q[r] = item;
Step 3: Update count :
Count++;
//function to insert an item at the rear end.

void insert_rear(int item, int q[],int r ,int count)

{
if (count == QUEUE_SIZE)
{
cout<<“Overflow of queue \n”;
return;
}
r = (r+1) % QUEUE_SIZE;
Q[r] = item;
count += 1;
}
*TO delete from the front end :
Step1 : Check for underflow :
if (count == 0)
{
cout<<“queue is empty /n”;
return;
}

Step2 : Delete item:

cout<<“The deleted elements is ”<<q[f];
f = (f+1) % QUEUE_SIZE;

Step 3: Update count:

count--;
//function to delete an item from the front end of c queue.

void delete_front(int q[] , int f , int count)

{
if (count == 0)
{
cout<<“underflow of queue /n”;
return ;
}
cout<<“the deleted elements is /n”<<q[f];
f = (f+1) % QUEUE_SIZE;
count -= 1;
}
*To display queue contents :

step1 : check for underflow:

if (count == 0)
{
cout<<“Queue is empty /n”;
}
Step 2 : Display
for ( i=1; i<=count; i++)
{
cout<<q[f];
f = (f+1) % QUEUE_SIZE;
}
//Function to display the contents of circular queue
void display (int q[], intf, int count )
{
int i;
if (count == 0)
{
cout<<“Q is empty /n”; return;
}
cout<<“contents of queue is /n”;
for (i = 1; i <= count; i++)
{
cout<<q[f];
f = (f+1) % QUEUE_SIZE;
}
}
Priority Queues:

The priority queue is a special type of data structure

in
which items can be inserted or deleted based on the
priority.

Always an element with highest priority is

processed
before processing any of the lower priority elements.

If the elements in the queue are of same priority,

then
the elements, which is inserted first into the queue is
processed.
The priority queues are classified into groups,

Ascending priority queue :

while deleting an element from the queue,

only the smallest element is removed first.

Descending priority queue :

while deleting an element from the queue,

only the largest element is deleted first.
// Insert an item at the correct place in priority queue.
Void insert_item(int item, int q[],int r)
{ int j;
if ( r == QUEUE_SIZE-1 )
{
printf(“queue is full”); return;
}
j = r;
while ( j >= 0 && item < q[j] )
{
Q[j+1] = q[j]; j--;
}
Q[j+1] = item;
r = r+1;
}