SATHYABAM

A
INSTITUTE OF SCIENCE AND TECHNOLOGY
Deemed to be University
Declared as category ‘A’ University by MHRD, Govt. of India
Jeppiaar Nagar, Rajiv Gandhi Salai, Chennai – 600 119, Tamil Nadu. India.

SUBJECT NAME:Data Structures and Algorithms

SUBJECT CODE: SCSA1205

UNIT : I
SATHYABAM
A
INSTITUTE OF SCIENCE AND TECHNOLOGY
Deemed to be University
Declared as category ‘A’ University by MHRD, Govt. of India
Jeppiaar Nagar, Rajiv Gandhi Salai, Chennai – 600 119, Tamil Nadu. India.

Unit-I
• Introduction Data Structures - Need - classification - operations –
Abstract data types (ADT) - Array - characteristics - types - storage
representations. Array Order Reversal-Array Counting or Histogram-
Finding the maximum Number in a Set, Recursion- Towers of Hanoi-
Fibonacci series-Factorial.
Algorithm
• Algorithm is finite set of logic or instructions, written in order for
accomplishing the certain predefined task.
• Each algorithm must have:
• Specification: Description of the computational procedure.
• Pre-conditions: The condition(s) on input.
• Body of the Algorithm: A sequence of clear and unambiguous instructions.
• Post-conditions: The condition(s) on output.
Characteristics of an Algorithm
• Input: An algorithm must have 0 or well defined inputs.
• Output: An algorithm must have 1 or well defined outputs, and
should match with the desired output.
• Finiteness: An algorithm must be terminated after the finite number
of steps.
• Effectiveness: An algorithm must have step-by-step directions which
is independent of any programming code.
• Definiteness: An algorithm must be unambiguous and clear.
Major categories of algorithms
• Sort: Algorithm developed for sorting the items in certain order.
• Search: Algorithm developed for searching the items inside a data
structure.
• Delete: Algorithm developed for deleting the existing element from the
data structure.
• Insert: Algorithm developed for inserting an item inside a data
structure.
• Update: Algorithm developed for updating the existing element inside a
data structure.
performance of algorithm
• Time complexity: It is a way of representing the amount of time
needed by a program to run to the completion.
• Space complexity: It is the amount of memory space required by an
algorithm, during a course of its execution.
Data
• Data means a value or set of values.
• for example, student’s name and its id are the data about the student.
Structure
• A structure is an arrangement of and relations between parts or
elements.
• It has a form or shape.
Data Structure
• A data structure is an arrangement of data elements.
• Data Structure can be defined as the group of data elements which provides an efficient way of storing and
organizing data in the computer so that it can be used efficiently.
• Examples of Data Structures are arrays, Linked List, Stack, Queue, etc
Data Structure
• Data Structure mainly specifies the following three things

o Organization of Data
o Accessing methods
o Processing alternatives for information

Algorithm + Data Structure = Program

Need of Data Structures

• As applications are getting complexed and amount of data is increasing day by day,
there may arise the following problems:
• Processor speed: To handle very large amount of data, high speed processing is
required.
• Data Search:If our application needs to search for a particular item, it needs to traverse
all the items every time, results in slowing down the search process.
• Multiple requests:If thousands of users are searching the data simultaneously on a
web server, then there are the chances that a very large server can be failed during that
process.
• In order to solve the above problems, data structures are used. Data is organized to
form a data structure in such a way that all items are not required to be searched and
required data can be searched instantly.
Advantages of Data Structures
• Efficiency: Efficiency of a program depends upon the choice of data
structures.
• Reusability: Data structures are reusable, i.e. once we have
implemented a particular data structure, we can use it at any other
place.
• Abstraction: Data structure is specified by the ADT which provides a
level of abstraction.
Classification of Data Structure

•Data Structures are normally classified into two broad categories

1. Primitive Data Structure

2. Non-primitive data Structure

