COURSE FILECONTENTS

Regulation:R19 Year:II - I Academic Year:2020 - 2021

Subject:DATA STRUCTURRES
Course Coordinator (s):
Available/
Description
Not Available
A I. Contents of Course File Available
B I. Syllabus with Prescribed text books Available
II. Course Objectives and Outcomes Available
III.CO-PO and PSO mapping with justification Available
IV. Gap Identification and Contents Beyond Syllabus with Available
mapping
C I. Academic Calendar Available
II. Teaching/Instructional Plan Available
III. Instructional Methodology – Pedagogical initiatives and Available
Innovation
IV. Assessment of Attainment of COs Plan – Direct and Indirect Available
V. University Results for Previous years and Current Attainment Available
Target
VI. Individual Time Table Available
D I. Course Materials/Notes – Unit wise Available
E I. Previous Question papers – Internal and External Available
II.Question Bank – Unit wise Available
III. Assignment and Tutorial Questions with Solutions Available
IV. Internal Examination – Question Papers with Key and Scheme Available
of Evaluation
F I. Attendance Record Available
G II. List of Slow Learners in the course Available
III. List of Advanced Learners and Programs conducted Available
IV. Remedial Classes to the Slow Learners Available
V. Remedial Classes Attendance Report Available
VI. Syllabus Coverage – Prescribed and Actual Available
VII. Make Up classes - Schedule Available
H I. Evaluation Record – Internal, Quiz and Assignments Available
II. Sample Internal Answer Scripts and Assignments Available
I I. Attainment Record – Direct and Indirect Available
II. Attainment Analysis – Corrective Action/Remedial Measures Available
J I. University Results – Regular, Revaluation, Supplementary (1st) Available
I. Course Closure Report – Suggestion for Continuous Available
K Improvement

Module Coordinator (s):

SYLLABUS
e Name: data structures Course Code:
h, Year – Sem : IT,II-I Regulation:R-19
mic year:2022-23 Faculty :
I
 tructures - Definition, Classification of Data Structures, Operations on Data Structures, Abstract Data Type (ADT),
naries of algorithms. Time and Space complexity.
ing - Linear search, Binary search, Fibonacci search.
- Insertion sort, Selection sort, Exchange (Bubble sort, quick sort), distribution (radix sort), merging (Merge sort)
hms.
II
List: Introduction, Single linked list, Representation of Linked list in memory, Operations on Single Linked list-
on, Deletion, Search and Traversal ,Reversing Single Linked list, Applications on Single Linked list- Polynomial
sion Representation ,Addition and Multiplication, Sparse Matrix Representation using Linked List, Advantages and
antages of Single Linked list, Double Linked list-Insertion, Deletion, Circular Linked list-Insertion, Deletion.
III
s: Introduction to Queues, Representation of Queues-using Arrays and using Linked list, Implementation of Queues-using
and using Linked list, Application of Queues-Circular Queues, Deques, Priority Queues, Multiple Queues.
Introduction to Stacks, Array Representation of Stacks, Operations on Stacks, Linked list Representation of Stacks,
ions on Linked Stack, Applications-Reversing list, Factorial Calculation, Infix to Postfix Conversion, Evaluating Postfix
sions.
IV
Basic Terminology in Trees, Binary Trees-Properties, Representation of Binary Trees using Arrays and Linked lists.
Search Trees- Basic Concepts, BST Operations: Insertion, Deletion, Tree Traversals, Applications-Expression Trees,
ort, Balanced Binary Trees- AVL Trees, Insertion, Deletion and Rotations.
V
: Basic Concepts, Representations of Graphs-Adjacency Matrix and using Linked list,
Traversals
& DFT), Applications- Minimum Spanning Tree Using Prims & Kruskals Algorithm,
a’s shortest path,
ive closure, Warshall’s Algorithm.
ooks:
Structures Using C. 2nd Edition.Reema Thareja, Oxford.
Structures and algorithm analysis in C, 2nded, Mark Allen Weiss.
nce Books:
damentals of Data Structures in C, 2nd Edition, Horowitz, Sahni, Universities Press.
Structures: A PseudoCode Approach, 2/e, Richard F.Gilberg, Behrouz A. Forouzon, Cengage.
Structures with C, Seymour Lipschutz TMH
urces:
//algs4.cs.princeton.edu/home/
://faculty.washington.edu/jstraub/dsa/Master_2_7a.pdf

Course Coordinator(s):
Module Coordinator Program Coordinator HOD

COURSE OBJECTIVES & OUTCOMES

Course Name:DATA STRUCTURES Course Code:

Branch, Year – Sem : IT-II-I Regulation:R-19

Academic year:2020-21 Faculty :

Course Objectives:
The objective of the course is to
 Introduce the fundamental concept of data structures and abstract data types
 Emphasize the importance of data structures in developing and implementing efficient algorithms
 Describe how arrays, records, linked structures, stacks, queues, trees, and graphs are represented in memory and used by
algorithms

Course Outcomes:
After completing this course a student will be able to:
 Summarize the properties, interfaces, and behaviors of basic abstract data types
 Discuss the computational efficiency of the principal algorithms for sorting & searching
 Use arrays, records, linked structures, stacks, queues, trees, and Graphs in writing programs
 Demonstrate different methods for traversing trees

Module Co-ordinator Program Co-ordinator HOD

Course Name: data structures Course Code:

Branch, Year – Sem : IT,II-I Regulation:R-19

Academic year:2022-23 Faculty :

P P P P P P
P P P P P P P
P P S
Course Outcomes O O O
O O O O O S S O
O O O O
4 5 6
1 3 1 1 1 O O 3
2 7 8 9
0 1 2
1 2
CO-1 : Describe mathematical
methods to analyze the
performance of an algorithm 3 2 1 - - - - - - - - 1 3 1 -
using asymptotic notations .

CO-2 : Apply algorithm

design techniques for
3 1 1 - - - - - - - - 1 3 1 -
solving realistic problems.
 CO-3 : Analyze the algorithms
and design principles to derive
solutions for real-time 2 2 3 - - - - - - - - 1 3 1 -
applications.

CO-4 : Design algorithms for

computational problems and
compare different algorithm 3 2 1 - - - - - - - - 1 2 1 -
methodologies

. CO-5 : Categorize algorithms

as NP Hard and NP Complete 3 2 1 - - - - - - - - 1 2 1 -

AVG 1 - - - - - - - - 2 -
. .
2.8 8 1.4 1 6 1
Note:Enter Correlation levels 1,2 or 3 as defined below:

1: Slightly(Low) 2: Moderate(Medium) 3:

Substantial(High) If there is no correlation, put “-“

CO: PO and PSO Mapping with Justification:

Correlation
CO PO/PSO Justification (including CO statement)
Level
CO-1: Describe mathematical methods to analyze the performance of an
CO-
PO1 3 algorithm using asymptotic notations. Requires a strong foundation in
1
mathematical and algorithmic principles.
Analytical skills are required to evaluate algorithm efficiency, aligning with
CO-1 PO2 2
PO2.
CO-1 PO3 1 Basic design skills are applied while comparing algorithm performances.
Learning about performance analysis supports lifelong learning and
CO-1 PO12 1
upskilling.
CO-1 PSO1 3 Asymptotic analysis is fundamental in computing, directly supporting PSO1.
Slight relevance when algorithm performance impacts domain-specific
CO-1 PSO2 1
solutions.
CO-2: Apply various algorithm design techniques (Divide and Conquer,
CO-
PO1 3 Greedy, Dynamic Programming, Backtracking) to solve computational
2
problems efficiently. Strong engineering knowledge is required.
Solving computational problems requires critical thinking and problem
CO-2 PO2 3
analysis, supporting PO2.
Designing efficient algorithms aligns with PO3 (Design/Development of
CO-2 PO3 2
Solutions).
CO-2 PO12 1 Applying algorithm design techniques enhances lifelong learning skills.
CO-2 PSO1 3 Core competency in algorithm design is essential in computing, supporting
 Correlation
CO PO/PSO Justification (including CO statement)
Level
PSO1.
CO-2 PSO2 2 Relevant for domain-specific computational solutions.
CO-3: Analyze and compare the performance of algorithms for searching,
CO-
PO1 3 sorting, and graph problems. Strong foundation in algorithmic principles
3
required.
Performance analysis requires analytical and problem-solving skills,
CO-3 PO2 3
supporting PO2.
Comparison of algorithm efficiency aids in designing optimized solutions,
CO-3 PO3 2
aligning with PO3.
CO-3 PO12 1 Understanding algorithm performance contributes to lifelong learning.
CO-3 PSO1 3 Essential for domain competency in computing and software development.
CO-3 PSO2 2 Helps in selecting domain-specific optimal solutions.
CO-4: Design and implement algorithms for NP-hard problems using
CO-
PO1 3 heuristic and approximation techniques. Requires deep understanding of
4
algorithm principles.
CO-4 PO2 3 Problem-solving for NP-hard problems aligns with PO2.
Designing heuristic algorithms directly maps to PO3 (Design/Development of
CO-4 PO3 3
Solutions).
CO-4 PO12 1 Learning heuristic and approximation methods supports lifelong learning.
Developing solutions for complex computational problems is central to
CO-4 PSO1 3
PSO1.
CO-4 PSO2 2 Heuristic techniques can be applied in domain-specific scenarios.
CO-5: Evaluate the suitability of different algorithms and data structures for
CO-
PO1 3 real-world applications and optimize them for performance. Strong
5
knowledge of algorithms and data structures required.
Analytical skills are needed to evaluate and compare algorithms, aligning
CO-5 PO2 3
with PO2.
Selecting and optimizing algorithms supports PO3 (Design/Development of
CO-5 PO3 3
Solutions).
CO-5 PO12 1 Evaluation and optimization promote continuous learning.
CO-5 PSO1 3 Core competency in choosing efficient solutions aligns with PSO1.
CO-5 PSO2 2 Helps in applying optimal algorithms in domain-specific applications.

Course Coordinator(s)

Module Coordinator Program Coordinator HOD

ACADEMIC CALENDAR
 TEACHING/INSTRUCTIONAL PLAN
Course Name: DATA STRUCTURESCourse Code: Regulation:R20A
Branch, Year – Sem: I.T, IV B.Tech. I Sem Faculty:
Academic year:2020-21

No. of
Teaching
UNITS TOPICS Classes Teaching Aids
Methods
Planned
 Introduction  PPTs
 Lecture
01  LCD Projector
 Whiteboard

Definition,  PPTs
Classification of  Lecture  LCD Projector
Data Structures, 02
 Whiteboard

Operations on Data  PPTs

Structures,  Lecture
01  LCD Projector
 Discussion
 Whiteboard

Abstract Data Type  PPTs

(ADT),  Lecture  LCD Projector
02
 Whiteboard

Preliminaries of  PPTs
algorithms  Lecture  LCD Projector
01
 Whiteboard
UNIT-
I Time and Space  PPTs
complexity.  Lecture  LCD Projector
02
 Whiteboard

Searching - Linear  PPTs

search  Lecture  LCD Projector
02
 Whiteboard

Binary search,  PPTs

Fibonacci search.  LCD Projector
02  Lecture
 Whiteboard

UNIT- Queues:  PPTs

II Introduction to  Lecture
02  LCD Projector
Queues,  Discussion
 Whiteboard

and using Linked  PPTs

list,  Lecture
02  LCD Projector
 Whiteboard

Representation of  Lecture
Queues-using  Problem  PPTs
Arrays Solving  LCD Projector
02
Method  Whiteboard

Search Reversing  Lecture

Single Linked list,,  PPTs
 Problem
02  LCD Projector
Solving
 Whiteboard
 Discussion

Reversing Single 02  Lecture  PPTs

 Linked list,  Problem
Solving
 LCD Projector
Method
 Whiteboard
 Discussion

, Applications on  Lecture
Single Linked list  Problem  PPTs
02 Solving  LCD Projector
Method  Whiteboard
 Discussion

Introduction to
Queues,  PPTs
 Lecture
Representation of  LCD Projector
01  Discussion
Queues-using  Whiteboard
Arrays and using
Linked list
Implementation of  PPTs
Queues-using  Lecture  LCD Projector
Arrays and using 01  Discussion  Whiteboard
Linked list
 Visual Aids- Images

Application of  PPTs
Queues-Circular  Lecture
01  LCD Projector
 Discussion
 Whiteboard

Deques, Priority  PPTs

UNIT- Queues, Multiple  Lecture
III 01  LCD Projector
Queues  Discussion
 Whiteboard

Introduction to  PPTs
Stacks, Array  Lecture
02  LCD Projector
Representation of  Discussion
 Whiteboard
Stacks,
Operations on  Lecture
Stacks, Linked list  PPTs
 Discussion
Representation of 02  LCD Projector
 Problem
Stacks, Operations  Whiteboard
Solving

Applications-  PPTs
Reversing list,  Lecture
Factorial 02  LCD Projector
 Discussion
Calculation, Infix to  Whiteboard
Postfix Conversion
UNIT- Trees: Basic  Lecture
IV Terminology in Tree  PPTs
 Discussion
02  LCD Projector
 Problem
 Whiteboard
Solving

Binary Trees- 02  Lecture  PPTs

Properties,  Discussion  LCD Projector
Representation of  Problem  Whiteboard
Binary Trees using
Arrays and Linked
 lists Solving

Binary Search  Lecture

Trees- Basic  PPTs
 Discussion
Concepts, 02  LCD Projector
 Problem
 Whiteboard
Solving

BST Operations:  Lecture

Insertion, Deletion,  PPTs
 Discussion
Tree Traversals 02  LCD Projector
 Problem
 Whiteboard
Solving

Applications-  Lecture
Expression Trees,  PPTs
 Discussion
Heap Sort 1  LCD Projector
 Problem
 Whiteboard
Solving

Applications-  Lecture
Expression Trees,  PPTs
 Discussion
Heap Sort, Balanced 1  LCD Projector
 Problem
Binary Trees-  Whiteboard
Solving

AVL Trees,  Lecture

Insertion, Deletion  PPTs
 Discussion
and Rotation 1  LCD Projector
 Problem
 Whiteboard
Solving

Trees: Basic  Lecture  PPTs

Terminology in Tree  Discussion  LCD Projector
02
 Whiteboard

UNIT- Graphs: Basic  PPTs

V Concepts,  Lecture
03  LCD Projector
 Discussion
 Whiteboard

Representations of  PPTs
Graphs-  Lecture
02  LCD Projector
 Discussion
 Whiteboard

-Adjacency Matrix  PPTs

and using Linked  Lecture
01  LCD Projector
list,  Discussion
 Whiteboard

Graph Traversals  PPTs

(BFT & DFT),  Lecture
01  LCD Projector
Applications-  Discussion
 Whiteboard

Minimum  PPTs
 Lecture
Spanning Tree  LCD Projector
01  Discussion
Using Prims  Whiteboard

& Kruskals 1  Lecture  PPTs

Algorithm
  Discussion
 LCD Projector
 Problem
 Whiteboard
Solving

Dijkstra’s  Lecture
 PPTs
shortest path,  Discussion
1  LCD Projector
 Problem
 Whiteboard
Solving

Total
No. of
60
Classe
s

Course Coordinator (s):

Module Coordinator Program Coordinator HOD

INSTRUCTIONAL METHODOLOGY- PEDAGOGICAL INITIATIVES & INNOVATIONS

Course Name:Data Structures Course Code:

Branch, Year – Sem:IT, II - I Regulation: R 19 Academic year: 2023-24

S.No. INSTRUCTIONAL METHODOLOGY YES/

NO
ICT Methods

a. Chalk & Board YES

1.
b. PPT YES

c. E-Learning YES
2. MOOCS & Open Sources(NPTEL) NO

3. Guest Lectures & Workshops NO

4. Collaborative Learning(Peer Teaching) NO

5. Role Play NO

6. Group discussions & Group Activity NO

7. Project based learning NO

8. Learning from Industrial visits NO

9. Seminar Method NO

10. Use of online journals, subscriptions NO

 Course Coordinator(s)

Module Coordinator Program Coordinator HOD

ASSESSMENT PLAN – COs (DIRECT)

The course outcomes are evaluated using Internal and External assessments as per the following:

Regulation Internal Assessment – External Assessment – Set

Set Target
Target
R20 50 % Marks 35 % Marks
Sl. No Attainment Level students attaining the Set- Target

1 3 80 % of students Scoring more

than
the Set Target
2 2 60 % of students Scoring more
than
the Set Target
3 1 40 % of students Scoring more
than
the Set Target
4 0 Less than 40 % of students
Scoring more than the Set Target

