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
 TREES
It is a non-linear data structure.

It is a hierarchical data structure. ( OS file

maintenance)

Most general form of a tree can be defined

as an “connected acyclic
graph “.
 Trees are normally divided into two
groups
10 20

General trees :
12 8 20

10

Binary trees : 10 or or 10
10

20 12 20
Binary Trees:
A binary is a tree which is a collection
of zero or more nodes. A tree can be empty or
partitioned into three subgroups namely root ,
left sub tree and right sub tree.

In general, a tree in which each node

has either zero, one or two sub trees is called
a binary tree.
10 10 10

or or
20 12 20

Root:
If tree is not empty, the first node is called
root node.
Left sub tree:
It is a tree which is connected to the
left of root & it is called left sub tree.

Right sub tree:

It is a tree which is connected to the
right of the root & it is called right
sub tree.

In general, a tree in which the out

degree of node has either zero, one or two is
called a binary tree.
Different terminologies normally associated
with trees:

Root node:
A node with in degree O is called root node
it is the first node in the tree. ( A root is a
node without parent )

Child:
The nodes , which are all reachable from a
node X using only one edge are called
children.

Siblings:
Two or more nodes having the same parent
are called siblings.
Parent :
A node having left sub tree or right sub
tree or both is said to be a parent node.

Leaf :
A node in a tree that has an out degree of
Zero is called a leaf nodes. ( Leaves are nodes
without children )

Internal nodes :
The nodes except leaf nodes in a tree are
called internal nodes.
Level:
The distance of a node from the root is
called level of the node.

In a tree, the root has a level 0(zero) and

level of any other node is one more than
the level of its father.

Height : (depth) :
The height of the tree is defined as the
maximum level of any leaf in the tree.
Types of binary trees:
The binary trees are classified as follows,

Strictly binary tree

Complete binary tree

Almost Complete binary tree

An expression tree

Binary search tree

AVL trees.
Strictly binary tree :

If the out degree of every node in a tree

is either
0 or 2 , then the tree is said to be strictly
binary tree.
10
10
Eg : OR
12 20
12 20

12
10 12
10
Complete binary tree:
A strictly binary tree in which the
number of nodes at any level i is 2 pow i, is said
to be a complete binary tree.

Eg :
10

12 20

12
10 12 10
Almost Complete binary tree:
It is a strictly binary tree, except the last
level.

Eg :
10

12 20

12
10 12
Storage representation of a binary tree :

The storage representation of binary

trees can be
classified as shown below,

Sequential allocation technique (static

allocation )

Linked allocation technique( Dynamic

allocation)
Sequential allocation technique:

A tress can also be represented

using an array which is called sequential
representation.

0 10

1
12 20 2

3 4 5 0 1 2 3
12
4 10 5 12 10 12 20 12 10 12
Linked allocation technique:

In a linked allocation technique, a

node in
a tree has three fields,

Info : Which contains actual information

Llink : which contains address of the left sub

tree.

Rlink : which contains address of the right

sub tree.
So, a node can be represented using structure
as shown below,

Struct node
{
int info;
Struct node * llink;
Struct node * rlink;
};

typedef struct node * NODE;

 A pointer variable “root” can be used to
point to
the root node always .

If the tree is empty , the pointer variable

root
points to NULL indicating the tree is empty,

i.e., NODE root = NULL;

Various operations on binary trees:

Insertion

Traversal

Search

Display
Before Insertion :
10

12 20

12
18 12

12 10

Now,
I want to insert a “ temp “ node for the above tree
as right node of 18?
Insertion Processing :
10

12 20

12
18 12

temp
12 10
10

Position of Insertion,
I want to insert a “ temp “ node for the above tree ?
After Insertion :
10

12 20

12
12 12

12 temp
10
10

if you want to insert a “ temp “ node we

have to give the direction as “ RLR “.
 //Algorithm to insert an item into a binary tree based
on direction.

Step 1 : Create a node temp and insert info and null to

left and right fields

Step 2 : If empty tree return temp as first node.

Step3 : Accept the direction to insert and find the

place to insert based on direction string.

Step 4 : If proper place not found, then invalid

direction delete temp node and return
back.

Step 5 : Otherwise insert node and return back.

 //function to insert an item into a binary tree based on