Classification of Data Structure
Classification of Data Structure
• Primitive Data Structures
• Simple data structure can be constructed with the help of primitive data
structure.
• A primitive data structure used to represent the standard data types of any
one of the computer languages.
• Variables, pointers, structures, unions, etc. are examples of primitive data
structures.
Non Primitive Data Structures
• Non Primitive Data Structures are classified as linear or non-linear.
• Linear- Arrays, linked lists, queues and stacks.
• Non-Linear- Trees and Graphs
Linear Data Structures
• A data structure is called linear if all of its elements are arranged in
the linear order.
• In linear data structures, the elements are stored in non-hierarchical
way where each element has the successors and predecessors except
the first and last element.
• Linear data structures can be constructed as a continuous
arrangement of data elements in the memory.
• It can be constructed by using array data type.
Types of Linear Data Structures
• Arrays: An array is a collection of similar type of data items stored in
consecutive memory location and is referred by common name; each
data item is called an element of the array.
• The data type of the element may be any valid data type like char, int,
float or double.
• The elements of array share the same variable name but each one
carries a different index number known as subscript.
• The array can be one dimensional, two dimensional or
multidimensional.
Linked List
• Linked list is a linear data structure which is used to maintain a list in
the memory.
• It can be seen as the collection of nodes stored at non-contiguous
memory locations.
• Each node of the list contains a pointer to its adjacent node.
• It is a collection of data of same data type but the data items need
not be stored in consecutive memory locations.
Stack
• Stack is a linear list in which insertion and deletions are allowed only
at one end, called top.
• It is a Last-In-First-Out (LIFO) linear data structure.
• Here, the element which is placed (inserted or added) last, is
accessed first.
• In stack terminology, insertion operation is
called PUSH operation and removal operation is
called POP operation.
Example
Queue
• Queue is a linear list in which elements can be inserted only at one
end called rear and deleted only at the other end called front.
• It is a First-In-First-Out Linear data structure.
• Queue is opened at both end therefore it follows First-In-First-Out
(FIFO) methodology for storing the data items.
Operations applied on Linear Data Structure
• The following list of operations applied on linear data structures
• 1. Add an element
• 2. Delete an element
• 3. Traverse
• 4. Sort the list of elements
• 5. Search for a data element
• 6. Merge the data
Non-Linear

• This data structure does not form a sequence i.e. each item or element is connected with two or more
other items in a non-linear arrangement.
• The data elements are not arranged in sequential structure.
Trees

• Trees are multilevel data structures with a hierarchical relationship among its elements known as
nodes.
• The bottommost nodes in the hierarchy are called leaf node while the topmost node is called root node.
• Each node contains pointers to point adjacent nodes.
• Trees are used to represent data that has some hierarchical relationship among the data elements.
• Tree data structure is based on the parent-child relationship among the nodes.
Graphs:

• Graphs can be defined as the pictorial representation of the set of elements (represented by vertices)
connected by the links known as edges.
• A graph is different from tree in the sense that a graph can have cycle while the tree cannot have the one.
• Graph is used to represent data that has relationship between pair of elements not necessarily hierarchical in
nature.
Operations applied on non-linear data structures

1. Add elements

2.Delete elements
 
3.Display the elements
 
4.Sort the list of elements
 
5.Search for a data element
Arrays
• An array is a collection of similar type of data items stored in
consecutive memory location and is referred by common name; each
data item is called an element of the array.
• The data type of the element may be any valid data type like char, int,
float or double.
• The elements of array share the same variable name but each one
carries a different index number known as subscript.
• The array can be one dimensional, two dimensional or
multidimensional.
Syntax
• datatype [] arrayName
• arrayName = new dataType[size of the array]
• datatype [] arrayName = new dataType[size of the array]

• Example
• int [] i;
• i = new int[10];
• int [] i = new int[10];
Initialization – Single Dimension Array
• int [] x = new int[1];
• int [] x = {10}; x 10
• int [] x = { 10, 20 };

