3.

2 212CSE2301: DATA STRUCTURES

212CSE2301 DATA STRUCTURES L T P X C

3 0 2 0 4
Pre-requisite :NIL
Course Category :Program Core
Course Type :Integrated Course - Theory

COURSE OBJECTIVES:
• Identify the systematic way of solving the problems searching techniques

• Understand and evaluate Abstract Data Types and linear data structures

• Design non-linear data structures such as trees and graphs

• Understand the efficiency of various sorting and hashing techniques

• Apply data structure concepts to various examples and real life applications

COURSE OUTCOMES:
CO1: Understand the role of algorithms and programming constructs as a systematic and
efficient way of solving problems searching techniques

CO2: Create Abstract Data Types for linear data structures and implement the same.

CO3: Design and implement non-linear data structures such as tree

CO4: Interpret and analyze efficiency of various sorting techniques and hashing

CO5: Design data structures and develop code for real life problems using graphs

MAPPING OF COURSE OUTCOMES WITH PO, PSO:

PO’S PSO’S
1 2 3 4 5 6 7 8 9 10 11 12 1 2
CO1 S S S
CO2 S S S
CO3 S S M L M S M
CO4 S S M L M S M
CO5 S S M L S

83
UNIT I: INTRODUCTION
Basic Terminologies: Data Structure- Operations: insertion, deletion, traversal etc.; Anal-
ysis of an Algorithm, Asymptotic Notations, Time Space Trade off. Searching: Linear
Search and Binary Search Techniques, and their complexity analysis.

UNIT II: LINEAR STRUCTURES

Abstract Data Types (ADT)-List ADT- Array based implementation- Singly linked list
implementation, Doubly linked lists, Circular Linked Lists- Applications of lists- stack
ADT- Queue ADT, Circular queue implementation- Applications of stacks and queue.

UNIT III: TREES

Trees: Basic Terminologies, Different types of Tree: Tree Traversals Binary Tree, Ex-
pression Tree. Binary Search Tree ADT, Threaded Binary Trees, AVL Tree, Red-Black
Trees, Splay Trees, B Tree , B+ Tree, Heaps – Binary heaps-Applications of binary heaps.

UNIT IV – SORTING AND HASHING

Sorting – Bubble Sort, Insertion Sort, Selection Sort, Shell Sort ,Heap Sort, Merge Sort,
Quick Sort. Hashing - Separate chaining, open addressing, rehashing, extendible hashing.

UNIT V - GRAPHS
Basic Terminologies and Representations Traversal algorithms: Depth First Search (DFS)
and Breadth First Search (BFS)- Shortest path algorithms –Floyds, Warshall , Minimum
Spanning Tree – Prims and Kruskals algorithms, Topological sorting, biconnectivity- Eu-
ler circuits.

15 WEEK COURSE PLAN

Week Lecture (1 hours) Pedagogy Practical (2 hours) Assignment/ Practice

Basic Terminolo- Explicit Problem scenario in Courseera on data struc-
Week 1 gies: Elementary Teaching structures, arrays tures using C++ /DS
Data Organiza- and pointers using python
tions, Data Struc-
ture operations :
insertion, deletion,
traversal,Analysis
of an Algorithm

84
Week 2 Asymptotic Nota- Explicit Problem scenario in Analysis of Problems in
tions, Time-Space Teaching searching terms of time and Space
trade off,Searching: (GATE)
Linear, Binary
Search Techniques,
and their complex-
ity analysis.
Week 3 ADT Stack and its Explicit Problem scenario in Assignment Submission
operations, Appli- Teaching Stack and its appli- problem using LIFO and
cations - Expres- cation using arrays FIFO
sion Conversion
and evaluation,
Complexity Analy-
sis
Week 4 ADT queue, Types Explicit Problem scenario in Roller-Coaster ride us-
of Queue: Simple, Teaching Queue and types of ing Queue ADT
Circular,Priority queue using arrays
Queues : Opera-
tions on each types
of Queues, Com-
plexity Analysis ,
Week 5 Singly linked Explicit Problem scenario in Merging L1and L2
lists: Represen- Teaching linked list opera- without duplicate data
tation and oper- tions in the list, Hackerrank
ations:Traversing, Challenges- I
Searching, Inser-
tion into, Deletion
from linked list
Week 6 Linked represen- Explicit Problem scenario in Implementation of Muti-
tation of Stack Teaching Stack and queue player board game using
and Queue, Header using Linked list linked list concepts in C/
nodes, Doubly and pointers python language, Hack-
linked list: op- errank Challenges- II
erations on it
and algorithmic
analysis,Circular
Linked Lists: all
operations their
algorithms and
the complexity
analysis.
Week 7 Basic Tree Termi- Explicit Problem scenario in Develop an application
nologies, Different Teaching Binary search ma- program for executing
types of Trees: Bi- nipulation all the tree traversal
nary Tree, Binary with interactive output
Search Tree