direction.
NODE insert(int item, NODE root)
{
NODE temp, cur , prev;
char direction [10];
int i;
temp = getnode();
temp->info = item;
temp-> llink = temp->rlink = NULL;
if (root == NULL) return temp;
Printf(“give the directions where you want to
insert”);
Scanf(“%s”, direction);
direction = toupper(direction);
Prev = NULL;
Cur = root;
/* find the position to insert */
for (i=0; i < strlen(direction); i++)
{
if (cur == NULL) break;
prev = cur;
if(direction[i] == ’L’)
cur = cur->llink;
else
cur = cur->rlink;
}
 if (cur != NULL || i! = strlen(direction))
{
printf(“insertion not possible”);
free(temp);
return root;
}
If(direction[i-1]== ’L’ )
Prev->llink = temp;
else
Prev->rlink = temp;
Return root;
}
Traversals :
Traversing is a method of visiting each node
of a tree exactly once in a systematic order.
During traversal, we may print the info field
of each node visited.

Different types of tree traversals:

Preorder
Inorder
Post order
Preorder traversal:

Step 1 : Process the root node

Step 2 : Traverse the left sub tree in preorder
Step 3 : Traverse the right sub tree in preorder

This can be done in two ways,

a) Recursive technique.
b) Iterative procedure.
// Recursive function for preorder traversal.

Void preorder(NODE root)

{
if(root == NULL) return;
printf(“%d”, root->info);
Preorder(root->llink);
Preorder(root->rlink);
}
// Iterative function for preorder traversal.

Void preorder ( NODE root )

{
NODE cur, s[20];
int top = -1;
if ( root == NULL )
{
printf ( “ Tree is empty “);
return;
}
cur = root;
for ( ; ; )
{
 while ( cur != NULL )
{
printf ( “ %d “ , cur -> info );
s[++top] = cur;
cur = cur -> llink;
}
if ( top != -1 )
{
cur = s[top--];
cur = cur -> rlink;
}
else
return;
} // end of for loop.
}
Inorder traversal :

Step 1 : Traverse the left sub tree in Inorder

Step 2 : Process the root node
Step 3 : Traverse the right sub tree in Inorder

This can be done in two ways,

a) Recursive technique.
b) Iterative procedure.
// Recursive function for Inorder traversal

Void inorder(NODE root)

{
if(root == NULL) return;
Inorder(root->llink);
Printf(“%d”, root->info);
Inorder(root->rlink);
}
// Iterative function for inorder traversal.

Void inorder ( NODE root )

{
NODE cur, s[20];
int top = -1;
if ( root == NULL )
{
printf ( “ Tree is empty “);
return;
}
cur = root;
for ( ; ; )
{
 while ( cur != NULL )
{
s[++top] = cur;
cur = cur -> llink;
}
if ( top != -1 )
{
cur = s[top--];
printf ( “ %d “ , cur -> info );
cur = cur -> rlink;
}
else
return;
} // end of for loop.
}
Postorder traversal :

Step 1 : Traverse the left sub tree in postorder

Step 2 : Traverse the right sub tree in postorder
Step 3 : Process the root node

This can be done in two ways,

a) Recursive technique.
b) Iterative procedure.
// Recursive function for Inorder traversal

Void postorder(NODE root)

{
if (root == NULL) return;
postorder(root->llink);
postorder(root->rlink);
printf(“%d”, root->info);
}
// Iterative function for post order traversal.
void postorder( NODE root )
{
struct stack
{
NODE address;
int flag; };
NODE cur;
struct stack s[20];
int top = -1;
if ( root == NULL )
{
printf (“ Tree is empty “);
return;
}
cur = root;
for (; ;)
{
while ( cur != NULL )
{
top++;
s[top].address = cur;
s[top].flag = 1;
cur = cur -> llink;
}
while ( s[top].flag < 0 )
{
cur = s[top].address;
top--;
printf (“%d”, cur -> info );
 if ( top == -1 )
return;
}
cur = s[top].address;
cur = cur -> rlink;
s[top].flag = -1;
}
}
Example : A

B C

D
E F

G H
I

Preorder :-> ABDGHCEIF

Postorder :-> GHDBIEFCA
Inorder :-> GDHBAEICF
// Recursive function to print the tree the tree in tree
form.

void display(NODE root, int level)

{
int i;
if (root == NULL) return;
display (root-> rlink; level+1);
for( i=0; i< level; i++)
printf(“ “);
printf(“%d\n”, root->info);
display(root->llink,level+1);
}
//c program to create a tree and traversals
#include<stdio.h>
#include<stdlib.h>
#include<process.h>
#include<string.h>

Struct node
{
int info;
Struct *llink;
Struct *rlink;
};
typedef struct node * NODE;

/* include all the above functions */