Evaluation of Attainment Level - CO

CO Attainment level = 20% of Internal Attainment level + 80% of External Attainment level

For R20 regulations:

Weight-ages for different internal assessment tools are based on % of total marks.

Theory Courses: Internal attainment level = (50% of DESCRIPTIVE + 33% of OBJECTIVE + 17%
of ASSIGNMENT) attainment levels
Attainment levels in External Examinations:
(a) External Examination – Grade to Marks Conversion for Theory courses

RAN ME GRA
GE AN DE
91- 95 O
100
 81-90 85 A
71-80 75 B
61-70 65 C
51-60 55 D
41-50 45 E
40 39 F

(b) External Examination – Grade to Marks Conversion for laboratory courses

RAN ME GRA
GE AN DE
91- 95 O
100
81-90 85 A
71-80 75 B
61-70 65 C
51-60 55 D
41-50 45 E
40 39 F

External examination performance alone is obtained by subtracting final internal marks from the mean marks
obtained as per the grade awarded by University.

Project Work: Attainment level = (20% Internal + 80% External) attainment levels

ASSESSMENT PLAN – POs (DIRECT& INDIRECT)

The attainment of program outcomes (POs) and Program Specific Outcomes (PSOs) is evaluated by
PAC that identifies, collects, and prepares data from assessment processes. The assessment processes are
categorized as per the following.

1. Direct Assessments
2. Indirect Assessments
Direct Assessment Tools and Process:

Direct attainment level of a PO & PSO is determined by taking average across all
courses attainment levels addressing that PO and/or PSO. The average attainment levels of
all courses at program level are calculated as per the process described elsewhere. The PO
and PSO attainment levels are evaluated based on the Program level Course – PO
mapping.

Indirect Assessment Tools and Process:

Indirect attainment level of PO & PSO is determined based on the student exit surveys.
This data is generated by administering course and program exit surveys.

The indirect assessment tools along with their assessment criteria are given in Table.

Course Coordinator(s)

Module Coordinator Program Coordinator HOD

Course Name:DATA STRUCTURES Course Code:

Branch, Year – Sem : IT-II-I Regulation:R-19
Academic year:2020-21 Faculty :

Week / 1 2 3 4 5 6 7
 Hour
Mon DS
Tue DS
Wed DS
Thu DS
Fri
Sat DS

Module Co-ordinator Program Co-ordinator HOD

QUESTION BANK – UNIT WISE

nit Sl.No Questions Bloom’s
No. . Taxono
my level
UNIT 1
1. Explain the various operations on data structures with suitable 2 CO1
examples.
2 Explain the different notations of algorithm complexity (Big-O, Big-Ω, 1 CO1
Big-θ) with examples.
3 Write and explain the algorithm for Binary Search with its time 2 CO1
complexity.
4 Explain the working of Quick Sort with an example. 1 CO1
5 Write and explain the algorithm for Merge Sort and analyze its 3 CO1
I complexity.
6 Compare Insertion Sort, Selection Sort, Bubble Sort, and Quick 3 CO1
Sort.
7 Define Data Structure. Classify different types of data structures. 4 CO1
8 Explain Time complexity and Space complexity with an example. 4 CO1
 UNIT 2
1 Define Linked List. What are its advantages over arrays? 1 CO2
2 Explain insertion and deletion operations in a singly linked list with 1 CO2
algorithms.
3 Write an algorithm to reverse a singly linked list. 2 CO2
4 Explain polynomial representation and addition using a linked list. 2 CO2
5 3 CO2
Describe sparse matrix representation using a linked list with an
II example.
6 Differentiate between singly, doubly, and circular linked lists with 3 CO2
diagrams.
7 Write algorithms for insertion and deletion in a doubly linked
list.
8 Write an algorithm to traverse a singly linked list.

UNIT 3
1 Define Queue and its types. 1 CO3
2 Convert the infix expression (A+B) * C into postfix. 1 CO3

3 Explain queue implementation using arrays with algorithms. 2 CO3

4 Write algorithms for insertion and deletion operations in a circular 2 CO3

queue.
III 5 Implement a stack using a linked list with operations. 3 CO3

6 Explain infix to postfix conversion with an example. 3 CO3

7 Explain evaluation of postfix expression with algorithm and example. 4 CO3

8 Discuss applications of stacks in real life and in computer science. 4 CO3

UNIT 4
1 Define Binary Tree. List its properties. List different tree traversal 1 CO4
methods.
2 Explain array and linked list representation of binary trees. 2 CO4
IV 3 Write algorithms for insertion and deletion in a BST. 2 CO4
4 Discuss preorder, inorder, and postorder traversals with examples. 3 CO4
5 Explain AVL Tree insertion and rotations with examples. 2 CO4

UNIT 5
1 Explain BFS and DFS with algorithms and examples. 1 CO5
2 1 CO5
v Write and explain Prim’s algorithm for finding MST with an example.
3 Write Kruskal’s algorithm with an example. 2 CO5
4 Explain Dijkstra’s shortest path algorithm with an example. 2 CO5
5 Discuss Warshall’s algorithm for transitive closure. 3 CO5
6 Explain Dijkstra’s shortest path algorithm with an example. 3 CO5
 Course Code: Branch, Year – IT, 2 Year nd
Regulation: R 19

Academic year: 2020-2021

DATA STRUCTURES

ASSIGNMENT-1

1. Explain the different notations of algorithm complexity (Big-O, Big-Ω, Big-θ) with examples.
2. Write and explain the algorithm for Merge Sort and analyze its complexity.
3. Explain insertion and deletion operations in a singly linked list with algorithms
4. Differentiate between singly, doubly, and circular linked lists with diagrams.
5. Explain queue implementation using arrays with algorithms.

Course Coordinator(s):

Module Coordinator Program Coordinator HOD

 Course Code: Branch, Year – IT, 2 Year nd
Regulation: R 19

Academic year: 2020-2021

DATA STRUCTURES

ASSIGNMENT-2

1. Explain infix to postfix conversion with an example.

2. Define Binary Tree. List its properties. List different tree traversal methods.
3. Explain AVL Tree insertion and rotations with examples
4. Write and explain Prim’s algorithm for finding MST with an example
5. Explain Dijkstra’s shortest path algorithm with an example.

Course Coordinator(s):

Module Coordinator Program Coordinator HOD

 DEPARTMENT OF INFORMATION TECHNOLOGY
R19 II B.TECH. I SEM I.T MID-I DESCRIPTIVE EXAMINATIONS -NOV 2020
COMPUTER ORGANIZATION
Date of Examination: 01-02-2021 Max Time: 90 Mins Max Marks: 10
Name of the Course Coordinator: Section: I.T
Answer all the following questions
Question No. 1. 2. 3.
Mapped with CO CO-1 CO-2 CO-3

1. Explain insertion and deletion in a binary search tree (BST) with examples. [4M]
2. Explain the working of Quick Sort with an example. [4M]
3. Explain the drawback of linear queue?
[2M]

Question No__CourseOutcome__MAPPING __Bloom’s Score

Question No. 1 2 3
Course Outcome CO-1 CO-2 CO-3
Marks allotted (Xi) 4 4 2
Bloom’s Taxonomy level 2 2 2
Bloom’s Taxonomy Score
on a Scale of (1-10) (Si) 6 6 6
Bloom’s Index Score
n

∑ X i∗S i
Blooms Index (BI )= i=1n
∑ Xi
i=1
Where ‘n’ are the number of questions in the Internal test paper / Assignment
‘Xi’ is the marks allocated for the ith question as per the assessment plan
‘Si’ is the score allocated for the ith question as per the Blooms Taxonomy score
24+24+12 60
BI = ------------------------------------------ = ---- = 6
10 10

Remarks of
Blooms Attainment
Code Course Faculty Name module
Index Level
coordinator
6

Note: <4- easy 4-7 moderate >7- difficult

Course Co-ordinator Module Co-ordinator Program Co-ordinator

 DEPARTMENT OF INFORMATION TECHNOLOGY
R19 II B.TECH. I SEM I.T MID-II DESCRIPTIVE EXAMINATIONS -NOV 2020
COMPUTER ORGANIZATION
Date of Examination: 01-02-2021 Max Time: 90 Mins Max Marks: 10
Name of the Course Coordinator: Section: I.T
Answer all the following questions
Question No. 1. 2. 3.
Mapped with CO CO-1 CO-2 CO-3

1. Explain infix to postfix conversion with an example [2M]

2. Define Binary Tree. List its properties. List different tree traversal methods. [4M]
3. Write and explain Prim’s algorithm for finding MST with an example [4M]

Question No__CourseOutcome__MAPPING __Bloom’s Score

Question No. 1 2 3
Course Outcome CO-1 CO-2 CO-3
Marks allotted (Xi) 2 4 4
Bloom’s Taxonomy level 2 1 2
Bloom’s Taxonomy Score
on a Scale of (1-10) (Si) 7 6 7
Bloom’s Index Score
n

∑ X i∗S i
Blooms Index (BI )= i=1n
∑ Xi
i=1
Where ‘n’ are the number of questions in the Internal test paper / Assignment
‘Xi’ is the marks allocated for the ith question as per the assessment plan
‘Si’ is the score allocated for the ith question as per the Blooms Taxonomy score
14+24+28 66
BI = ------------------------------------------ = ---- = 6.6
10 10

Remarks of
Blooms Attainment
Code Course Faculty Name module
Index Level
coordinator
6.6

Note: <4- easy 4-7 moderate >7- difficult

Course Co-ordinator Module Co-ordinator Program Co-ordinator

MID-II ANSWER SCRIPT
 Branch, Year – Sem:II-I Regulation:R19
Academic year:2022-23 Faculty :

S.NO. ROLL NO. NAME OF THE STUDENT

1 198X1A1201 ANNAPUREDDY VIDYADHARI
2 198X1A1202 AARE AKHILA REDDY
3 198X1A1203 ANNAVARAPU CHANDRA SEKHAR REDDY
4 198X1A1204 BELLI BHAVANI
5 198X1A1205 BHANDHANADHAM ANTONY LOKESH
6 198X1A1206 BOMMU SRAVYA
7 198X1A1207 BOYAPATI VENKATA NARENDRA
8 198X1A1208 BUDATI MEGHANA SAI RAJESWARI
9 198X1A1209 CHANDARLAPATI VENKATA NAGA SUVARNA
10 198X1A1210 CHALLA GOPI
11 198X1A1211 CHALLA MAHESWARI
12 198X1A1212 CHERUKURI SAI SATISH
13 198X1A1213 CHINTA LAHARI
14 198X1A1214 CHINTA SHAMITHA
15 198X1A1215 CHINTHANIPPULA SUMANTH CHOWDARY
16 198X1A1216 CHITTIPROLU VENKATA DEEPTHI
17 198X1A1217 DEVINENI BHARGAVI
18 198X1A1218 DIVVELA UMA NAGA VENKATA BHARATH AKASH
19 198X1A1219 DOMMALAPATI ANUSHA
20 198X1A1220 EATI VAMSI RAMAKRISHNA
21 198X1A1221 GOGADA NIKHIL CHOWDARY
22 198X1A1222 GUDIKANDULA TILAK
23 198X1A1223 GURRAM RUFUS SHAKIN
24 198X1A1224 IMADABATTINI LAKSHMI PRASANNA
25 198X1A1225 IRIGI SRIKANTH
26 198X1A1226 JANGA NAVEEN REDDY
27 198X1A1227 KANKIPATI VENKAT
28 198X1A1228 KARNATI HEMALATHA
29 198X1A1229 KARTHIK CHIRATANAGANDLA
30 198X1A1231 KORRAPROLU VIJAYA BHUMIKA
31 198X1A1232 KUNAPULI VIJAYALAKSHMI APARNA
32 198X1A1233 LIKHITHA BANDLAMUDI
33 198X1A1234 MADIREDDY SATYANARAYANA REDDY
MUVVA SIVA NAGA VENKATA SAI DURGA ADI
34 198X1A1235
BHUVANESWARI
35 198X1A1236 PALAPARTHI GAYATHRI REDDY
36 198X1A1237 PALAVADI VENKAT KRISHNA UDAY VARDHAN
37 198X1A1238 PILLI SRAVANI
38 198X1A1239 RAPOLU GOPI
39 198X1A1240 SADINENI SAI PRIYATHAM
40 198X1A1241 SANE RESHMA
41 198X1A1242 SHAIK AFRID
42 198X1A1243 SHAIK AMEEN BASHA
43 198X1A1244 SHAIK RIYAZ AHMED
44 198X1A1245 TALLAM OMKANTH
45 198X1A1246 TELAGANETI NANDINI
46 198X1A1247 THIYYAGURA VENKATA GAYATRI
47 198X1A1248 UMMANENI MOHAN RAM SUBRAMANYAM
48 198X1A1249 VAKA REETHIKA REDDY
49 198X1A1250 VAMSI KRISHNA REDDY PALAPARTHI
50 198X1A1251 VARRA NAGI REDDY
51 198X1A1252 VINTHA KEERTHI REDDY
52 198X1A1253 VETALADEVUNI SAI PRAVEENA
53 198X1A1254 YADLAPALLI AKSHAYA
54 198X1A1255 YERUVA BALA MARIYA JYOTHI
55 198X1A1256 KANIGELUPULA SREE SWETHA
56 198X1A1257 VAJRALA SRI BINDU
57 198X1A1258 BHUVANAGIRI MARUTHI LALITHA
58 198X1A1259 CHIGURUPATI ANKITHA
59 198X1A1260 BANNARAVURI ESWAR DEV
60 198X1A1261 CHINTHA BHAVANA
61 198X1A1262 JILLELLAMUDI CHANDRA
62 198X1A1263 TIYYAGURA SRI RAM REDDY

Course Coordinator(s)

Module Coordinator Program Coordinator HOD

REMEDIAL CLASSES FOR SLOW LEARNERS

Course Name: COMPUTER ORGANIZATION Course Code:

Branch, Year – Sem : IT,II-I Regulation:R-19
Academic year: Faculty :

S.
Name of the Name of the No. of Studen
N Topics Covered Date
Subject Faculty attended
o.
1 CO Register Transfer
08-02-
Bus and Memory
2021
Transfers
24
Computer 09-02-
Instructions, 2021
Instruction Cycle
Data Representation: 10-02-
24
Data types 2021
Computer 11-02-
Arithmetic: Addition 2021 24
and Subtraction
Register Transfer 12-02- 24
Language and Micro 2021
operations
 Addressing Modes, 13-02-2021
Data Transfer and 24
Manipulation

Module Coordinator Program Coordinator HOD

CLASSES FOR SLOW LEARNERS – ATTENDANCE REPORT

Course Name: B.TECH Course Code:
Branch, Year – Sem : IT,II-I Regulation:R-19
Academic year: Faculty :
Name of the Subject: DATA STRUCTURES

Date 08/02 09/02 10/02 11/02 12/02 13/02

N Name of the
Roll No
Student
ANNAPUREDDY
198X1A1201 1 2 3 4 5 6
VIDYADHARI
BHANDHANADHAM
198X1A1205 1 2 3 4 5 6
ANTONY LOKESH
BOYAPATI VENKATA
198X1A1207 1 2 3 4 5 6
NARENDRA
198X1A1217 DEVINENI BHARGAVI 1 2 3 4 5 6
198X1A1227 KANKIPATI VENKAT 1 2 3 4 5 6
KARTHIK
198X1A1229 1 2 3 4 5 6
CHIRATANAGANDLA
KUNAPULI
198X1A1232 VIJAYALAKSHMI 1 2 3 4 5 6
APARNA
LIKHITHA
198X1A1233 1 2 3 4 5 6
BANDLAMUDI
MADIREDDY
198X1A1234 SATYANARAYANA 1 2 3 4 5 6
REDDY
MUVVA SIVA NAGA
0 198X1A1235 VENKATA SAI DURGA 1 2 3 4 5 6
ADI BHUVANESWARI
PALAVADI VENKAT
1 198X1A1237 KRISHNA UDAY 1 2 3 4 5 6
VARDHAN
2 198X1A1238 PILLI SRAVANI 1 2 3 4 5 6
SADINENI SAI
3 198X1A1240 1 2 3 4 5 6
PRIYATHAM
4 198X1A1241 SANE RESHMA 1 2 3 4 5 6
5 198X1A1242 SHAIK AFRID 1 2 3 4 5 6
6 198X1A1243 SHAIK AMEEN BASHA 1 2 3 4 5 6
7 198X1A1244 SHAIK RIYAZ AHMED 1 2 3 4 5 6
8 198X1A1245 TALLAM OMKANTH 1 2 3 4 5 6
THIYYAGURA
9 198X1A1247 1 2 3 4 5 6
VENKATA GAYATRI
UMMANENI MOHAN
0 198X1A1248 1 2 3 4 5 6
RAM SUBRAMANYAM
VAKA REETHIKA
1 198X1A1249 1 2 3 4 5 6
REDDY
BANNARAVURI
2 198X1A1260 1 2 3 4 5 6
ESWAR DEV
CHINTHA
3 198X1A1261 1 2 3 4 5 6
BHAVANA