x 10 20
Characteristics
(i)Array stores elements of same data type.
(ii)The elements of an array are stored in subsequent memory locations.
(iii)The name of array represents the starting address of the elements.
• 
(i)When data objects are stored in array, individual objects are selected by an index.
(ii)By default an array index starts from 0 and ends with (n-1). Index is also referred
as subscripts.
(iii)The size of the array is mentioned at the time of declaring array.
• 
(i)While declaring 2D array, number of columns should be specified whereas for
number of rows there is no such rule.
(ii)Size of array can’t be changed at run time.
Array Types
• Single Dimension Array
• Multi Dimension Array
• Double Dimension Array (or) Matrix
• Three Dimension Arrays
Initialization – Double Dimension Array
• int [][] x = new int[1][1];
• Int [][] x = new int[4][3]; x 10
• int [][] x = {10};
• int [][] x = { {10, 20}, {30, 40} };
x 10 20

30 40
Three Dimensional Array
int [][][] A = new int[3][4][3];

(1,1,1) (1,1,2) (1,1,3) (2,1,1) (2,1,2) (2,1,3) (3,1,1) (3,1,2) (3,1,3)

(1,2,1) (1,2,2) (1,2,3) (2,2,1) (2,2,2) (2,2,3) (3,2,1) (3,2,2) (3,2,3)

(1,3,1) (1,3,2) (1,3,3) (2,3,1) (2,3,2) (2,3,3) (3,3,1) (3,3,2) (3,3,3)

(1,4,1) (1,4,2) (1,4,3) (2,4,1) (2,4,2) (2,4,3) (3,4,1) (3,4,2) (3,4,3)

1 2 3
Reversing an Array
• Input: A = [1, 2, 3, 4, 5]
• Output: A = [5, 4, 3, 2, 1]
• Algorithm:
• n = length of the Array (A)
• for i = n – 1, j = 0, i >= 0, increment j by 1 and decrement i by
• B[j] = A[i]
• for i = 0 to n
• A[i] = B[i]
Finding the maximum Number in a Set
• Algorithm

• Read the array elements

 
• Initialize first element of the array as max.

• Traverse array elements from second and compare every element with
current max

• Find the largest element in the array and assign it as max

• Print the largest element.

Array Count
•Input Array: A[1..n] store input data where A[j] ∈ {1, 2, 3, …, k}

•Output Array: B[1..n] finally store the sorted data

•Example 1 :
•Given List :
•A = { 2,5,3,0,2,3,0,3}

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

C- Highest Element is 5 in the given array

0 1 2 3 4 5
0 0 0 0 0 0

C[A[J]]=C[A[J]]+1
0 1 2 3 4 5
2 0 2 3 0 1
Storage Representation
• An array is a set of homogeneous elements.
• Every element is referred by an index.
• Memory storage locations of the elements are not arranged as a
rectangular array with rows and columns. Instead they are arranged in
a linear sequence beginning with location 1,2,3 and so on.
• The nature of storage depends on how the programming language
stores the 2D array elements.
• The elements are stored either column-by-column (column-major
order) or row-by-row (row-major order).
Example – Row Major Order
Data (A):
• Rows : 3 1 2 3 4
• Columns : 4 5 6 7 8
9 10 11 12
Linear Arrangement of Array A
Row 1 2 3
Index (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4)

Memory 100 102 104 106 108 110 112 114 116 118 120 122

Data 1 2 3 4 5 6 7 8 9 10 11 12
Row Major Order
• Location (A [j,k] ) = Base Address of (A) + w [ (N * (j-1)) + (k-1) ]

• Location (A [j, k] ): Location of jth row and kth column

• Base (A) : Base Address of the Array A
•w : Bytes required to represent single element of the Array A
•N : Number of columns in the Array
•j : Row position of the element
•k : Column position of the element
Example
(A [j,k] ) = Base Address of (A) + w [ (N * (j-1)) + (k-1) ]