Void main()
{
NODE root= NULL;
Int choice, item, flag;
For(;;)
{
printf(“1. Insert [Link] [Link]
[Link] 5. Display [Link]”);
printf(“enter the choice”);
Scanf(“%d”, &choice);
Switch(choice)
{
Case 1:
printf(“enter the item to be inserted”);
Scanf(“%d”, &item);
 Root=insert( item, root);
Break;
Case 2:
if(root == NULL)
printf(“tree is empty”);
else
{
printf(“ the given tree is”);
printf(root, 1);
printf(“preorder traversal is”);
preorder(root);
printf(“\n”);
}
break;
Case 3 :
if(root==NULL)
printf(“tree is empty);
Else
{
printf(“ the given tree is “):
display(root,1);
printf(“inorder traversal is”);
inorder(root);
printf(“\n”);
}
break;
case 4:
If(root==NULL)
Printf(“tree is empty”);
Else
{
printf(“the given tree is”);
display(root,1);
printf(“postorder traversal is”);
postorder(root);
printf(‘\n”);
}
break;
 Case 5 :
if(root == NULL)
printf(“ tree is empty”);
else
display(root,1);
default :
exit(0);
}
}
}
Examples :

1. write a binary tree based on the following

traversals,

preorder : ABDEGHCFIJ
inorder : DBGEHACIFJ
 Binary Search Tree ( BST ) :
A binary search tree is a binary tree in
which for each node in the tree, elements in the left
sub tree are
less than root and elements in the right sub tree are
greater
than root. 100 20

Ex :
11 10 60
70
0

60 10 40
80 70
5
Insertion:

Ex: 100, 50, 200, 90, 80, 25, 300, 150, 180, 140
// Algorithm to insert an item into a binary search tree.

Step 1 : Create a node temp and insert info and null to

left and right fields

Step 2 : If empty tree return temp as first node.

Step3 : Based on info field find out the proper position

to insert temp node.

Step 4 : Insert node and return back.

// function to insert an item into a binary search tree
NODE insert (int item, NODE root)
{
NODE temp, cur, prev;
temp = getnode ();
temp-> info = item;
temp-> llink = NULL;
temp-> rlink = NULL;
if(root == NULL) return temp;
prev = NULL;
Cur = root;
while (cur !=NULL)
{
Prev = cur;
 if(item < cur->info)
cur = cur->llink;
else
cur = cur->rlink;
}
if( item < prev->info)
prev->llink = temp;
else
prev->rlink = temp;
return root;
}
Searching:
// c function to search an element in BST
NODE iterative search(int item, NODE root)
{
root1 = root;
if(root1 == NULL) return root;
while(root1 != NULL)
{
if(item == root1->info)
break;
if(item < root1->info)
root1 = root1->llink;
else
root1 = root1->rlink;
}
if(root1 == NULL)
{
printf(“item not found”);
return root;
}
printf(“key found”);
return root;
}
Disadvantages of Binary trees & BST:
In the above two types the tree can
degenerate into a severely unbalanced one with height
equal to n-1
E.g. : Binary tree Binary search tree
10 100

20
20 30 90
0

40 40

50 70

60 60

This can be overcome by using “AVL” trees.

AVL Trees:
AVL trees were invented in 1962 by two
Russian scientist G.M Adelson Velsky & E.M Landis.

Definition:
An AVL tree is a binary search tree in which the
balance factor of every node, which is defined as the
difference b/w the heights of the node’s left & right sub
trees is,
either 0 or +1 or -1 .
Balance factor = height of left sub tree – height
of right sub tree.
Example :

AVL tree BST ( not AVL tree )

1 2
10 10

0 1 0
5 20 5 20
0

14 7 -1 0 4 17 -
12
1
2 8
0 0 2 0
8
0
 If an insertion of a new node makes an AVL tree
unbalanced , we transform the tree by a rotation

Rotation :
A Rotation in an AVL tree is a local
transformation of its sub tree rooted at a node whose
balance has become either +2 or -2 ,if there are
several such nodes, we rotate the tree rooted at the
unbalanced node that is the closest to the newly
inserted leaf.
Types of rotations :

Totally there are four types of rotations

1. Single right rotation or R-rotation

2. Single left rotation or L-rotation

3. Double right-left rotation or RL-rotation

4. Double left-right rotation or LR-rotation

Points to remember to select different rotation
technique :

[Link] line with positive unbalanced.

apply Right rotation for unbalanced node.
5 +2
4 0

4
+1 2 5 0
0
2
0
[Link] line with negative unbalanced.
apply left rotation for unbalanced node.

-2
5 0
4

-1 0
4
0 2 5

20
[Link] line with positive unbalanced.
apply left-right rotation.