Module Coordinator Program Coordinator HOD

 SYLLABUS COVERAGE

Course Name: DATA STRUCTURES Course Code:

Branch, Year – Sem : IT,II-I Regulation:R-19
Academic year: Faculty :

SYLLABUS COVERAGE
Unit Prescribed Covered Remarks
date date
Unit 15-11-2021 17-11-2021
1
Unit 19-12-2021 22-12-2021
2
Unit 23-01-2021 25-01-2021
3
Unit 08-02-2021 10-02-2021
4
Unit 22-02-2021 22-02-2021
5

Module Coordinator Program Coordinator HOD

 PROGRAMMES OFFERED FOR ADVANCED LEARNERS
Course Name: DATA STRUCTURES Course Code:
Branch, Year – Sem : IT,II-I Regulation:R-19
Academic year: 2020-2021 Faculty :

Sl. Programme Duration Date(s)

No.

08-02-2021 to
1 Carrier Guidance 1 week
13-02-2021

Program Coordinator HOD

CLASSES FOR SLOW LEARNERS – ATTENDANCE REPORT

Course Name: DATA STRUCTURES Course Code:
Branch, Year – Sem : IT,II-I Regulation:R-19
Academic year: Faculty :
 TOTA
S NO REGD NO MID-I QUIZ-I A-I TOTAL MID-I QUIZ-I A-II
L
 198X1A120
1 10 3 5 18 10 4 5 19
1
198X1A120
2 7 2 5 14 10 5 5 20
2
198X1A120
3 8 5 5 18 10 3 5 18
3
198X1A120
4 3 5 5 13 10 5 5 20
4
198X1A120
5 10 6 5 21 10 4 5 19
5
198X1A120
6 10 3 5 18 10 5 5 20
6
198X1A120
7 6 3 5 14 9 4 5 18
7
198X1A120
8 10 5 5 20 10 4 5 19
8
198X1A120
9 10 4 5 19 10 2 5 17
9
198X1A121
10 8 3 5 16 9 3 5 17
0
198X1A121
11 10 3 5 18 10 2 5 17
1
198X1A121
12 4 4 5 13 7 3 5 15
2
198X1A121
13 7 3 5 15 6 1 5 12
3
198X1A121
14 7 4 5 16 8 2 5 15
4
198X1A121
15 4 5 5 14 8 3 5 16
5
198X1A121
16 8 2 5 15 9 3 5 17
6
198X1A121
17 0 5 5 10 8 7 5 20
7
198X1A121
18 7 4 5 16 9 4 5 18
8
198X1A121
19 7 4 5 16 10 5 5 20
9
198X1A122
20 6 4 5 15 8 6 5 19
3
198X1A122
21 9 2 5 16 10 3 5 18
4
198X1A122
22 7 5 5 17 9 7 5 21
6
198X1A122
23 7 2 5 14 8 2 5 15
7
198X1A122
24 9 4 5 18 10 6 5 21
8
198X1A122
25 6 1 5 12 8 5 5 18
9
198X1A123
26 8 4 5 17 9 3 5 17
1
198X1A123
27 8 3 5 16 8 4 5 17
2
198X1A123
28 10 2 5 17 10 3 5 18
3
 198X1A123
29 9 3 5 17 10 4 5 19
4
198X1A123
30 8 2 5 15 10 2 5 17
5
198X1A123
31 10 6 5 21 10 3 5 18
6
198X1A123
32 10 3 5 18 10 3 5 18
8
198X1A124
33 6 4 5 15 8 1 5 14
0
198X1A124
34 8 0 4 12 10 3 4 18
1
198X1A124
35 7 4 5 16 10 3 5 18
2
198X1A124
36 7 4 5 16 10 5 5 20
3
198X1A124
37 10 5 5 20 10 2 5 17
4
198X1A124
38 9 4 5 18 9 5 5 19
5
198X1A124
39 10 6 5 21 10 5 5 20
6
198X1A124
40 10 5 5 20 10 5 5 20
7
198X1A124
41 9 6 5 20 10 4 5 19
8
198X1A124
42 8 6 5 19 9 2 5 16
9
198X1A125
43 12 4 5 21 10 4 5 19
0
198X1A125
44 0 0 4 4 8 3 4 16
1
198X1A125
45 10 4 5 19 10 2 5 17
2
198X1A125
46 10 5 5 20 10 3 5 18
3
198X1A125
47 10 4 5 19 8 4 5 17
4
198X1A125
48 10 4 5 19 10 2 5 17
5
198X1A125
49 10 4 5 19 10 6 5 21
6
198X1A125
50 9 3 5 17 10 3 5 18
7
198X1A125
51 9 2 5 16 9 2 5 16
8
198X1A125
52 9 5 5 19 10 2 5 17
9
198X1A126
53 7 1 5 13 8 3 5 16
0
198X1A126
54 10 5 5 20 10 5 5 20
1
198X1A126
55 6 2 5 13 8 3 5 16
2
198X1A126
56 6 4 5 15 6 3 5 14
3
 Module Coordinator Program Coordinator HOD

UNIVERSITY RESULTS – Regular & Revaluation

RESULTS
STLD Results PASS/
NO REGD. NO PASS/FAIL after
CRD FAIL
Grade GP revalutio
3 n
1 198X1A1201 C 6 0 F
2 198X1A1202 C 6 3 P

3 198X1A1203 D 5 3 P

4 198X1A1204 B 7 3 P

5 198X1A1205 C 6 3 P
6 198X1A1206 B 7 3 P
7 198X1A1207 F 0 0 F
8 198X1A1208 B 7 3 P

9 198X1A1209 C 6 3 P

10 198X1A1210 D 5 3 P

11 198X1A1211 F 0 0 F

12 198X1A1212 C 6 3 P

13 198X1A1213 F 0 0 F

14 198X1A1214 D 5 3 P

15 198X1A1215 F 0 0 F

16 198X1A1216 B 7 3 P

17 198X1A1217 C 6 0 F
18 198X1A1218 C 6 3 P

19 198X1A1219 C 6 3 P
20 198X1A1223 C 6 3 P

21 198X1A1224 D 5 3 P

22 198X1A1226 F 0 0 F

23 198X1A1227 F 0 0 F
24 198X1A1228 C 6 3 P

25 198X1A1229 F 0 0 F

26 198X1A1231 C 6 3 P

27 198X1A1232 F 0 0 F
28 198X1A1233 D 5 0 P
29 198X1A1234 D 5 0 P
30 198X1A1235 D 5 0 P
31 198X1A1236 B 7 3 P

32 198X1A1238 D 5 3 P

33 198X1A1240 D 5 3 P

34 198X1A1241 C 6 3 P

35 198X1A1242 F 0 0 F
36 198X1A1243 C 6 3 P
37 198X1A1244 B 7 3 P
38 198X1A1245 F 0 0 F
39 198X1A1246 B 7 3 P
40 198X1A1247 F 0 0 F
41 198X1A1248 B 7 0 F
42 198X1A1249 C 6 3 P
43 198X1A1250 C 6 3 P

44 198X1A1251 F 0 0 F

45 198X1A1252 D 5 3 P

46 198X1A1253 B 7 3 P

47 198X1A1254 C 6 3 P

48 198X1A1255 F 0 0 F

49 198X1A1256 B 7 3 P

50 198X1A1257 C 6 3 P

51 198X1A1258 C 6 3 P

52 198X1A1259 C 6 3 P

53 198X1A1260 D 5 3 P

54 198X1A1261 S 9 3 P

55 198X1A1262 C 6 3 P

56 198X1A1263 F 0 0 F
 Course Coordinator(s)

Module Coordinator Program Coordinator HOD

COURSE CLOSURE REPORT

Name of the Course Coordinator
Course Code
Course Title
Class Year/Sem
Academic Year
Contact Hours
No. of Students

University Results:
Pass % of Students
% Average Marks
Minimum / Maximum
marks

A. Course Outcome Attainments – Targets

Sl. No Description Too C Targ Attainmen Remarks

ls O ets ts
1 Internal 1 3 0
Assessment 2 3 0
Qui 3 3 0
z 4 3
5 3
6 3
1 3 2
2 3 3
Des 3 3 3
crip 4 3 3
tive 5 3 2
6 3 2
1 3 3
2 3 3
Assi 3 3 3
gn 4 3 3
me 5 3 3
nt 6 3 3
2 External Uni 1- 3 2.75
Assessment vers 6
ity
exa
min
atio
 ns
3 Indirect Cou 1- 3 2.83
Assessment rse 6
Exit
Sur
vey

B. Action Taken to Improve the Performance in the current Semester (based on the course closure report in
the previous AY):

C. The student performance has been consistently poor with respect to some COs. Analysis of answer
scripts, exit survey and interaction with the students revealed that this could be attributed to:

D. Course Outcome – Suggestions - Justification

Sl. Current COs Modified COs - Suggestive

No
1 Principles and the
Implementation of Computer Nil
Arithmetic
2 Operation of CPUs Nil
 including RTL, ALU,
Instruction Cycle and Busses
3 Fundamentals of different
Instruction Set Architectures
Nil
and their relationship to the
CPU Design
4 Memory System and I/O
Organization Nil

5 Principles of Operation of
Multiprocessor Systems and
Nil
Pipelining

E. Mapping of COs (Modified) with POs – Suggestive and Justification

F. Action proposed to Improve the Performance:

Course Coordinator Module Coordinator

Program Coordinator

UNITWISE MATERIALS
UNIT-1
Unit – I
Syllabus:
• Data Structures - Definition, Classification of Data Structures, Operations on Data Structures, Abstract Data
Type (ADT), Preliminaries of algorithms. Time and Space complexity.
• Searching - Linear search, Binary search, Fibonacci search.
• Sorting- Insertion sort, Selection sort, Exchange (Bubble sort, quick sort), distribution (radix sort), merging
(Merge sort) algorithms.

INTRODUCTION:
 A data structure is a particular way of storing and organizing data in a computer so that it can be
used efficiently.
 Some common examples of data structures are arrays, linked lists, queues, stacks, binary trees, and
hash tables
 Today computer programmers do not write programs just to solve a problem but to write an
efficient program.
 When selecting a data structure to solve a problem, the following steps must be performed.
1. Analysis of the problem to determine the basic operations that must be supported.
2. Quantify the resource constraints for each operation.
3. Select the data structure that best meets these requirements.

 The term data means a value or set of values. It specifies either the value of a variable or a constant
(e.g., marks of students, name of an employee, address of a customer, value of pi, etc.).
 A record is a collection of data items. For example, the name, address, course, and marks obtained
are individual data items. But all these data items can be grouped together to form a record.
 A file is a collection of related records. For example, if there are 60 students in a class, then there are
60 records of the students. All these related records are stored in a file.

CLASSIFICATION OF DATA STRUCTURES:

 Data structures are generally categorized into two classes: primitive and non-primitive data
structures.
Primitive and Non-primitive Data Structures:
 Primitive data structures are the fundamental data
types which are supported by a programming
language. Some basic data types are integer, real,
character, and boolean. The terms ‘data type, basic
data type’, and ‘primitive data type’ are often used
interchangeably.
 Non-primitive data structures are those data structures which are created using primitive data
structures. Examples of such data structures include linked lists, stacks, trees, and graphs.
 Non-primitive data structures can further be classified into two categories: linear and non-linear
data structures.

Linear and Non-linear Structures:

 If the elements of a data structure are stored in a linear or sequential order, then it is a linear data
structure.
o Examples include arrays, linked lists, stacks, and queues.
o Linear data structures can be represented in memory in two different ways. One way is to have to a
linear relationship between elements by means of sequential memory locations. The other way is to
have a linear relationship between elements by means of links.

 If the elements of a data structure are not stored in a sequential order, then it is a non-linear data
structure.
o The relationship of adjacency is not maintained between elements of a non-linear data structure.
Examples include trees and graphs.

Arrays:
 An array is a collection of similar data elements. These data elements have the same data type. The
elements of the array are stored in consecutive memory locations and are referenced by an index
(also known as the subscript).
 In C, arrays are declared using the following syntax: datatype name[size];
Ex: int marks[10];

limitations:
o Arrays are of fixed size.
o Data elements are stored in contiguous memory locations which may not be always available.
o Insertion and deletion of elements can be problematic because of shifting of elements from their
positions.
 Linked Lists:
 linked list is a dynamic data structure in which elements (called nodes) form a sequential list.
 In a linked list, each node is allocated space as it is added to the list. Every node in the list points to
the next node in the list.
 Every node contains the following
The value of the node or any other data that corresponds to that node A pointer or
link to the next node in the list

 The first node in the list is pointed by Head/Start/First. The last node in the list contains a NULL
pointer to indicate that it is the end or tail of the list.
Advantage: Easier to insert or delete data elements
Disadvantage: Slow search operation and requires more memory space

Stacks:
 A stack is a linear data structure in which insertion and deletion of elements are done at only one
end, which is known as the top of the stack.
 Stack is called a last-in, first-out (LIFO) structure
because the last element which is added to the
stack is the first element which is deleted from
the stack.
 Stacks can be implemented using arrays or
linked lists.
 Every stack has a variable top associated with
it. Top is used to store the address of the
topmost element of the stack.
 It is this position from where the element will be added or deleted. There is another variable MAX,
which is used to store the maximum number of elements that the stack can store.
 If top = NULL, then it indicates that the stack is empty and if top = MAX–1, then the stack is full.
 A stack supports three basic operations: push, pop, and peep. The push operation adds an element
to the top of the stack. The pop operation removes the element from the top of the stack. And the
peep operation returns the value of the topmost element of the stack (without deleting it).
 Queues:
 A Queue is a linear data structure in which insertion can be done at rear end and deletion of
elements can be dome at front end.
 A queue is a first-in, first-out (FIFO) data
structure in which the element that is inserted
first is the first one to be taken out.
 Like stacks, queues can be implemented by using either arrays or linked lists.

Insert element into the Queue:

Delete element from Queue:

 A queue is full when rear = MAX – 1, An underflow condition occurs when we try to delete an
element from a queue that is already empty. If front = NULL and rear = NULL, then there is no
element in the queue.

Trees:
 A tree is a non-linear data structure which consists of a collection of nodes arranged in a
hierarchical order.
 One of the nodes is designated as the root node, and the remaining nodes can be partitioned into
disjoint sets such that each set is a sub-tree of the root
 The simplest form of a tree is a binary tree. A binary tree consists
of a root node and left and right sub-trees, where both sub-trees
are also binary trees.
 Each node contains a data element, a left pointer which points to
the left sub-tree, and a right pointer which points to the right sub-
tree.
 The root element is the topmost node which is pointed by a ‘root’
pointer. If root = NULL then the tree is empty.
 Here R is the root node and T1 and T2 are the left and right subtrees of R. If T1 is non-empty, then T1
is said to be the left successor of R. Likewise, if T2 is non-empty, then it is called the right successor
of R.
Advantage: Provides quick search, insert, and delete operations
Disadvantage: Complicated deletion algorithm

Graphs:
 A graph is a non-linear data structure which is a collection of vertices (also called nodes) and
edges that connect these vertices.
 A node in the graph may represent a city and the edges connecting the
nodes can represent roads.
 A graph can also be used to represent a computer network where the
nodes are workstations and the edges are the network connections.
 Graphs do not have any root node. Rather, every node in the graph can be connected with every
another node in the graph.
Advantage: Best models real-world situations
Disadvantage: Some algorithms are slow and very complex

OPERATIONS ON DATA STRUCTURES:

 This section discusses the different operations that can be performed on the various data structures
previously mentioned.
 Traversing It means to access each data item exactly once so that it can be processed. For example, to
print the names of all the students in a class.
 Searching It is used to find the location of one or more data items that satisfy the given constraint.