85
Week 8 Applications of BT, Explicit Problem scenario in Tree Terminology and
BST, Threaded Bi- Teaching Binary search Tree its operations( GATE)
nary Trees and its manipulation
insertion and dele-
tion
Week 9 Height Balanced Explicit Problem scenario in Indian Railway ticketing
Trees : AVL Tree Teaching AVL operations system using Red -Black
and its Rotations trees
Week 10 B Tree, B+ Explicit Problem scenario in To implement an appli-
Tree:definitions, Teaching B+ tree operations cations for Auto correc-
algorithms and tors and spell checker us-
analysis ing all tree concepts
Week 11 Objective and Explicit Problem scenario in Apply all sorting tech-
properties of dif- Teaching internal sorting niques for sorting a
ferent sorting large data set From
algorithms, Selec- your observation and
tion Sort, Bubble analysis,determine the
Sort,Insertion Sort, best sorting technique
Quick Sort, Merge for working with large
Sort numbers
Week 12 Heap Sort, Perfor- Explicit Problem scenario in Secure Hashing Algo-
mance and Com- Teaching External sorting rithm SHA-512
parison of sorting
methods, Hashing.
Week 13 Graph -Basic Ter- Explicit Problem scenario in Implementation of
minologies and Teaching Graph application Google Page Rank Al-
Representations, and traversal gorithm , Search engine
Traversal algo- crawlers - web page
rithms: Depth indexing and searching
First Search, using graph traversal
(DFS) and Breadth
First Search (BFS)
Week 14 Shortest path algo- Explicit Problem scenario in Floyds Warshall algo-
rithms –Dijkstra Teaching Shortest path rithm for Shortest Path
Week 15 Minimum Span- Explicit Problem scenario in Bellman Ford algorithm
ning Tree Algo- Teaching MST Algorithms
rithms -Prim’s,
Kruskal’s Algo-
rithm, Topological
sorting

86
EXPERIMENTS:
1. Programs using structures, arrays, pointers to structures and passing them as pa-
rameters to functions.

2. Programs for various types of recursion searching

3. Program for linked list and its operations.

4. Program for array implementation of stack and queue

5. Program for various applications of stack.

6. Program for linked list implementation of stack and queue.

7. Program for binary search tree and its operations

8. Program for various simple sorting techniques: Selection Sort b) Bubble Sort c)
Insertion Sort

9. Program for various advanced sorting techniques : a) quick sort b) Merge sort c)
Heap sort

10. Program for Dijikstra’s shortest path algorithms in graphs

11. Program for finding minimum spanning tree in graphs using Kruskal’s and Prim’s
algorithms

12. Secure Hashing Algorithm SHA-512

13. Bellman Ford algorithm

14. RED black and Splay tree

TEXT BOOK(S):
1. M.A.Weiss, “Data Structures and Algorithm Analysis in C”, 4 th Edition, Pearson
Education, 2013.

REFERENCES:
1. A.V.Aho, J.E.Hopcroft and J.D.Ullman, “Data Structures and Algorithms”, Pear-
son Education, 2005.

2. Fundamentals of Data Structures”, Third Edition by Ellis Horowitz, Sartaj Sahni,

Computer Science Press,2010.

3. Deepalakshmi, Shasi Anand Sridharan, “Fundamental Data Structures and algo-

rithms” Pearson Publications, India, 2019

87