Right rotation for unbalanced node and left

rotation for the nearest node.

+2
5 0
4
-1
4
0
0 2 5

2 0
[Link] line with negative unbalanced.
apply right-left rotation.

Left rotation for unbalanced node and right

rotation for the nearest node.

-2
5 0
7
+1
8
0
0 5 8
7
0
 A graph G consists of two things :
i.e., G = (V,E).
1. A set V of elements called nodes (or points or
vertices)

2. A set E of edges such that each edge e in E is

identified with a unique (unordered) pair [u, v] of
nodes in V, denoted by e = [ u, v ].
E.g. : 2

1 3 V = { 1, 2, 3, 4, 5 }

E = {(1,2),(1,5),(1,3),
5 4 (5,4),(4,3),(2,3)}
 2 2

1 3 1 3

5 4 5 4
Ex :
1

3 2

5 4

The adjacency list representation of the above graph

is,
Adj [1] = { 2, 3, 5 }
Adj [2] = { 1, 3, 4 }
Adj [3] = { 1, 2, 5 }
Adj [4] = { 2, 5 }
Adj [5] = { 1, 3, 4 }
 1 2 3 4 5
1 0 1 1 0 1
2 1 0 1 1 0
3 1 1 0 0 1
4 0 1 0 0 1
5 1 0 1 1 0
 We start from the initial vertex V and mark it as
visited (set to 1).

Next step is to find all unvisited adjacency vertices

of starting vertex and pick any one vertex from this
list (if you have many) and call it as w.

Now, DFS algorithm can be recursively invoked by

sending “w” as the new starting vertex & continue
for all vertices.
e.g. : 1
Connected undirected graph :

2 3

6 7
4 5

8
2 . Strongly connected, Directed graph :

1 2 1 2

3 4 3 4

Input Output
3 . Undirected, Disconnected graph :

5
5 6
1 2
1 2
6
4 3
4 3
7
8 7

Input output 1
8

output 2
 4 . Directed weakly connected graph :

1 2 3
1 2

3
5 4
5 4
Input Output 1 output 2
//C function for dfs

dfs (int v)
{
visited [v] = 1;
for( int w = 2; w <= n; w++ )
{
if(visited [w] == 0 && a[v][w] == 1)
{
printf(“%d”, w);
dfs(w);
}
}
}
//C function for dfs visit _all.
dfs_visit _all()
{
for (int i = 1; i <=n; i++)
{
visited[i] = 0;
}
for (int i = 1; i <= n; i++)
{
if (visited [i] == 0)
{
printf(“%d”, i)
dfs(i);
}
}
}
//Complete C program.
# include<stdio.h>
# define max=10;
// include dfs & dfs_visit_all functions
void main()
{
int a[max] [max];
int n;
printf(“enter the no of vertices”);
Scanf(“%d”, &n);
printf(“enter the adjacency matrix”)
for (int i=1; i<=n; i++)
for (int j=1; j<=n;j++)
Scanf(“%d”, &a[i][j]);
dfs_visit_all(); }
Algorithm bfs (G, V)

//Input:Graph with V vertices & E edges.

//Output: BFS tree.
visited[v] = 1;
inqueue(v);
while queue is not empty() do
v = delqueue();
for all w adjacent to v to
if visited[w] = 0
inqueue(w);
visited[w] = 1;
end bfs.
e.g. : 1
Connected undirected graph :

2 3

6 7
4 5

8
// c function for bfs

bfs(int v)
{
f=0; r=-1;
visited[v] = 1;
insqueue(v);

while( f <= r )
{
v = delqueue();
for ( int w = 1; w <= n; w++)
{
 if(visited[w] == 0 && a[v][w] == 1)
{
insqueue(w);
printf("%d",w);
visited[w] = 1;
}
}
}
}
void insqueue( int e)
{
q[++r] = e;
}
int delqueue()
{
int t = q[f];
f++;
if( f > r)
{
f = 0;
r = -1;
}
return t;
}
//complete c program for bfs
#include <stdio.h>
#define max = 10;
int visited[max];
/* include the bfs, insqueue, delqueue functions.

void main()
{
int s; int i; int j; int n; a[10][10]
printf("Enter the no. of vertices");
scanf("%d", &n);
printf("Enter the adjacency matrix");
for(i = 1; i <= n; i++)
for( j =1; j <= n; j++)
scanf("%d",&a[i][j]);
 for( i = 1; i<= n; i++)
visitied[i] = 0;

printf("Enter the starting vertex");

scanf("%d", &s);
printf("The vertices visited from %d "s" are);

bfs(s);
}