Such a data item may or may not be present in the given collection of data items. For example, to
find the names of all the students who secured 100 marks in mathematics.
 Inserting It is used to add new data items to the given list of data items. For example, to add the
details of a new student who has recently joined the course.
 Deleting It means to remove (delete) a particular data item from the given collection of data items.
For example, to delete the name of a student who has left the course.
 Sorting Data items can be arranged in some order like ascending order or descending order
depending on the type of application. For example, arranging the names of students in a class in an
alphabetical order, or calculating the top three winners by arranging the participants’ scores in
descending order and then extracting the top three.
 Merging Lists of two sorted data items can be combined to form a single list of sorted data items.
 ABSTRACT DATA TYPE:

 An abstract data type (ADT) is a data structure, focusing on what it does and ignoring how it does its
job. (or) 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.
 Ex: stacks ADT and queues ADT. the user is
concerned only with the type of data and the
operations that can be performed on it.
 We can implement both these ADTs using an
array or a linked list.
Advantage of using ADTs
 Modification of a program is simple, For example, if you want to add a new field to a student’s
record to keep track of more information about each student, then it will be better to replace an
array with a linked structure to improve the program’s efficiency.
 In such a scenario, rewriting every procedure that uses the changed structure is not desirable.
Therefore, a better alternative is to separate the use of a data structure from the details of its
implementation.

PRELIMINARIES OF ALGORITHM:

 Algorithm is step by step logical procedure for solving a problem.

 In Algorithm each step is called Instruction.
 An Algorithm is any well-defined computational procedure that take some values as inputs and
produce some values as output.
 An Algorithm is a sequence of computational steps that transform input into output.
 An Algorithm has 5 basic properties:
1. Input:An Algorithm has take ‘0’ or more number of inputs that can be supplied as externally.
2. Output: An Algorithm must produce at least one output.
3. Definiteness: Each instruction in the algorithm must be clear.
4. Finiteness: An algorithm must terminate after a finite number of steps.
5. Effectiveness: Each operation should be effective. i.e the operations must be terminate after finite
amount of time.
Structure of an Algorithm:
1. Algorithm is a procedure consisting of heading and body. In body part we are writing
statements and in the head part we are writing the following.
Syntax: Algorithm name_of_Algo (param1,param2, …);
 2. The beginning and ending of block should be indicated by ‘{‘ and ‘}’ or ‘start’ and ‘end’ respectively.
3. Every statement in the algorithm should be end with semicolon (;).
4. Single line comments are
written using ‘//’ as
beginning of comments.
5. The identifier should
begin with character and
it may be combination of
alpha numeric.
6. Assignment operator (:=) we can use as follows Variable :=
expression (or) value;
7. There are other type of operators such as Boolean operators (TRUE/FALSE), logical operators
(AND,OR,NOT) and relational operators (<,>,<=,>=,…..)
8. The input and output we can write it as read and print respectively.
The Array index are stored with in [ ] brackets. The index of array starts from ‘0’ to ‘N-1’. Syntax:
datatype Aray_name[size];
10. The conditional statements such as if-then (or) if-then-else are written as follows.
if(condition) then statements;
if(condition) then statements;
else
statements;

TIME AND SPACE COMPLEXITY:

 The efficiency of an algorithm can be computed by measuring the performance of an algorithm. We

can measure the performance of an algorithm in Two(2) ways.
1. Time Complexity
2. Space Complexity

1. Time Complexity:
 The time complexity of an algorithm is the amount of computing time required by an algorithm to
run its completion.
 There are 2 types of computing time 1. Compile time 2. Run time
  The time complexity generally computed at run time (or) execution time.
 The time complexity can be calculated in terms of frequency count.
 Frequency count is a count denoting the number of times the statement should be executed.
 The time complexity can be calculated as
Comments – 0
Assignment / return statement – 1 Conditional (or)
Selection Constructs – 1

Example 1: Sum of the elements in an Array

Statements Step count/ Frequency Total Steps
Execution
Algorithm Addition (A,n) 0 - 0
{ 0 - 0
//A is an array of size ‘n’ 0 - 0
Sum :=0; 1 1 1
for i:=1 to n do 1 n+1 n+1
Sum:=Sum+A[i]; 1 n n
return Sum; 1 1 1
} 0 - 0
Total 2n+3

Example 2: Subtraction of two matrices

Statements Step count/ Frequency Total Steps
Execution
Algorithm Subtract (A,B,C,m,n) 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
Total 2mn+2m+1

2. Space Complexity:
 Space Complexity can be defined as amount of memory (or) space required by an Algorithm to run.
 To compute the space complexity we use 2 factors i. Constant ii. Instance characteristics.
 The space requirement S(p) can be given as S(p) = C+Sp
Where C- Constant, it denotes the space taken for input and output. Sp – Amount
of space taken by an instruction, variable and identifiers.
 Example 1: Sum of three numbers
Algorithm Add(a,b,c)
{
//a,b,c are float type variables return a+b+c;
}
 The space required for this algorithm is: Assume a,b,c are occupies 1 word size each, total size comes
to be 3.

Example 2: Sum of Array values

Algorithm Addition (A,n)
{
//A is an array of size ‘n’ Sum :=0;
for i:=1 to n do Sum:=Sum+A[i];
return Sum;
}
 The space required for this algorithm is:
One word space for each variable then i,sum,n  3 For Array A[ ]
we require the size  n
Total space complexity for this algorithm is S(p) ≥ (n+3)

What to Analyze in an algorithm:

An Algorithm can require different times to solve different problems of same size
1. Worst case: Maximum amount of time that an algorithm require to solve a problem of size ‘n’.
Normally we can take upper bound as complexity. We try to find worst case behavior.
2. Best case: Minimum amount of time that an algorithm require to solve a problem of size ‘n’.
Normally it is not much useful.
3. Average case: the average amount of time that an algorithm require to solve a problem of size ‘n’.
Some times it is difficult to find. Because we have to check all possible data organizations

SEARCHING:

 Searching means to find whether a particular value is present in an array or not.

 If the value is present in the array, then searching is said to be successful and the searching process
gives the location of that value in the array.
 However, if the value is not present in the array, the searching process displays an appropriate
message and in this case searching is said to be unsuccessful.
 Searching techniques are linear search, binary search and Fibonacci Search
 LINEAR SEARCH:

 Linear search is a technique which traverse the array sequentially to locate given item or search
element.
 In Linear search, we access each element of an array one by one sequentially and see weather it is
desired element or not. We traverse the entire list and match each element of the list with the item
whose location is to be found. If the match found then location of the item is returned otherwise the
algorithm return NULL.
 A search is successful then it will return the location of desired element
 If A search will unsuccessful if all the elements are accessed and desired element not found.
 Linear search is mostly used to search an unordered list in which the items are not
sorted. Linear search is implemented using following steps...
Step 1 - Read the search element from the user.
Step 2 - Compare the search element with the first element in the list.
Step 3 - If both are matched, then display "Given element is found!!!" and terminate the function
Step 4 - If both are not matched, then compare search element with the next element in the list. Step
5 - Repeat steps 3 and 4 until search element is compared with last element in the list.
Step 6 - If last element in the list also doesn't match, then display "Element is not found!!!" and
terminate the function.
Example:
Consider the following list of elements and the element to be searched...
 BINARY SEARCH:

• Binary search is the search technique which works efficiently on the sorted lists. Hence, in order to
search an element into some list by using binary search technique, we must ensure that the list is
sorted.
• Binary search follows divide and conquer approach in which, the list is divided into two halves and
the item is compared with the middle element of the list. If the match is found then, the location of
middle element is returned otherwise, we search into either of the halves depending upon the result
produced through the match.
Algorithm:
Step 1 - Read the search element from the user.
Step 2 - Find the middle element in the sorted list.
Step 3 - Compare the search element with the middle element in the sorted list.
Step 4 - If both are matched, then display "Given element is found!!!" and terminate the function.
Step 5 - If both are not matched, then check whether the search element is smaller or larger than the
middle element.
Step 6 - If the search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for the left
sublist of the middle element.
Step 7 - If the search element is larger than middle element, repeat steps 2, 3, 4 and 5 for the right
sublist of the middle element.
Step 8 - Repeat the same process until we find the search element in the list or until sublist contains
only one element.
Step 9 - If that element also doesn't match with the search element, then display "Element is not found
in the list!!!" and terminate the function.

Example:
Example 2:
 FIBONACCI SEARCH:

 Fibonacci search is an efficient search algorithm based on divide and conquer principle that can find
an element in the given sorted array with the help of Fibonacci series in O(log N) time complexity.
This is based on Fibonacci series which is an infinite sequence of numbers denoting a pattern which is
captured by the following equation:

F(n)=n if n<=1
F(n)=F(n-1)+F(n-2) if n>1
o where F(i) is the ith number of the Fibonacci series where F(0) and F(1) are defined as 0 and 1
respectively.
 The first few Fibonacci numbers are: 0,1,1,2,3,5,8,13....
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1 F(3) = F(2) +
F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 1 + 2 = 3 and so continues the series
 Other searches like binary search also work for the similar principle on splitting the search space to a
smaller space but what makes Fibonacci search different is that it divides the array in unequal parts
and operations involved in this search are addition and subtraction these arithmetic operations
takes place simple and hence reducing the work load of the computing machine.

Algorithm:
 Let the length of given array be n [0...n-1] and the element to be searched be x.
 Then we use the following steps to find the element with minimum steps:
1. Find the smallest Fibonacci number greater than or equal to n. Let this number be f(M)
Let the two Fibonacci numbers preceding it be f(M-1) and f(M-2). F(M) =
F(Size of array)
F(M-1) = F(M) - 1
F(M-2) = F(M-1) -1
i (index) = min (offset + F(M-2) , n-1) //Offset = -1
2. While the array has elements to be checked:
-> Compare x with the last element of the range covered by f(M-2)
-> If x matches, return index value
-> Else if x is less than the element, move the three Fibonacci variables two Fibonacci down,
Indicating removal of approximately two-third of the unsearched array from rear end. Not Reset offset
to index
 -> Else x is greater than the element, move the three Fibonacci variables one Fibonacci down. Reset
offset to index. Indicating removal of approximately one-third of the unsearched array from front end.
3. Since there might be a single element remaining for comparison, check if F(M-1) is '1'. If Yes,
compare x with that remaining element. If match, return index value.

Example: The Elements in array & Search key is

Search_K 8
ey 5
elements 1 2 3 4 4 5 8 8 8 9 9
0 2 5 0 5 0 0 2 5 0 5
Index 0 1 2 3 4 5 6 7 8 9 1
0
Initially the Fibonacci series is …
0 1 1 2 3 5 8 13 2 3
1 4
1 2 3 4 5 6 7 8 9 1
0
F(m- F( F(m-
2) m 1)
)
To calculate index position i = min(offset+F(m-2), n-1), Initially offset value is -1.
F( F(m- F(m- Offs i(index) a[i] Consequence
m) 1) 2) et
13 8 5 -1 (-1+5,10) = 45 1 steps down, Reset offset
4
8 5 3 4 (4+3, 82 1 steps down, Reset offset
10)=7
5 3 2 7 (7+2, 10) 90 2 steps down
=9
2 1 1 7 (7+1, 10) = 85 Return i
8
Finally our desired element is found at the location of 8.

SORTINGS:

 Definition: Sorting is a technique to rearrange the list of records(elements) either in ascending or

descending order, Sorting is performed according to some key value of each record.

Categories of Sorting:
The sorting can be divided into two categories. These are:
 Internal Sorting
 External Sorting
 Internal Sorting: When all the data that is to be sorted can be accommodated at a time in the main
memory (Usually RAM). Internal sortings has five different classifications: insertion, selection,
exchanging, merging, and distribution sort
 External Sorting: When all the data that is to be sorted can’t be accommodated in the memory
(Usually RAM) at the same time and some have to be kept in auxiliary memory such as hard disk,
floppy disk, magnetic tapes etc.
Ex: Natural, Balanced, and Polyphase.

INSERTION SORT:

 In Insertion sort the list can be divided into two parts, one is sorted list and other is unsorted list. In
each pass the first element of unsorted list is transfers to sorted list by inserting it in appropriate
position or proper place.
 The similarity can be understood from the style
we arrange a deck of cards. This sort works on
the principle of inserting an element at a
particular position, hence the name Insertion
Sort.
Following are the steps involved in insertion sort:
1. We start by taking the second element of the given array, i.e. element at index 1, the key. The
key element here is the new card that we need to add to our existing sorted set of cards
2. We compare the key element with the element(s) before it, in this case, element at index 0:
o If the key element is less than the first element, we insert the key element before the first element.
o If the key element is greater than the first element, then we insert it after the first element.
3. Then, we make the third element of the array as key and will compare it with elements to it's left
and insert it at the proper position.
4. And we go on repeating this, until the array is sorted.

Example 1:
 Example 2:

SELECTION SORT:

 Given a list of data to be sorted, we simply select the smallest item and place it in a sorted list. These
steps are then repeated until we have sorted all of the data.
 In first step, the smallest element is search in the list, once the smallest element is found, it is
exchanged with the element in the first position.
 Now the list is divided into two parts. One is
sorted list other is unsorted list. Find out the
smallest element in the unsorted list and it is
exchange with the starting position of
unsorted list, after that it will added in to
sorted list.
 This process is repeated until all the elements are
sorted. Ex: asked to sort a list on paper.
Algorithm:
SELECTION SORT(ARR, N)
Step 1: Repeat Steps 2 and 3 for K = 1 to N-1 Step 2: CALL
SMALLEST(ARR, K, N, Loc)
Step 3: SWAP A[K] with ARR[Loc] Step 4: EXIT
Algorithm for finding minimum element in the list.
SMALLEST (ARR, K, N, Loc)
Step 1: [INITIALIZE] SET Min = ARR[K] Step 2:
[INITIALIZE] SET Loc = K
Step 3: Repeat for J = K+1 to N
IF Min > ARR[J]
SET Min = ARR[J]
SET Loc = J [END OF IF]
[END OF LOOP]
Step 4: RETURN Loc

Example 1:
 Example 2: Consider the elements 23,78,45,88,32,56

Time Complexity:
Number of elements in an array is ‘N’ Number of
passes required to sort is ‘N-1’
Number of comparisons in each pass is 1st pass N-1, 2nd Pass N-2 … Time required
for complete sorting is:
T(n) <= (N-1)*(N-1) T(n) <= (N-1)2
Finally, The time complexity is O(n2).

BUBBLE SORT:

 Bubble Sort is also called as Exchange Sort

 In Bubble Sort, each element is compared with its adjacent element
a) If he first element is larger than the second element then the position of the elements are
interchanged.
b) Otherwise, the position of the elements are not changed.
c) The same procedure is repeated until no more elements are left for comparison.
 After the 1st pass the largest element is placed at
(N-1)th location. Given a list of n elements, the
bubble sort requires up to n – 1 passes to sort the
data.

Example 1:
 We take an unsorted array for our example.
 Bubble sort starts with very first two elements, comparing them to check which one is greater.

 In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33
with 27. We find that 27 is smaller than 33 and these two values must be swapped.

 Next we compare 33 and 35. We find that both are in already sorted positions.

 Then we move to the next two values, 35 and 10. We know then that 10 is smaller 35.

 We swap these values. We find that we have reached the end of the array. After one iteration, the
array should look like this −

 To be defined, we are now showing how an array should look like after each iteration. After the
second iteration, it should look like this

 Notice that after each iteration, at least one value moves at the end.

 And when there's no swap required, bubble sorts learns that an array is completely sorted.

Example 2:
 Algorithm:
BUBBLE SORT(ARR, N)
Step 1: Read the array elements Step
2: i:=0;
Step 3: Repeat step 4 and step 5 until i<n Step
4: j:=0;
Step 5: Repeat step 6 until j<(n-1)-i Step 6:
if A[j] > A[j+1]
Swap(A[j],A[j+1])
End if
End loop 5
End loop 3
Step 7: EXIT

Time Complexity:
Number of elements in an array is ‘N’ Number of
passes required to sort is ‘N-1’
Number of comparisons in each pass is 1st pass N-1, 2nd Pass N-2 … Time required
for complete sorting is:
T(n) <= (N-1)*(N-1) T(n) <= (N-1)2
Finally, The time complexity is O(n2).

QUICK SORT:

 Quick sort follows Divide and Conquer algorithm. It is dividing array in to smaller parts based on