Linear Arrangement of Array A

Row 1 2 3
Index (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4)
Memory 100 102 104 106 108 110 112 114 116 118 120 122
Data 1 2 3 4 5 6 7 8 9 10 11 12

Base (A) = 100

w = 2 Bytes (integer type)
N=4
j=3
k=2
Location ( A [3, 2] ) = 100 + 2 [ (4 * (3-1) + (2-1) ]
= 118
Example – Column Major Order
Data (A):
• Rows : 3 1 2 3 4
• Columns : 4 5 6 7 8
9 10 11 12
Linear Arrangement of Array A
Column 1 2 3 4
Index (1,1) (2,1) (3,1) (1,2) (2,2) (3,2) (1,3) (2,3) (3,3) (1,4) (2,4) (3,4)

Memory 100 102 104 106 108 110 112 114 116 118 120 122

Data 1 5 9 2 6 10 3 7 11 4 8 12
Column Major Order
• Location (A [j, k] ) = Base Address of (A) + w [ (M * (k-1)) + (j-1) ]

• Location (A [j, k] ): Location of jth row and kth column

• Base (A) : Base Address of the Array A
•w : Bytes required to represent single element of the Array A
•M : Number of rows in the Array
•j : Row position of the element
•k : Column position of the element
Example
Linear Arrangement of Array A
Column 1 2 3 4
Index (1,1) (2,1) (3,1) (1,2) (2,2) (3,2) (1,3) (2,3) (3,3) (1,4) (2,4) (3,4)

Memory 100 102 104 106 108 110 112 114 116 118 120 122

Data 1 5 9 2 6 10 3 7 11 4 8 12

Base (A) = 100

w = 2 Bytes (integer type)
M=3
j=3
k=2
Location ( A [3, 2] ) = 100 + 2 [ (3 * (2-1) + (3-1) ]
= 110
Recursion
• When function is called within the same function, it is known as recursion.
• The function which calls the same function, is known as recursive function.
• Linear Recursion

• Binary Recursion
• Linear Recursion: the function calls itself repeatedly until it hits the termination
condition (Base condition). Eg.Factorial
• Binary Recursion:This form of recursion has the potential for calling itself
twice instead of once as before. Eg:Binary search
Design Methodology and Implementation of Recursion
 

The recursive solution for a problem involves a two-way journey:

 
✱ First we decompose the problem from the top to the bottom
 
✱ Then we solve the problem from the bottom to the top.
Steps for Designing Recursive Algorithms

• Each call of a recursive algorithm either solves one part of the problem or it reduces the size of
the problem.
• The general part of the solution is the recursive call. At each recursive call, the size of the
problem is reduced.
• The statement that solve the problem is known as the base case.
• Every recursive algorithm must have a base case.
• The rest of the algorithm is known as the general case. The general case contains the logic
needed to reduce the size of the problem.
• Once the base case has been reached, the solution begins.
• We now know one part of the answer and can return that part to the next, more
general statement.
• This allows us to solve the next general case.
• As we solve each general case in turn, we are able to solve the next-higher general case until
we finally solve the most general case, the original problem.
Rules for Designing a Recursive Algorithm

• First, determine the base case.

• Then determine the general case.

• Combine the base case and the general cases into an algorithm.
 
• Each recursive call must reduce the size of the problem and move it toward the base
case.
 
• The base case, when reached, must terminate without a call to the recursive algorithm;
that is, it must execute a return.
FACTORIAL

•Factorial of the given number can be calculated as:

n
• n! = 1 × 2 × 3 × … × n = Õ i
i=1
Algorithm

• RecursiveFactorial (n)

if (N equals 0)

Return 1

else

Return (n*recursiveFactorial (n-1))

end if
end recursiveFactorial
Calling a Recursive Factorial Algorithm with n=3
FIBONACCI SERIES

•Fibonacci Series generates subsequent number by adding two previous numbers. Fibonacci series
starts from two numbers ? F0 & F1. The initial values of F0 & F1 can be

• 0 and 1

• 1 and 1 respectively.

• Fibonacci series satisfies the following conditions

•Fn = Fn-1 + Fn-2

•The Fibonacci series looks like

F8 = 0 1 1 2 3 5 8 13
Fibonacci Recursive Algorithm

Fibo (n)

If n = 0
Return 0
Else
If n = 1
Return 1

Else
Fibo (n) = Fibo (n-1) + Fibo (n-2)
Return Fibo (n)
Int fibo(n) {
n=3 If (n==0) return 0;
If (n==1) return 1;
return fibo(n-1)+fibo(n-2);
}

Int fibo(n) { Int fibo(n) {

If (n==0) return 0; If (n==0) return 0;
n=2 If (n==1) return 1; n=1 If (n==1) return 1;
return fibo(n-1)+fibo(n-2); return fibo(n-1)+fibo(n-2);
} }
Int fibo(n) { Int fibo(n) {
If (n==0) return 0; If (n==0) return 0;
n=1 If (n==1) return 1; n=0 If (n==1) return 1;
return fibo(n-1)+fibo(n-2); return fibo(n-1)+fibo(n-2);
} }
1+0=1

n=1 n=0
Int fibo(n) { Int fibo(n) {
If (n==0) return 0; If (n==0) return 0;
If (n==1) return 1; If (n==1) return 1;
return fibo(n-1)+fibo(n-2); return fibo(n-1)+fibo(n-2);
} }
1 +1=2

n=1
Int fibo(n) {
If (n==0) return 0;
If (n==1) return 1;
return fibo(n-1)+fibo(n-2);
}
Towers of Hanoi

• There are three towers

• Need to move all of the disks from the first tower to the last tower
• Larger disks can not be placed on top of smaller disks
• The third tower can be used to temporarily hold disks
Towers

Disks

Smallest

Largest
Rules

• Only one disk can be moved among the towers at any given time.

• Only the “top” disk can be removed.

• No large disk can sit over a small disk

Tower of Hanoi

Source Destination Intermediate

Tower of Hanoi

Source Destination Intermediate

Tower of Hanoi

Source Destination Intermediate

Tower of Hanoi

Source Destination Intermediate

Tower of Hanoi

Source Destination Intermediate

Tower of Hanoi

Source Destination Intermediate

Tower of Hanoi

Source Destination Intermediate

Recursive Procedure
def moveDisk(n, source, dest, inter):
if n>=1:
moveDisk(n-1, source, inter, dest)
print("Moving Disk
From:“,source,"To:",dest)
moveDisk(n-1, inter, dest, source)

moveDisk(3, "A", "B", "C")

Output

1. Moving Disk C From: A To: B

2. Moving Disk B From: A To: C
3. Moving Disk A From: B To: C
4. Moving Disk C From: A To: B
5. Moving Disk B From: C To: A
6. Moving Disk A From: C To: B
7. Moving Disk C From: A To: B
1. Move A to B 0, A, C, B
2. Move A to C 1, A, B, C
3. Move B to C
4. Move A to B
0, C, B, A
5. Move C to A 2, A, C, B
6. Move C to B 0, B, A, C
7. Move A to B
1, B, C, A
0, A, C, B
3, A, B, C
0, C, B, A
1, C, A, B
0, B, A, C
2, C, B, A
0, A, C, B
1, A, B, C
0, C, B, A
Tail Recursion

A function call is said to be tail recursive if there is nothing to do after the function returns except return
its value.
void print(int n)
{
if (n < 0)
return;
printf(“%d”, n);
print(n-1);
}
ABSTRACT DATA TYPES

• Abstract Data Type (ADT) is a type or class for objects whose behavior is defined by a set of value and a
set of operations.
• The user of data type does not need to know how that data type is implemented
• Three ADTs namely List ADT, Stack ADT, Queue ADT.
List ADT

• The data is generally stored in key sequence in a list which has a head structure consisting of count, pointers
and address of compare function needed to compare the data in the list.
• The data node contains the pointer to a data structure and a self-referential pointer which points to the next
node in the list.

//List ADT Type Definitions typedef

struct node{

void *DataPtr; struct node *link;

} Node; typedef struct{ int count;

Node *pos; Node *head; Node

*rear;
int (*compare) (void *argument1, void *argument2);
 
} LIST;
List Functions
Stack ADT

• In Stack ADT Implementation instead of data being stored in each node, the pointer to data is stored.
• The stack head structure also contains a pointer to top and count of number of entries currently in stack.

//Stack ADT Type Definitions

typedefstruct node{

void *DataPtr; struct

node *link;

} StackNode;

typedefstruct{ int count;

StackNode *top;
} STACK;
Operations
• All operations take place at a single end that is top of the stack and following operations can
be performed:
• 
• push() – Insert an element at one end of the stack called top.
• 
• pop() – Remove and return the element at the top of the stack, if it is not empty.
• 
• peek() – Return the element at the top of the stack without removing it, if the stack is not empty.
• 
• size() – Return the number of elements in the stack.
• 
• isEmpty() – Return true if the stack is empty, otherwise return false.
• 
• isFull() – Return true if the stack is full, otherwise return false.
Queue ADT
• 

• //Queue ADT Type Definitions typedefstructnode { void*DataPtr;

• structnode *next;
• 

• } QueueNode; typedefstruct { QueueNode *front; QueueNode *rear; intcount;

•}
QUEUE;
• enqueue() – Insert an element at the end of the queue.
• 
• dequeue() – Remove and return the first element of the queue, if the queue is
not empty.
• 
• peek() – Return the element of the queue without removing it, if the queue is
not empty.
• 
• size() – Return the number of elements in the queue.
• 
• isEmpty() – Return true if the queue is empty, otherwise return false.
• 
• isFull() – Return true if the queue is full, otherwise return false.
Quiz
 1.Which of the following uses FIFO method
A - Queue
B - Stack
C - Hash Table
D - Binary Search Tree

2.A data structure in which linear sequence is maintained by pointers is known as

• (A) Array
• (B) Stack
• (C) Linked list
• (D) Pointer-based data structure
3. ____ is a linear collection of self-referential structures, called nodes, connected by pointer
links.
• (A) Queue
• (B) Linked list
• (C) Tree
• (D) Stack
4.Which of the following is not a linear data structure?
• (A) Stack
• (B) Queue
• (C) Linked list
• (D) Binary tree
5.Which of the following data structure permits insertion and deletion operations
only on one end of the structure?
• (A) Linked list
• (B) Array
• (C) Stack
• (D) Queue
6.Inserting an item into the stack when stack is notfull is called
…………. Operation and deletion of itemform the stack, when stack is
not empty is called………..operation. A) push, pop
• B) pop, pushC) insert, deleteD) delete, inser
7.……………. Is a pile in which items are added at oneend and
removed from the other.
•  A) Stack 
• B) Queue
• C) ListD) None of the above
8.Which of the following data structure can’t storethe non-
homogeneous data elements? A) Arrays
• B) RecordsC) PointersD) Stacks
• 9.To represent hierarchical relationship betweenelements, Which data
structure is suitable?
•  A) Dequeue B) Priority 
• C) Tree
• D) Graph
10.A graph is a collection of nodes, called ………. Andline segments
called arcs or ……….. that connect pairof nodes. A) vertices, edges
• B) edges, verticesC) vertices, pathsD) graph node, edges
11.Which of the following data structure is non-lineartype?
•  A) StringsB) ListsC) Stacks
• D) Tree