partitioning and performing the sort operations on those divided smaller parts. Hence, it works well
for large datasets.
So, here are the steps how Quick sort works in simple words.
1. First select an element which is to be called as pivot element.
2. Next, compare all array elements with the selected pivot element and arrange them in such a way
that, elements less than the pivot element are to its left and greater than pivot is to it's right.
3. Finally, perform the same operations on left and right side elements to the pivot element.
How does Quick Sort Partitioning Work
1. First find the "pivot" element in the array.
2. Start the left pointer at first element of the array.
3. Start the right pointer at last element of the array.
4. Compare the element pointing with left pointer and if it is less than the pivot element, then move
the left pointer to the right (add 1 to the left index). Continue this until left side element is greater
than or equal to the pivot element.
5. Compare the element pointing with right pointer and if it is greater than the pivot element, then
move the right pointer to the left (subtract 1 to the right index). Continue this until right side
element is less than or equal to the pivot element.
6. Check if left pointer is less than or equal to right pointer, then swap the elements in locations of
these pointers.
7. Check if index of left pointer is greater than the index of the right pointer, then swap pivot element
with right pointer.

Example:

Algorithm:
quickSort(array, lb, ub)
{
if(lb< ub)
{
pivotIndex = partition(arr, lb, ub);
quickSort(arr, lb, pIndex - 1);
quickSort(arr, pivotIndex+1, ub);
}
}
 RADIX SORT:

 Radix sort is a linear sorting algorithm for integers and uses the concept of sorting names in
alphabetical order. When we have a list of sorted names, the radix is 26 (or 26 buckets) because
there are 26 letters in the English alphabet. So radix sort is also known as bucket sort.
 Observe that words are first sorted according to the first letter of the name. That is, 26 classes are
used to arrange the names, where the first class stores the names that begin with A, the second class
contains the names with B, and so on.
 During the second pass, names are grouped according to the second letter. After the second pass,
names are sorted on the first two letters. This process is continued till the nth pass, where n is the
length of the name with maximum number of letters.
 When radix sort is used on integers, sorting is done on each of the digits in the number. The sorting
procedure proceeds by sorting the least significant (LSD) to the most significant (MSD) digit. While
sorting the numbers, we have ten buckets, each for one digit (0, 1, 2, …, 9) and the number of passes
will depend on the length of the number having maximum number of digits.
ample 1: Sort the numbers given below using radix sort. 345, 654,
924, 123, 567, 472, 555, 808, 911
 In the first pass, the numbers are sorted according to the digit at ones place.

 After this pass, the numbers are collected bucket by bucket. In the second pass, the numbers are
sorted according to the digit at the tens place.
 In the third pass, the numbers are sorted according to the digit at the hundreds place.
 The numbers are collected bucket by bucket. After the third pass, the list can be given as final
sorted list. 123, 345, 472, 555, 567, 654, 808, 911, 924.

Algorithm:

1. Let A be a linear array of n elements A[1], A[2], A[3]......................A[n]. Digit is the total number of digit in
the largest element in array A.
2. Input n number of elements in an array A.
3. Find the total number of digits in the largest element in the array.
4. Initialize i=1 and repeat the steps 4 and 5 until( i<=Digit).
5. Initialize the bucket j=0 and repeat the steps 5until (j<n).
6. Compare the ith position of each element of the array with bucket number and place it in the
corresponding bucket.
7. Read the elements (S) of the bucket from 0th bucket to 9th bucket and from the first position to the higher
one to generate new array A.
8. Display the sorted array A.
9. Exit.

Divide and Conquer:

 Divide and Conquer is an algorithmic pattern. In algorithmic methods, the design is to take a dispute
on a huge input, break the input into minor pieces, decide the problem on each of the small pieces,
and then merge the piecewise solutions into a global solution. This mechanism of solving the
problem is called the Divide & Conquer Strategy.
 Divide and Conquer algorithm consists of a dispute using the
following three steps.
1. Divide the original problem into a set of sub-problems.
2. Conquer: Solve every sub-problem individually, recursively.
3. Combine: Put together the solutions of the sub-problems to
get the solution to the whole problem.

MERGE SORT:

Merge sort is one of the most efficient sorting algorithms. It works on the principle of Divide and
Conquer. Merge sort repeatedly breaks down a list into several sublists until each sublist consists of a
single element and merging those sublists in a manner that results into a sorted list.
 Implementation Recursive Merge Sort:
 The merge sort starts at the Top and proceeds downwards, “split the array into two, make a
recursive call, and merge the results.”, until one gets to the bottom of the array-tree.
Example: Let us consider an example to understand the approach better.
1. Divide the unsorted list into n sub-lists based on mid value, each array consisting 1 element
2. Repeatedly merge sub-lists to produce newly sorted sub-lists until there is only 1 sub-list
remaining. This will be the sorted list
Recursive Mere Sort Example:

Example 2:

MergeSort Algoritm:
MergeSort(A, lb, ub )
{
If lb<ub
{
mid = floor(lb+ub)/2; mergeSort(A, lb, mid)
mergeSort(A, mid+1, ub) merge(A, lb, ub ,
mid)
}
}
Two- Way Merge Sort:

Merge Algorithm:
Step 1: set i,j,k=0
Step 2: if A[i]<B[j] then
copy A[i] to C[k] and increment i and k
else
copy B[j] to C[k] and increment j and k
Step 3: copy remaining elements of either A or B into Array C.
Time Complexities All the Searching & Sorting Techniques:

www.Jntufastupdates.c 1
om
 UNIT-II

www.Jntufastupdates.c 2
om
www.Jntufastupdates.c 3
om
www.Jntufastupdates.c 4
om
www.Jntufastupdates.c 5
om
www.Jntufastupdates.c 6
om
www.Jntufastupdates.c 7
om
www.Jntufastupdates.c 8
om
www.Jntufastupdates.c 9
om
www.Jntufastupdates.c 10
om
www.Jntufastupdates.c 11
om
www.Jntufastupdates.c 12
om
www.Jntufastupdates.c 13
om
www.Jntufastupdates.c 14
om
www.Jntufastupdates.c 15
om
www.Jntufastupdates.c 16
om
www.Jntufastupdates.c 17
om
www.Jntufastupdates.c 18
om
www.Jntufastupdates.c 19
om
www.Jntufastupdates.c 20
om
www.Jntufastupdates.c 21
om
www.Jntufastupdates.c 22
om
www.Jntufastupdates.c 23
om
www.Jntufastupdates.c 24
om
www.Jntufastupdates.c 25
om
 Unit – III
Syllabus:
• Queues: Introduction to Queues, Representation of Queues-using Arrays and using Linked list,
Implementation of Queues-using Arrays and using Linked list, Application of Queues-Circular Queues,
Deques, Priority Queues, Multiple Queues.
• Stacks: Introduction to Stacks, Array Representation of Stacks, Operations on Stacks, Linked list
Representation of Stacks, Operations on Linked Stack, Applications-Reversing list, Factorial Calculation, Infix
to Postfix Conversion, Evaluating Postfix Expressions.

QUEUE:

● Queue is a linear data structure in which elements can be

inserted from one end called rear and deleted from other
end called front.

● The deletion or insertion of elements can take place only at the front or rear end called dequeue
and enqueue respectively. The first element that gets added into the queue is the first one to get
removed from the queue. Hence the queue is referred to as First-In- First-Out list (FIFO).

Operations performed on Queue:

There are two possible operations performed on a queue. They are

✔ enqueue: Allows inserting an element at the rear of the queue.

✔ dequeue: Allows removing an element from the front of the queue.

REPRESENTATION OF QUEUEs:

ARRAYs: Queues can be easily represented

using linear arrays. Every queue has front and
rear variables that point to the position from
where deletions and insertions can be done,
respectively. The array representation of a
queue is shown
Drawback: The array must be declared to
have some fixed size. If we allocate space

www.Jntufastupdates.c 26
om
 for 50 elements in the queue and it hardly uses 20–25 locations, then half of the space will be wasted.

LINKED LISTs:

 In a linked queue, every element has two parts, one that stores the data and another that stores
the address of the next element.
 The START pointer of the linked list is used as FRONT. Here, we will also use another pointer
called REAR, which will store the address of the last element in the queue. All insertions will be
done at the rear end and all the deletions will be done at the front end.
 If FRONT = REAR = NULL, then it indicates that the queue is empty.

IMPLEMENTATION OF QUEUEs:

Using Arrays:
Algorithm for ENQUEUE operation
1. Check whether queue is FULL. (rear >= SIZE-1)
2. If it is FULL, then display an error message "Queue is FULL!!! Insertion is not possible!!!" and
terminate the function.
3. If it is NOT FULL, then increment rear value by one (rear++) and set queue[rear]
= value.

Algorithm for DEQUEUE operation

1. Check whether queue is EMPTY. (front == -1)
2. If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate the
function.
3. If it is NOT EMPTY, then display queue[front] as deleted element, increment the front value
by one (front ++). If we are deleting last element both front and rear are equal (front == rear), then
set both front and rear to '-1' (front = rear = -1).

Implementation:

www.Jntufastupdates.c 27
om
 Let us consider a queue, which can hold maximum
of five elements.
 Initially the queue is empty. An element can be added to
the queue only at the rear end of the queue.
 Before adding an element in the queue, it is checked
whether queue is full. If the queue is full, then addition
cannot take place. Otherwise, the element is added to the
end of the list at the
rear end. If
we are inserting first element into the queue then change front to 0 (Zero).
 Now, delete an element 1. The
element deleted is the element at the front of the queue. So the status of the queue is:
 When the last element delete 5.
The element deleted at the front of the queue. So the status of the queue is empty. So change the
values of front and rear to -1 (front=rear= -1)
 The dequeue operation deletes the element from the front of the queue.
Before deleting and element, it is checked if the queue is empty. If not the element pointed by
front is deleted from the queue and front is now made to point to the next element in the queue.
 Drawback: If we implement the queue using an array, we need to specify the array size at the
beginning (at compile time). We can't change the size of an array at runtime. So, the queue will
only work for a fixed number of elements.

Using Linked List:

 In a linked queue, each node of the queue consists of two parts i.e. data part and the next part. Each
element of the queue points to its immediate next element in the memory.
 In the linked queue, there are two pointers maintained in the
memory i.e. front pointer and rear
pointer. The front pointer contains the address of the
starting element of the queue while the rear pointer
contains the address of the last element of the queue.

www.Jntufastupdates.c 28
om
 Insertion and deletions are performed at rear and front end respectively. If front and rear both are
NULL, it indicates that the queue is empty. Initially

struct node *front = NULL, *rear = NULL;

Operation on Linked Queue: There are two basic operations which can be implemented on the linked
queues. The operations are Enqueue and Dequeue.

Enqueue function: Enqueue function will add the element at the end of the linked list.

1. Declare a new node and allocate memory for it.

2. If front == NULL, make both front and rear points to the new node.

3. Otherwise, add the new node in rear->next (end of the list) and make the new
node as the rear node. i.e. rear = new node

Dequeue function: Dequeue function will remove the first element from the queue.

1. Check whether the queue is empty or not

2. If it is the empty queue (front == NULL), We can't dequeue the element.

3. Otherwise, Make the front node points to the next node. i.e front = front->next; if front

pointer becomes NULL, set the rear pointer also NULL.

Free the front node's memory.

Example: Enqueue()

www.Jntufastupdates.c 29
om
 Dequeue()

TYPES OF QUEUES:
A queue data structure can be classified into the following types:
1. Circular Queue 2. Deque 3. Priority Queue 4. Multiple Queue

CIRCULAR QUEUEs:

 In a Linear queue, once the queue is completely full, it's not possible to insert any more elements.
When we dequeue any element to remove it from the queue, we are actually moving the front of
the queue forward, but rear is still pointing to the last element of the queue, we cannot insert
new elements.
 Circular Queue is also a linear data structure, which follows the principle of FIFO(First In First Out),
but instead of ending the queue at the last position, it again starts from the first position after the
last, hence making the queue behave like a circular data structure.

Operations on Circular Queue: The following are the operations that can be performed
o enQueue(value): This function is used to insert the new value in the Queue. The new element is
always inserted from the rear end.
o deQueue(): This function deletes an element from the Queue. The deletion in a Queue always
takes place from the front end.

Enqueue operation: The steps of enqueue operation are given below:

o First, we will check whether the Queue is full or not.
o Initially the front and rear are set to -1. When we insert the first element in a Queue, front and rear
both are set to 0.
o From 2nd element onwards, When we insert a new element, the rear gets incremented, i.e.,
rear=rear+1.

Queue is not full:

o If rear != max - 1, then rear will be incremented and the new value will be inserted at the rear end
of the queue.
o If front != 0 and rear = max - 1, it means that queue is not full, then set the value of rear to 0 and
insert the new element there.

Queue is full:
o When front ==0 && rear = max-1, which means that front is at the first position of the Queue and
rear is at the last position of the Queue.
o front== rear + 1;
www.Jntufastupdates.c 30
om
 Dequeue Operation: The steps of dequeue operation are given below:
o First, we check whether the Queue is empty or not. If the queue is empty, we cannot perform
the dequeue operation.
o When the element is deleted, the value of front gets decremented by 1.
o If there is only one element left which is to be deleted, then the front and rear are reset -1.

Let's understand the enqueue and dequeue operation through the diagrammatic
representation.

Applications of Queue:
1. Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
2. Queues are used to transfer data asynchronously between two processes
3. Queues are used as buffers on MP3 players and portable CD players, iPod playlist.
4. Queues are used in Playlist for jukebox to add songs to the end, play from the front.
5. Queues are used in operating system for handling interrupts. The interrupts are handled in the same
order as they arrive i.e First come first served.

www.Jntufastupdates.c 31
om
 DEQUE:
Deque or Double Ended Queue is a type of
queue in which insertion and removal of
elements can be performed from either from
the front or rear. Thus, it does not follow FIFO
rule (First In First Out).

Types of Deque:
1. Input Restricted Deque: In this deque, input is restricted at a single end but allows
deletion at both the ends.
2. Output Restricted Deque: In this deque, output is restricted at a single end but allows
insertion at both the ends.

Operations on a Deque
 Initially take an array (deque) of size n. and Set two pointers at the first position and set front = -1
and rear = -1.
1. Insert at the Front: This operation adds an element at the front.
 Check the position of front, If front < 1, we can’t add elements in the front end. Otherwise
decrement the front and at front location we can insert the element.
2. Insert at the Rear: This operation adds an element to the rear.
 Check if the array is full. Then the queue is overflow. Otherwise, reinitialize rear = 0 & front=0 for
the first insertion, Else, increase rear by 1.and at rear location we can insert the element.
3. Delete from the Front: The operation deletes an element from the front.
 Check If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition). If
the deque has only one element (i.e. front = rear), set front = -1 and rear = -1. Else, front = front +
1.
4. Delete from the Rear: This operation deletes an element from the rear.
 If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition). If the
deque has only one element (i.e. front = rear), set front = -1 and rear = -1. Else, rear = rear - 1.

www.Jntufastupdates.c 32
om
 Priority Queue:-

 A priority queue is a data structure in which each element is assigned a priority. The priority of the
element will be used to determine the order in which the elements will be processed.
 The general rules of processing the elements of a priority queue are
o An element with higher priority is processed before an element with a lower priority.
o Two elements with the same priority are processed on a first-come-first-served (FCFS) basis.
Array Representation of a Priority Queue:
 When arrays are used to implement a priority queue, then a separate queue for each priority
number is maintained. Each of these queues will be implemented using circular arrays or circular
queues. Every individual queue will have its own FRONT and REAR pointers.
 We use a two-dimensional array for this purpose where each queue will be allocated the same
amount of space.
 FRONT[P] and REAR[P] contain the front and rear values of row P, where P is the priority number.

Insertion:

 To insert a new element with priority P in the priority queue, add the element at the rear end of row
P, where P is the row number as well as the priority number of that element.
 For example, if we have to insert an element X with priority number 2, then the priority queue will
be given as shown in Fig.

www.Jntufastupdates.c 33
om
 Deletion:
 To delete an element, we find the first nonempty queue and then process the front element of the
first non-empty queue.
 In our priority queue, the first non-empty queue is the one with priority number 6 and the front
element is K, so K will be deleted and processed first.

Multiple Queues:-

 When we implement a queue using an array, the size of the array must be known in advance. If the
queue is allocated less space, then frequent overflow conditions will be encountered. To deal with
this problem, the code will have to be modified to reallocate more space for the array.
 In case we allocate a large amount of space for the queue, it will result in sheer wastage of the
memory. So a better solution to deal with this problem is to have multiple queues or to have more
than one queue in the same array of sufficient size.
 An array Queue[n] is used to represent two queues, Queue A and Queue B. The value of n is such
that the combined size of both the queues will never exceed n. While operating on these queues, it
is important to note one thing—queue A will grow from left to right, whereas queue B will grow
from right to left at the same time.
Example:

 In the above example the array consists two queues like QA and QB. For QA there are pointers
like fA(front of QA) and rA(rear of A). similarly for QB are fB & rB.
 Initially for QA, the pointer values of fA=rA= -1. For QB, the pointer values are fB=rB=SIZE.
Because initially QA and QB are empty.
 For the first insertion in QA, the values of fA=rA=0. Similarly for QB, the values are fB=rB=SIZE-
1.
 From the second insertion onwards we can increment only the rear pointer rA for QA and
decrement the rear rB for QB.
 Delete the elements from queue only at front end. In QA, the elements can delete from fA, if you
delete the element then increment fA. In QB, the elements can delete from fB, if you delete the
element then decrement fB.
 When the condition rA=rB-1 or rA+1=rB meets then the entire queue is full. If you try to insert the
element in either of queues it says that QUEUE is OVERFLOW.

www.Jntufastupdates.c 34
om
 Stack:-

● Stack is a linear data structure in which insertion and deletion can

perform at the same end called top of stack.

● When an item is added to a stack, the operation is called push, and

when an item is removed from the stack the operation is called pop.

● Stack is also called as Last-In-First-Out (LIFO) list which means that the
last element that is inserted will be the first element to be removed
from the stack.
● When a stack is completely full, it is said to be Stack is Overflow and if stack is completely empty, it
is said to be Stack is Underflow.

REPRESENTATION & IMPLEMENTATION STACK:

Array Representation of Stacks:

 Every stack has a variable called TOP associated with it, which is used to pointing the topmost
element of the stack. It is this position where the element will be inserted to or deleted from.
 There is another variable called MAX, which is used to store the maximum number of elements that
the stack can hold.
 If TOP = NULL, then it indicates that the stack is empty and if TOP = MAX–1, then the stack is full.

Array Implementation of Stack:

The basic operations performed in a Stack:

1. Push(x) - add element x at the top of the stack
2. Pop( ) - remove top element from the stack
3. peek() - get top element of the stack without removing it

Algorithm for PUSH operation:

1. Check if the stack is full or not.

2. If the stack is full, then print error of overflow and exit the program.
3. If the stack is not full, then increment the top and add the element at top location.

www.Jntufastupdates.c 35
om
 Algorithm for POP operation

1. Check if the stack is empty or not.

2. If the stack is empty, then print error of underflow and exit the program.
3. If the stack is not empty, then print the element at the top and decrement the top.

Algorithm for PEEK operation

1. Check if the stack is empty or not.

2. If the stack is empty, then print error of underflow and exit the program.
3. If the stack is not empty, then print the element at the top without removing it.

Linked Representation of Stacks:

 The drawback in that the array must be declared to have some fixed size. In case the stack is a very
small one or its maximum size is known in advance
 In a linked stack, every node has two parts, one that stores data and another that stores the
address of the next node. The START pointer of the linked list is used as TOP.
 All insertions and deletions are done at the TOP (similar to insertion at beginning).

www.Jntufastupdates.c 36
om
 If TOP = NULL, then it indicates that the stack is empty.
 The linked representation of a stack is

Linked Implementation of Stack:

 In a linked stack, each node of the stack consists of two parts i.e. data part and the next part. Each
element of the stack points to its immediate next element in the memory.
 In the linked stack, there one pointer maintained in the memory i.e.
TOP pointer. The TOP pointer contains the address of the starting
element of the STACK.
 Both Insertion and deletions are performed at only one end
called TOP. If TOP is NULL, it indicates that the stack is empty. Initially

struct node *TOP = NULL ;

Operation on Linked STACK: There are two basic operations which can be implemented on the
linked queues. The operations are PUSH and POP.

PUSH function: PUSH function will add the element at the beginning of the linked list.
1. Declare a new node and allocate memory for it.
2. If TOP == NULL, make TOP points to the new node.
3. Otherwise, add the new node at TOP end and makes the next of new node is previous TOP.

POP function: POP function will remove the TOP element from the STACK.
1. Check whether the stack is empty or not
2. If it is the stack is empty (TOP == NULL), We can't POP the element.
3. Otherwise, Make the TOP node points to the next node. i.e TOP = TOP->next; Free the
TOP node's memory.

www.Jntufastupdates.c 37
om
 Algorithms:

Applications of Stacks

✔ Stack is used to reversing the given string.

✔ Stack is used to evaluate a postfix expression.
✔ Stack is used to convert an infix expression into postfix/prefix form.
✔ Stack is used to matching the parentheses in an expression.

Reversing list:
A list of numbers or string can be reversed by using the stack, perform the following steps
1. Reading the elements from the array and pushed into the stack.
2. Pop the elements and again stored into the array starting from first index
Algorithm: Example:

Factorial Calculation:

 To find the solution of larger problem, a general method is reduce the larger problem into one or
more sub problems. This process will continuous until the sub problem is finding the solution.
Finally using all the sub problems solutions we will find the solution for the larger problem.

www.Jntufastupdates.c 38
om
 A Recursion is defined as a function that calls itself.
 To understand recursion, let us take an example of calculating factorial of a number.
 To calculate n!, we multiply the number with factorial of the number that is 1 less than that
number. n! = n*(n-1)*(n-2)* ... *2*1
 In other words, n! = n * (n–1)!
 Let us say we need to find the value of 5!
5! = 5 * 4 * 3 * 2 * 1 = 120
 This can be written as 5! = 5 * 4!,
where 4!= 4 * 3!
Therefore, 5! = 5 * 4 * 3!
Similarly, 5! = 5 * 4 * 3 * 2!
Expanding further 5! = 5 * 4 * 3 * 2 * 1!
We know, 1! = 1
 Now if you look at the problem carefully, you can see that we can write a recursive function to
calculate the factorial of a number. Every recursive function must have a base case and a recursive
case. For the factorial function,
Base case is when n = 1, because if n = 1, the result will be 1 as 1! = 1.
Recursive case of the factorial function will call itself but with a smaller value of n, this case
can be given as factorial(n) = n × factorial (n–1)

Evaluation of Expressions:-

● An expression is defined as the combination of operands (variables, constants) and operators

arranged as per the syntax of the language.
● An expression can be represented using three different notations. They are infix, postfix and
prefix notations:

Prefix: An arithmetic expression in which we fix (place) the arithmetic operator before (pre) its two
operands. The prefix notation is called as polish notation. Example: + A B
Infix: An arithmetic expression in which we fix (place) the arithmetic operator in between the two
operands. Example: A + B
Postfix: An arithmetic expression in which we fix (place) the arithmetic operator after (post) its two operands.
The postfix notation is called as suffix notation OR reverse polish notation.
Example: A B +
Operator Precedence: When an expression consist different level of operators we follow it. We consider
five binary operations: +, -, *, / and ^ (exponentiation). For these binary operations, the following in the
order of precedence (highest to lowest): ^ , * , /, +, -

www.Jntufastupdates.c 39
om
 Operator Associativity: When an expression consist more than one same level precedence operators we
follow it.
Basically we have Left to Right associativity and Right to Left Associativity. Most of the operators are
follows Left to Right but some of the operators are follow Right to left Associativity like Unary (+/-), +
+/-- , Logical negation (!), Pointer and address (*,&), Conditional Operators and Assignment
operators(=,+=,-=,*=,/=,%=).
Example: x=a/b–c+d*e–a*c

Let a = 4, b = c = 2, d = e = 3 then the value of x is found as

= ((4 / 2) – 2) + (3 * 3) – (4 * 2) =0+9–8 =1

EVALUATION OF POSTFIX EXPRESSION:

The standard representation for writing expressions is infix notation. But the compiler uses the
postfix notation for evaluating the expression rather than the infix notation. It is an easy task for
evaluating the postfix expression than infix expression because there are no parentheses. To evaluate
an expression we scan it from left to right. The postfix expression is evaluated easily by the use of a
stack.

To evaluate a postfix expression use the following steps...

1. Read the poststring from left to right
2. Initialize an empty Stack
3. Repeat until end of the poststring
i. If the scanned character is operand, then push it on to the Stack.
ii. If the scanned character is operator (+ , - , * , / etc.,), then pop top two elements from the stack, perform
the operation with the operator then push result back on to the Stack.
4. Finally! We have one element in the stack, perform a pop operation and display the popped value as
final result.

Postfix Expression is 5 3 + 8 2 - *
Symbol Stack Evaluation

Initially

Stack is empty

5
5

www.Jntufastupdates.c 40
om
 Push(5)

www.Jntufastupdates.c 41
om
 3
3 5
Push(3)

Value1=3 Value2=5
8
+ Result=5+3=8 Push(8)
Value1=pop()
Value2=pop() Result=Value2+Value1 Push(Result)

8
8
Push(8) 8
2

2 8
8
Push(2)

Value1=2 Value2=8
6 Result=8-2=6 Push(6)
- 8
Value1=pop() Value2=Pop() Result=Value2-Value1
Push(Result)

Value1=6 Value2=8
* Result=8*6=48
Value1=pop() Push(48)
48
Value2=Pop() Result=Value2*Value1 Push(Result)

End of Expression Final Result is 48

48
Result=pop()

www.Jntufastupdates.c 42
om
 Conversion of INFIX the stack. If top of Stack has lower precedence over
to POSTFIX:
the scanned character then push the operator into
Procedure to convert
from infix expression the stack else pop the element from the stack and add
to postfix expression is it to postfix string and push the scanned character to
as follows.
stack.
1. Initialize an empty
stack
2. Push “(“onto Stack, Example: a * (b + c) *d)
and add “)” to the end
of Infix string.
3. Scan the Infix string T Stack Postfix
from left to right until o String
end of the infix k
e
i. If the scanned character is n
“(“, pushed into the
stack. (
a ( a
ii. If the scanned character
is “)”, pop the * ( * A
elements from the ( ( * ( A
stack up to b ( * ( Ab
encountering the + ( * ( + Ab
“(“, and add the c ( * ( + Abc
popped elements ) ( * abc+
to postfix string ( *
* abc+*
except ( *
d abc+*d
parentheses.
) abc+*d*
iii. If the scanned character is
an operand, add it to
the Postfix string.
iv. If the scanned character
is an Operator,
compare the
precedence of the
character with the
element on top of
 UNIT-V
A graph is an abstract data structure that is used to implement the mathematical concept of
graphs. It is basically a collection of vertices (also called nodes) and edges that connect these
vertices. A graph is often viewed as a generalization of the tree structure, where instead of
having a purely parent-to-child relationship between tree nodes, any kind of complex
relationship can exist.

WHY GRAPHS ARE USEFUL

Graphs are widely used to model any situation where entities or things are related to each
other in pairs. For example, the following information can be represented by graphs:
 Family trees: in which the member nodes have an edge from parent to each of
their children.
 Transportation networks : in which nodes are airports, intersections, ports, etc. The edges
can be airline flights, one-way roads, shipping routes, etc.

DEFINATION:
A graph G is defined as an ordered set (V, E), where V(G) represents the set of vertices and E(G)
represents the edges that connect these vertices.
We have two types of Graphs. Basically:
1. UNDIRECTED GRAPH
2. DIRECTED
GRAPH UNDIRECTED
GRAPH:
Shows a graph with V(G) = {A, B, C, D and E} and E(G) = {(A, B), (B, C), (A, D), (B, D),
(D,E), (C, E)}. Note that there are five vertices or nodes and six edges in the graph.
 FIGURE 5.1

A graph can be directed or undirected. In an undirected graph, edges do not have any
direction associated with them. That is, if an edge is drawn between nodes A and B, then the
nodes can be traversed from A to B as well as from B to A. Figure 5.1 shows an undirected
graph because it does not give any information about the direction of the edges.

DIRECTED GRAPH:
A directed graph G, also known as a digraph, is a graph in which every edge has a direction
assigned to it. An edge of a directed graph is given as an ordered pair (u, v) of nodes in G.
For an edge (u, v),
 The edge begins at u and terminates at v.
 u is known as the origin or initial point of e. Correspondingly, v is known as the
destination or terminal point of e.
 u is the predecessor of v. Correspondingly, v is the successor of u.
 Nodes u and v are adjacent to each other.

FIGURE 5.2

Which shows a directed graph. In a directed graph, edges form an ordered pair. If there is an
edge from A to B, then there is a path from A to B but not from B to A. The edge (A, B) is
said to initiate from node A (also known as initial node) and terminate at node B (terminal
node).
2. REPRESENTATION OF GRAPHS
There are two common ways of storing graphs in the computer’s memory. They are:
 Sequential representation by using an adjacency matrix.
 Linked representation by using an adjacency list that stores the neighbours of a node
using a linked list.

2.1 ADJACENCY MATRIX REPRESENTATION

An adjacency matrix is used to represent which nodes are adjacent to one
another. By definition: Two nodes are said to be adjacent if there is an edge
connecting them.
In a directed graph G, if node v is adjacent to node u, then there is definitely an edge from u to
v. That is, if v is adjacent to u, we can get from u to v by traversing one edge. For any graph G
having n nodes, the adjacency matrix will have the dimension of n X n.
In an adjacency matrix, the rows and columns are labelled by graph vertices.
 An entry aij in the adjacency matrix will contain 1, if vertices vi and vj are adjacent to
each other.
 However, if the nodes are not adjacent, aij will be set to zero.

FIGURE 5.3 Adjacency Matrix Entry

Since an adjacency matrix contains only 0s and 1s, it is called a bit matrix or a Boolean
matrix. The entries in the matrix depend on the ordering of the nodes in G. Therefore, a
change in the order of nodes will result in a different adjacency matrix.
 Figure 5.4 shows some graphs and their corresponding adjacency matrices.

From the above examples, we can draw the following conclusions:

 For a simple graph (that has no loops), the adjacency matrix has 0s on the diagonal.
 The adjacency matrix of an undirected graph is symmetric.
 The memory use of an adjacency matrix is O(n2), where n is the number of nodes in the
graph.
 Number of 1s (or non-zero entries) in an adjacency matrix is equal to the number of
edges in the graph.
 The adjacency matrix for a weighted graph contains the weights of the edges connecting
the nodes.
Now let us discuss the powers of an adjacency matrix:
From adjacency matrix A1, we can conclude that an entry 1 in the ith row and jth column

means that there exists a path of length 1 from vi to vj. Now consider, A2, A3, and A4.
Any entry aij = 1 if aik = akj = 1. That is, if there is an edge (vi, vk) and (vk, vj), then
there is a path from vi to vj of length 2.

FIGURE 5.5 Directed graph with its adjacency matrix

Now, based on the above calculations, we define matrix B as:

Br = A1 + A2 + A3 + ... + A r

FIGURE 5.6 Path Matrix Entry

The main goal to define matrix B is to obtain the path matrix P. The path matrix P can be
calculated from B by setting an entry Pij = 1, if Bij is non-zero and Pij = 0, if otherwise. The
path matrix is used to show whether there exists a simple path from node vi to vj or not.
Let us now calculate matrix B and matrix P using the above discussion.
2.2 ADJACENCY LINKED LIST REPRESEENTATION

 An adjacency list is another way in which graphs can be represented in the computer’s
memory.
 This structure consists of a list of all nodes in G.
 Furthermore, every node is in turn linked to its own list that contains the names of all other
nodes that are adjacent to it.
The key advantages of using an adjacency list are:
 It is easy to follow and clearly shows the adjacent nodes of a particular node.
 It is often used for storing graphs that have a small-to-moderate number of edges. That is,
an adjacency list is preferred for representing sparse graphs in the computer’s memory;
otherwise, an adjacency matrix is a good choice.
 Adding new nodes in G is easy and straightforward when G is represented using an
adjacency list. Adding new nodes in an adjacency matrix is a difficult task, as the size of the
matrix needs to be changed and existing nodes may have to be reordered.
 FIGURE 5.7 Graph G and its adjacency list

 For a directed graph, the sum of the lengths of all adjacency lists is equal to the number of
edges in G.
 However, for an undirected graph, the sum of the lengths of all adjacency lists is equal to
twice the number of edges in G because an edge (u, v) means an edge from node u to v as
well as an edge from v to u.
 Adjacency lists can also be modified to store weighted graphs.
Let us now see an adjacency list for an undirected graph as well as a weighted graph.

FIGURE 5.8 Adjacency list for an undirected graph and a weighted graph
PROGRAMMING EXAMPLE

1. Write a program to create a graph of n vertices using an adjacency list. Also

write the code to read and print its information and finally to delete the graph.
#include
<stdio.h>
#include
<conio.h>
#include
<alloc.h>
struct node
{
char vertex;
struct node
*next;
};
struct node *gnode;
void displayGraph(struct node *adj[], int
no_of_nodes); void deleteGraph(struct node *adj[],
int no_of_nodes); void createGraph(struct node
*adj[], int no_of_nodes); int main()
{
struct node
*Adj[10]; int i,
no_of_nodes;
clrscr();
printf("\n Enter the number of nodes in G: ");
scanf("%d", &no_of_nodes);
for(i = 0; i < no_of_nodes;
i++) Adj[i] = NULL;
createGraph(Adj,
no_of_nodes); printf("\n The
graph is: ");
displayGraph(Adj,
no_of_nodes);
deleteGraph(Adj,
no_of_nodes); getch();
return 0;
}
void createGraph(struct node *Adj[], int no_of_nodes)
{
struct node *new_node,
*last; int i, j, n, val;
for(i = 0; i < no_of_nodes; i++)
{
last = NULL;
printf("\n Enter the number of neighbours of %d: ",
i); scanf("%d", &n);
for(j = 1; j <= n; j++)
{
printf("\n Enter the neighbour %d of %d: ", j, i);
scanf("%d", &val);
new_node = (struct node *) malloc(sizeof(struct
node)); new_node –> vertex = val;
new_node –> next =
NULL; if (Adj[i] ==
NULL)
Adj[i] =
new_node; else
last –> next =
new_node; last =
new_node
}
}
}
void displayGraph (struct node *Adj[], int no_of_nodes)
Graphs 393
{
struct node
*ptr; int i;
for(i = 0; i < no_of_nodes; i++)
{
ptr = Adj[i];
printf("\n The neighbours of node %d
are:", i); while(ptr != NULL)
{
printf("\t%d", ptr –>
vertex); ptr = ptr –> next;
}
}
}
void deleteGraph (struct node *Adj[], int no_of_nodes)
{
int i;
struct node *temp, *ptr;
for(i = 0; i <= no_of_nodes; i++)
{
ptr = Adj[i];
while(ptr ! =
NULL)
{
temp = ptr;
ptr = ptr –>
next;
free(temp);
}
Adj[i] = NULL;
}
}
Output
 Enter the number of nodes in G: 3
Enter the number of neighbours of
0: 1 Enter the neighbour 1 of 0: 2
Enter the number of neighbours of
1: 2 Enter the neighbour 1 of 1: 0

Enter the neighbour 2 of 1: 2

Enter the number of neighbours of
2: 1 Enter the neighbour 1 of 2: 1
The neighbours of node 0
are: 1 The neighbours of
node 1 are: 0 2 The
neighbours of node 2 are: 0

Note If the graph in the above program had been a weighted graph, then the structure of the
node would have been:
typedef struct node
{
int
vertex
; int
weigh
t;
struct node *next;
};

3.GRAPH TRAVERSALS
There are two standard methods of graph traversal. These two methods are:
1. Breadth-first search
2. Depth-first search
1. Breadth-First Search Algorithm
Breadth-first search (BFS) is a graph search algorithm that begins at the root node and
explores all the neighbouring nodes. Then for each of those nearest nodes, the algorithm
explores their unexplored neighbour nodes, and so on, until it finds the goal.
ALGORITHM
Step 1: SET STATUS = 1 (ready
state) for each node in G
Step 2: Enqueue the starting node
A and set its STATUS = 2
(waiting state)
Step 3: Repeat Steps 4 and 5 until QUEUE is empty
Step 4: Dequeue a node N.
Process it and set its STATUS = 3
(processed state).
Step 5: Enqueue all the
neighbours of N that are in the
ready state
(whose STATUS = 1) and
set their STATUS = 2
(waiting
state) [END
OF LOOP]
Step 6: EXIT

FIGURE 5.9 Graph G And Its Adjacnecy List

EXAMPLE
Consider the graph G given in Fig. 5.9.The adjacency list of G is also given. Assume that G
represents the daily flights between different cities and we want to fly from city A to I with
minimum stops. That is, find the minimum path P from A to I given that every edge has a
length of 1.
 SOLUTION:
The minimum path P can be found by applying the breadth-first search algorithm that begins
at city A and ends when I is encountered. During the execution of the algorithm, we use two
arrays:
1. QUEUE
2. ORIG
 While QUEUE is used to hold the nodes that have to be processed,
 ORIG is used to keep track of the origin of each edge.
 Initially, FRONT = REAR = –1.
The algorithm for this is as follows:
(a) Add A to QUEUE and add NULL to ORIG.
FRONT = 0 QUEUE = A
REAR = 0 ORIG = \0
(b)Dequeue a node by setting FRONT = FRONT + 1 (remove the FRONT element of QUEUE)
and enqueue the neighbours of A. Also, add A as the ORIG of its neighbours.
FRONT = 1 QUEUE = A B C D
REAR = 3 ORIG = \0 A A A
(c) Dequeue a node by setting FRONT = FRONT + 1 and enqueue the neighbours of B. Also,
add B as the ORIG of its neighbours.
FRONT = 2 QUEUE = A B C D E
REAR = 4 ORIG = \0 A A A B
(d)Dequeue a node by setting FRONT = FRONT + 1 and enqueue the neighbours of C. Also,
add C as the ORIG of its neighbours. Note that C has two neighbours B and G. Since B has
already been added to the queue and it is not in the Ready state, we will not add B and
only add G.
FRONT = 3 QUEUE = A B C D E G
REAR = 5 ORIG = \0 A A A B
C
(e) Dequeue a node by setting FRONT = FRONT + 1 and enqueue the neighbours of D. Also,
add D as the ORIG of its neighbours. Note that D has two neighbours C and G. Since both of
them have already been added to the queue and they are not in the Ready state, we will
not add them again.
FRONT = 4 QUEUE = A B C D E G
REAR = 5 ORIG = \0 A A A B
C
(f) Dequeue a node by setting FRONT = FRONT + 1 and enqueue the neighbours of E. Also,
add E as the ORIG of its neighbours. Note that E has two neighbours C and F. Since C has
already been added to the queue and it is not in the Ready state, we will not add C and add
only F.
FRONT = 5 QUEUE = A B C D E G F
REAR = 6 ORIG = \0 A A A B C
E

(g)Dequeue a node by setting FRONT = FRONT + 1 and enqueue the neighbours of G. Also,
add G as the ORIG of its neighbours. Note that G has three neighbours F, H, and I.
FRONT = 6 QUEUE = A B C D E G F H I
REAR = 9 ORIG = \0 A A A B C E G
G

Since F has already been added to the queue, we will only add H and I. As I is our final
destination, we stop the execution of this algorithm as soon as it is encountered and added to
the QUEUE. Now, backtrack from I using ORIG to find the minimum path P. Thus, we have
P as A -> C -> G -> I.
Features of Breadth-First Search Algorithm
Space complexity:
The space complexity is therefore proportional to the number of nodes at the
deepest level of the graph.
Given a graph with branching factor b (number of children at each node) and depth
d, the asymptotic space complexity is the number of nodes at the deepest level O(bd).
The space complexity can also be expressed as O ( | E | + | V | ), where | E | is the
total number of edges in G and | V | is the number of nodes or vertices.
Time Complexity:
In the worst case, breadth-first search has to traverse through all paths to all
possible nodes, thus the time complexity of this algorithm asymptotically approaches O(bd).
However, the time complexity can also be expressed as O( | E | + | V | ), since
 every vertex and every edge will be explored in the worst case.
Completeness:
Breadth-first search is said to be a complete algorithm because if there is a solution,
breadth-first search will find it regardless of the kind of graph. But in case of an infinite
graph where there is no possible solution, it will diverge.
Optimality:
Breadth-first search is optimal for a graph that has edges of equal length, since it
always returns the result with the fewest edges between the start node and the goal node.
we have weighted graphs that have costs associated with each edge, so the goal
next to the start does not have to be the cheapest goal available.
Applications of Breadth-First Search Algorithm
Breadth-first search can be used to solve many problems such as:
 Finding all connected components in a graph G.
 Finding all nodes within an individual connected component.
 Finding the shortest path between two nodes, u and v, of an unweighted graph.
 Finding the shortest path between two nodes, u and v, of a weighted graph.

Programming Example
2. Write a program to implement the breadth-first search

algorithm. #include <stdio.h>

#define MAX 10

void breadth_first_search(int adj[][MAX],int visited[],int start)

int queue[MAX],rear = –1,front =– 1, i;

queue[++rear] = start;

visited[start] = 1;

while(rear !=

front)

{
start = queue[+

+front]; if(start ==

4) printf("5\t");

else

printf("%c \t",start +

65); for(i = 0; i < MAX;

i++)

{
if(adj[start][i] == 1 && visited[i] == 0)

queue[++rear] = i;

visited[i] = 1;

int main()

{
int visited[MAX] =
{0}; int adj[MAX]
[MAX], i, j;
printf("\n Enter the adjacency matrix:
"); for(i = 0; i < MAX; i++)
for(j = 0; j < MAX; j++)
scanf("%d", &adj[i][j]);
breadth_first_search(adj,visite
d,0); return 0;
}
 Output
Enter the adjacency matrix:
01010
10110
01001
11001
00110
ABDCE
2. Depth First Algorithm
The depth-first search algorithm progresses by expanding the starting node of G and then
going deeper and deeper until the goal node is found, or until a node that has no children is
encountered.
When a dead-end is reached, the algorithm backtracks, returning to the most recent node that
has not been completely explored.
Algorithm
Step 1: SET STATUS = 1 (ready state) for each node
in G Step 2: Push the starting node A on the stack and
set
its STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until STACK is
empty Step 4: Pop the top node N. Process it
and set its
STATUS = 3 (processed state)
Step 5: Push on the stack all the neighbours of N that are
in the ready state (whose STATUS = 1) and set
their STATUS = 2 (waiting state)
[END OF
LOOP] Step 6: EXIT
 FIGURE 5.10 Graph G And Its Adjacency List
Example:
Consider the graph G given in. The adjacency list of G is also given. Suppose we want to
print all the nodes that can be reached from the node H (including H itself). One alternative
is to use a depth-first search of G starting at node H. The procedure can be explained here.
Solution:
(a) Push H onto the stack.
STACK: H
(b)Pop and print the top element of the STACK, that is, H. Push all the neighbours of H
onto the stack that are in the ready state. The STACK now becomes
PRINT: H STACK: E, I

(c) Pop and print the top element of the STACK, that is, I. Push all the neighbours of I
onto the stack that are in the ready state. The STACK now becomes
PRINT: I STACK: E, F

(d)Pop and print the top element of the STACK, that is, F. Push all the neighbours of F
onto the stack that are in the ready state. (Note F has two neighbours, C and H. But only C
will be added, as H is not in the ready state.) The STACK now becomes
PRINT: F STACK: E, C

e) Pop and print the top element of the STACK, that is, C. Push all the neighbours of C
onto the stack that are in the ready state. The STACK now becomes
PRINT: C STACK: E, B, G

(f) Pop and print the top element of the STACK, that is, G. Push all the neighbours of G
onto the stack that are in the ready state. Since there are no neighbours of G that are in
the ready state,
no push operation is performed. The STACK now becomes PRINT:
G STACK: E, B

(g)Pop and print the top element of the STACK, that is, B. Push all the neighbours of B onto
 the stack that are in the ready state. Since there are no neighbours of B that are in the
ready state,
no push operation is performed. The STACK now becomes PRINT:
B STACK: E

h) Pop and print the top element of the STACK, that is, E. Push all the neighbours of E
onto the stack that are in the ready state. Since there are no neighbours of E that are in the
ready state, no push operation is performed. The STACK now becomes empty.
PRINT: E STACK:

Since the STACK is now empty, the depth-first search of G starting at node H is complete
and the nodes which were printed are:
H, I, F, C, G, B, E
These are the nodes which are reachable from the node H.
Features of Depth-First Search
Algorithm Space complexity:
The space complexity of a depth-first search is lower than that of a breadth first search.
Time complexity:
The time complexity of a depth-first search is proportional to the number of vertices plus the
number of edges in the graphs that are traversed. The time complexity can be given as (O(|V|
+|E|)).
Completeness:
Depth-first search is said to be a complete algorithm. If there is a solution, depthfirst search
will find it regardless of the kind of graph. But in case of an infinite graph, where there is no
possible solution, it will diverge.

Applications of Depth-First Search Algorithm

Depth-first search is useful for:
 Finding a path between two specified nodes, u and v, of an unweighted graph.
 Finding a path between two specified nodes, u and v, of a weighted graph.
 Finding whether a graph is connected or not.
 Computing the spanning tree of a connected graph.
Programming Example:
3. Write a program to implement the depth-first search
algorithm. #include <stdio.h>
#define MAX 5
void depth_first_search(int adj[][MAX],int visited[],int start)
{
int
stack[MAX
]; int top =
–1, i;
printf("%c–",start + 65);
visited[start] = 1;
stack[++top] =
start; while(top !
= –1)
{
start = stack[top];
for(i = 0; i < MAX; i++)
{
if(adj[start][i] && visited[i] == 0)
{
stack[++top] = i;
printf("%c–", i +
65); visited[i] = 1;
break;
}
}
if(i ==
MAX)
top––;
}
}
int main()
{
int adj[MAX][MAX];
 int visited[MAX] = {0}, i, j;
400 Data Structures Using C
printf("\n Enter the adjacency matrix:
"); for(i = 0; i < MAX; i++)
for(j = 0; j < MAX; j++)
scanf("%d", &adj[i][j]);
printf("DFS Traversal: ");
depth_first_search(adj,visited
,0); printf("\n");
return 0;
}
Output
Enter the adjacency matrix:
01010
10110
01001
11001
00110
DFS Traversal: A –> C –> E –>

APPLICATIONS
MINIMUM SPANNING TREES:
 A spanning tree of a connected, undirected graph G is a sub-graph of G which is a tree that
connects all the vertices together
 A graph G can have many different spanning trees.
 We can assign weights to each edge (which is a number that represents how unfavourable
the edge is), and use it to assign a weight to a spanning tree by calculating the sum of the
weights of the edges in that spanning tree.
 A minimum spanning tree (MST) is defined as a spanning tree with weight less than or
equal to the weight of every other spanning tree. In other words, a minimum spanning
tree is a spanning tree that has weights associated with its edges, and the total weight of the
tree (the sum of the weights of its edges) is at a minimum.

Example: Consider an unweighted graph G given below (Fig. 5.11). From G, we can draw
many distinct spanning trees. Eight of them are given here. For an unweighted graph, every
spanning tree is a minimum spanning tree.

FIGURE 5.11 Unweighted Graph And Its Spanning Trees

EXAMPLE: Consider a weighted graph G shown in Fig. 5.12. From G, we can draw three
distinct spanning trees. But only a single minimum spanning tree can be obtained, that is, the
one that has the minimum weight (cost) associated with it. Of all the spanning trees given in
Fig. 5.12, the one that is highlighted is called the minimum spanning tree, as it has the
lowest cost associated with it.

FIGURE 5.12 Weighted Graph And Its Spanning Trees.

 APPLICATIONS FOR MINIMUM SPANNING TREES:
 MST’S is widely used for designing networks.
 MST’S are used to find airlane routes.
 MST’S are also used to find the cheapest way to connect terminals, such as cities,
electronic components or computers via roads, airlines, railways, wires or telephone lines.
 MST’S are applied in routing algorithms for finding the most efficient path.

We have two types of ALGORITHMS in Minimum Spanning Trees. They are:

1. PRIM’S ALGORITHM
2. KRUSKAL’S ALGORITHM

1. PRIM’S ALGORITHM
 Prim’s algorithm is a greedy algorithm that is used to form a minimum spanning tree for a
connected weighted undirected graph.
 In other words, the algorithm builds a tree that includes every vertex and a subset of the
edges in such a way that the total weight of all the edges in the tree is minimized.
For this, the algorithm maintains three sets of vertices which can be given as below:
 Tree vertices Vertices that are a part of the minimum spanning tree T.
 Fringe vertices Vertices that are currently not a part of T, but are adjacent to some tree
vertex.
 Unseen vertices Vertices that are neither tree vertices nor fringe vertices fall under this
category.

ALGORITHM
Step 1: Select a starting vertex
Step 2: Repeat Steps 3 and 4 until there are fringe
vertices Step 3: Select an edge e connecting the tree
vertex and
fringe vertex that has minimum
weight Step 4: Add the selected edge and the
vertex to the
minimum spanning tree T
[END OF LOOP]
Step 5: EXIT
EXAMPLE: Construct a minimum spanning tree of the graph given in Fig. 5.13

FIGURE 5.13
Step 1: Choose a starting vertex A.
Step 2: Add the fringe vertices (that are adjacent to A). The edges connecting the vertex
and fringe vertices are shown with dotted lines.
Step 3: Select an edge connecting the tree vertex and the fringe vertex that has the minimum
weight and add the selected edge and the vertex to the minimum spanning tree T. Since the
edge connecting A and C has less weight, add C to the tree. Now C is not a fringe vertex
but a tree vertex.
Step 4: Add the fringe vertices (that are adjacent to C).
Step 5: Select an edge connecting the tree vertex and the fringe vertex that has the minimum
weight and add the selected edge and the vertex to the minimum spanning tree T. Since the
edge connecting C and B has less weight, add B to the tree. Now B is not a fringe vertex
but a tree vertex.
Step 6: Add the fringe vertices (that are adjacent to B).
Step 7: Select an edge connecting the tree vertex and the fringe vertex that has the
minimum weight and add the selected edge and the vertex to the minimum spanning tree
T. Since the edge connecting B and D has less weight, add D to the tree. Now D is not a
fringe vertex but a tree vertex.
Step 8: Note, now node E is not connected, so we will add it in the tree because a minimum
spanning tree is one in which all the n nodes are connected with n–1 edges that have
minimum weight. So, the minimum spanning tree can now be given as,
 2. KRUSKAL’S ALGORITHM
 Kruskal’s algorithm is used to find the minimum spanning tree for a connected weighted
graph.
 The algorithm aims to find a subset of the edges that forms a tree that includes every
vertex. The total weight of all the edges in the tree is minimized.
 However, if the graph is not connected, then it finds a minimum spanning forest. Note that
a forest is a collection of trees. Similarly, a minimum spanning forest is a collection of
minimum spanning trees.
 Kruskal’s algorithm is an example of a greedy algorithm, as it makes the locally optimal
choice at each stage with the hope of finding the global optimum.

ALGORITHM
Step 1: Create a forest in such a way that each graph is a separate tree.
Step 2: Create a priority queue Q that contains all the edges of the
graph.
Step 3: Repeat Steps 4 and 5 while Q is NOT
EMPTY Step 4: Remove an edge from Q
Step 5: IF the edge obtained in Step 4 connects two different trees, then
Add it to the forest (for combining two trees into one tree).
ELSE
Discard the
edge Step 6: END

EXAMPLE: Apply Kruskal’s algorithm on the graph given in Fig. 5.14.

Initially, we have F = {{A}, {B}, {C}, {D}, {E}, {F}}
MST = {}
Q = {(A, D), (E, F), (C, E), (E, D), (C, D), (D,
F), (A, C), (A, B), (B, C)}

FIGURE 5.14
Step 1: Remove the edge (A, D) from Q and make the following changes:

F = {{A, D}, {B}, {C}, {E}, {F}} MST = {A, D}

Q = {(E, F), (C, E), (E, D), (C, D),
(D, F), (A, C), (A, B), (B, C)}
Step 2: Remove the edge (E, F) from Q and make the following changes:

F = {{A, D}, {B}, {C}, {E, F}} MST = {(A, D), (E, F)}
Q = {(C, E), (E, D), (C, D), (D, F),
(A, C), (A, B), (B, C)}
Step 3: Remove the edge (C, E) from Q and make the following changes:

F = {{A, D}, {B}, {C, E, F}}

MST = {(A, D), (C, E), (E, F)}
Q = {(E, D), (C, D), (D, F), (A, C), (A, B), (B, C)}

Step 4: Remove the edge (E, D) from Q and make the following changes:

F = {{A, C, D, E, F}, {B}}

MST = {(A, D), (C, E), (E, F), (E, D)}
Q= {(C, D), (D, F), (A, C), (A, B), (B, C)}
Step 5: Remove the edge (C, D) from Q. Note that this edge does not connect different trees,
so simply discard this edge. Only an edge connecting (A, D, C, E, F) to B will be added to
the MST. Therefore,
F = {{A, C, D, E, F}, {B}}
MST = {(A, D), (C, E), (E, F), (E, D)}
Q = {(D, F), (A, C), (A, B), (B, C)}
Step 6: Remove the edge (D, F) from Q. Note that this edge does not connect different trees,
so simply discard this edge. Only an edge connecting (A, D, C, E, F) to B will be added to
the MST.
F = {{A, C, D, E, F}, {B}}
MST = {(A, D), (C, E), (E, F), (E, D)}
Q = {(A, C), (A, B), (B, C)}
Step 7: Remove the edge (A, C) from Q. Note that this edge does not connect different trees,
so simply discard this edge. Only an edge connecting (A, D, C, E, F) to B will be added to
the MST.
F = {{A, C, D, E, F}, {B}}
MST = {(A, D), (C, E), (E, F), (E, D)} Q = {(A, B), (B,
C)}
Step 8: Remove the edge (A, B) from Q and make the following changes:

F = {A, B, C, D, E, F}
MST = {(A, D), (C, E), (E, F), (E,D), (A, B)}
Q = {(B, C)}
Step 9: The algorithm continues until Q is empty. Since the entire forest has become one
tree, all the remaining edges will simply be discarded. The resultant MS can be given as
shown below

F = {A, B, C, D, E, F}
MST = {(A, D), (C, E), (E, F), (E,D), (A, B)}
Q = {}

PROGRAMMING EXAMPLE:
5. Write a program which finds the cost of a minimum
spanning tree. #include<stdio.h>
#include<conio.h
> #define MAX
10
int adj[MAX][MAX], tree[MAX][MAX],
n; void readmatrix()
{
int i, j;
printf(“\n Enter the number of nodes in the Graph :
“); scanf(“%d”, &n);
printf(“\n Enter the adjacency matrix of the
Graph”); for (i = 1; i <= n; i++)
for (j = 1; j <= n; j+
+) scanf(“%d”,
&adj[i][j]);
}
int spanningtree(int src)
{
 DE
PARTMENT OF INFORMATION TECHNOLOGY
int visited[MAX], d[MAX],
parent[MAX]; int i, j, k, min, u, v, cost;
for (i = 1; i <= n; i++)
{
d[i] = adj[src]
[i]; visited[i]
= 0; parent[i]
= src;
}
visited[src] = 1;
cost = 0;
k = 1;
for (i = 1; i < n; i++)
{
min = 9999;
for (j = 1; j <= n; j++)
{
if (visited[j]==0 && d[j] < min)
{
min =
d[j]; u =
j;
cost += d[u];
}
}
visited[u] = 1;
//cost = cost +
d[u]; tree[k][1] =
parent[u];
tree[k++][2] = u;
for (v = 1; v <= n; v++)
if (visited[v]==0 && (adj[u][v] < d[v]))
 DE
PARTMENT OF INFORMATION TECHNOLOGY
{
d[v] = adj[u][v];
parent[v] = u;
}
}
return cost;
}
void display(int cost)
{
int i;
printf(“\n The Edges of the Mininum Spanning Tree
are”); for (i = 1; i < n; i++)
printf(“ %d %d \n”, tree[i][1], tree[i][2]);
printf(“\n The Total cost of the Minimum Spanning Tree is : %d”, cost);
}
main()
{
int source, treecost;
readmatrix();
printf(“\n Enter the Source :
“); scanf(“%d”, &source);
treecost =
spanningtree(source);
display(treecost);
return 0;
}
Output
Enter the number of nodes in the Graph : 4
Enter the adjacency matrix : 0 1 1 0
0001
0100
1010
Enter the source : 1
 DE
PARTMENT OF INFORMATION TECHNOLOGY
The edges of the Minimum Spanning Tree are
1442
23
The total cost of the Minimum Spanning Tree is : 1

Dijkstra’s Algorithm
Dijkstra’s algorithm, given by a Dutch scientist Edsger Dijkstra in 1959, is used to find the
shortest path tree. This algorithm is widely used in network routing protocols, most notably
IS-IS and OSPF (Open Shortest Path First).
Given a graph G and a source node A, the algorithm is used to find the shortest path (one
having the lowest cost) between A (source node) and every other node. Moreover, Dijkstra’s
algorithm is also used for finding the costs of the shortest paths from a source node to a
destination node.
For example, if we draw a graph in which nodes represent the cities and weighted edges
represent the driving distances between pairs of cities connected by a direct road, then
Dijkstra’s algorithm when applied gives the shortest route between one city and all other
cities.

ALGORITHM
 Dijkstra’s algorithm is used to find the length of an optimal path between two nodes in a
graph.
 The term optimal can mean anything, shortest, cheapest, or fastest.
 If we start the algorithm with an initial node, then the distance of a node Y can be given as
the distance from the initial node to that node.

1. Select the source node also called the initial node

2. Define an empty set N that will be used to hold nodes to which a shortest path has been found.
3. Label the initial node with , and insert it into N.
4. Repeat Steps 5 to 7 until the destination node is in N or there are no more labelled nodes in N.
5. Consider each node that is not in N and is connected by an edge from the newly inserted node.
6. (a) If the node that is not in N has no label then SET the label of the node = the label of
the newly inserted node + the length of the edge.
 DE
PARTMENT OF INFORMATION TECHNOLOGY
(b) Else if the node that is not in N was already labelled, then SET its new
label = minimum (label of newly inserted vertex + length of edge, old
label)
7. Pick a node not in N that has the smallest label assigned to it and
add it to N.

Dijkstra’s algorithm labels every node in the graph where the labels represent the
distance (cost) from the source node to that node.
There are two kinds of labels: temporary and permanent.
Temporary labels are assigned to nodes that have not been reached, while permanent labels
are given to nodes that have been reached and their distance (cost) to the source node is
known. A node must be a permanent label or a temporary label, but not both.
The execution of this algorithm will produce either of the following two results:
1. If the destination node is labelled, then the label will in turn represent the distance
from the source node to the destination node.
2. If the destination node is not labelled, then there is no path from the source to the
destination node.

EXAMPLE:
Consider the graph G given in Fig. 5.14. Taking D as the initial node, execute the Dijkstra’s
algorithm on it.

FIGURE 5.14

Step 1: Set the label of D = 0 and N = {D}.

Step 2: Label of D = 0, B = 15, G = 23, and F = 5. Therefore, N = {D, F}.
Step 3: Label of D = 0, B = 15, G has been re-labelled 18 because
 DE
PARTMENT OF INFORMATION TECHNOLOGY
minimum (5 + 13, 23) = 18, C has been re-labelled 14 (5 + 9). Therefore,
N = {D,
F, C}.
Step 4: Label of D = 0, B = 15, G = 18. Therefore, N = {D, F, C, B}.
Step 5: Label of D = 0, B = 15, G = 18 and A = 19 (15 + 4). Therefore, N =
{D, F, C, B, G}.
Step 6: Label of D = 0 and A = 19. Therefore, N = {D, F, C, B, G, A}
Note that we have no labels for node E; this means that E is not reachable from D. Only
the nodes that are in N are reachable from B.
The running time of Dijkstra’s algorithm can be given as O(|V|2+|E|)=O(|V|2) where V is the
set of vertices and E in the graph.
Warshall’s Algorithm
If a graph G is given as G=(V, E), where V is the set of vertices and E is the set of edges,
the path matrix of G can be found as, P = A + A2 + A3 + ... + An.
This is a lengthy process, so Warshall has given a very efficient algorithm to calculate the
path matrix. Warshall’s algorithm defines matrices P0, P1, P2, º, Pn.

Path Matrix Entry

 This means that if P0[i][j] = 1, then there exists an edge from node vi to vj.
 If P1[i][j] = 1, then there exists an edge from vi to vj that does not use any other vertex
except v1.
Hence, the path matrix Pn can be calculated with the formula given as:
Pk[i][j] = Pk–1[i][j] V (Pk–1[i][k] ^ Pk–1[k][j])
where V indicates logical OR operation and ^ indicates logical AND operation.
 DE
PARTMENT OF INFORMATION TECHNOLOGY
ALGORITHM
Step 1: [ the Path Matrix] Repeat Step 2 for I = to n-1,
where n is the number of nodes in the graph
Step 2: Repeat Step 3 for J = to n-1
Step 3: IF A[I][J] = , then SET P[I]
[J] =
ELSE P[I][J] = 1
[END OF LOOP]
[END OF LOOP]
Step 4: [Calculate the path matrix P] Repeat Step 5 for K = to n-
1 Step 5: Repeat Step 6 for I = to n-1

Step 6: Repeat Step 7 for J= to n-1

Step 7: SET P [I][J] = P [I][J] V (P [I][K] P
[K][J])
Step 8: EXIT
EXAMPLE:
Consider the graph in Fig. 13.39 and its adjacency matrix A. We can straightaway calculate
the path matrix P using the Warshall’s algorithm. The path matrix P can be given in a single
step as:

GRAPH G AND ITS PATH MATRIX

PROGRAMMING EXAMPLE

6. Write a program to implement Warshall’s algorithm to find the path

matrix. #include <stdio.h>
#include <conio.h>
 DE
PARTMENT OF INFORMATION TECHNOLOGY
void read (int mat[5][5], int n);
void display (int mat[5][5], int
n); void mul(int mat[5][5], int
n);
int main()
{
int adj[5][5], P[5][5], n, i, j, k;
clrscr();
printf("\n Enter the number of nodes in the graph :
"); scanf("%d", &n);
printf("\n Enter the adjacency matrix : ");
read(adj, n);

clrscr();
printf("\n The adjacency matrix is : ");
display(adj, n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(adj[i][j] == 0)
P[i][j] = 0;
else
P[i][j] = 1;
}
}
for(k=0; k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
P[i][j] = P[i][j] | ( P[i][k] & P[k][j]);
}
 DE
PARTMENT OF INFORMATION TECHNOLOGY
}
printf("\n The Path Matrix is
:"); display (P, n);
getch(); return 0;
}
void read(int mat[5][5], int n)
{
int i, j;
for(i=0;i<n;i+
+)
{
for(j=0;j<n;j++)
{
printf("\n mat[%d][%d] = ", i, j);
scanf("%d", &mat[i][j]);
}
}
}
void display(int mat[5][5], int n)
{
int i, j;
for(i=0;i<n;i+
+) printf("\n");
for(j=0;j<n;j+
+)
printf("%d\t", mat[i][j]);
}
}
Output
The adjacency
matrix is 0 1 1 0
0011
0001
 DE
PARTMENT OF INFORMATION TECHNOLOGY
1100
Graphs 417
The Path
Matrix is 1 1 1
1
1111
1111
1111
Transitive Closure of a Directed Graph
Definition
For a directed graph G = (V,E), where V is the set of vertices and E is the set of edges, the
transitive closure of G is a graph G* = (V,E*). In G*, for every vertex pair v, w in V there is
an edge (v, w) in E* if and only if there is a valid path from v to w in G.

(a) A graph G and its

(b) transitive closure G*

Where and Why is it Needed?

Finding the transitive closure of a directed graph is an important problem in the following
computational tasks:
 Transitive closure is used to find the reachability analysis of transition networks
representing distributed and parallel systems.I
 It is used in the construction of parsing automata in compiler construction.
 Recently, transitive closure computation is being used to evaluate recursive database
queries (because almost all practical recursive queries are transitive in nature).

ALGORITHM
Transitive_Closure(A, t, n)
 DE
PARTMENT OF INFORMATION TECHNOLOGY
Step 1: SET i=1, j=1, k=1
Step 2: Repeat Steps 3 and 4 while
i<=n Step 3: Repeat Step 4 while
j<=n
Step 4: IF (A[i][j] = 1)
SET t[i][j] = 1
ELSE
SET t[i][j] =
INCREMENT j [END
OF LOOP]
INCREMENT i [END
OF LOOP]
Step 5: Repeat Steps 6 to 11 while k<=n
Step 6: Repeat Steps 7 to 1 while i<=n
Step 7: Repeat Steps 8 and 9 while
j<=n Step 8: SET t[i,j] = t[i][j] V (t[i]
[k] t[k][j])
Step 9: INCREMENT j
[END OF
LOOP] Step 10 :
INCREMENT i
[END OF LOOP]
Step 11: INCREMENT k
[END OF LOOP]
Step 12: END