SY CSA
Dr. Rupali Gangarde
DS: 3-credits course (30 CA+ 45 ESE)
DS Lab: 1-Credits (30+20) ESE
Books Recommended:
“Fundamentals of Data Structures in C”, E. Horowitz, [Link]
and [Link]-Freed, ISBN 10:8173716056, University Press,
2nd Edition 2007.
“Let us C & Pointer in C”, Yashwant Kanitkar, ISBN
9788183331630, BPB, 13thEdition 2013 .
Data structure using C”, AM Tanenbaum, Y Langsam & MJ
Augustein, ISBN 9788131702291, Pearson Prentice Hall India,
9th Edition 2009.
Data is collection of raw facts.
Data Structure is representation of the
logical relationship existing between
individual elements of data.
In other words, a data structure is a way of
organizing all data items that considers not
only the elements stored but also their
relationship to each other.
Algorithm is a set of instructions written to
carry out certain tasks & the data structure
is the way of organizing the data with their
logical relationship retained.
To develop a program of an algorithm, we
should select an appropriate data structure
for that algorithm.
Program = Algorithm +Data Structure
Data structure are normally divided into
two broad categories:
• Primitive Data Structure
• Non-Primitive Data Structure
Data structure
Primitive DS Non-Primitive DS
Integer
Integer Float
Float Character Pointer
Non-Primitive DS
Linear List Non-Linear List
Array Queue Graph Trees
Link List Stack
Different Searching and Sorting Techniques
Static:
Array
Dynamic: Linked list
Types of LL & operations on it
A stack is also an ordered collection of elements like arrays, but it
has a special feature that deletion and insertion of elements can be
done only from one end called the top of the stack (TOP).
Due to this property it is also called as last in first out type of data
structure (LIFO).
Can be implemented using both arrays and linked list.
Like Stack of plates.
Queue are first in first out type of data structure (i.e. FIFO)
In a queue new elements are added to the queue from one end called
REAR end and the element are always removed from other end called the
FRONT end.
Can be implemented using both arrays and linked list.
The people standing in a railway reservation row are an example of
queue.
Difference in linear and non-linear data structure, trees
and binary trees-concept and terminology, binary tree
as an ADT(Abstract Data Type), algorithm for tree
traversals (recursive and non recursive), conversion of
general tree to binary tree, binary search trees,
concept of threaded binary tree, threaded binary tree
as ADT, preorder, in order traversals of threaded binary
search tree. A
B C D
E F G
H
BST & converting tree to binary tree, creating BT using LL
Tree is non-linear type of data structure in which data items
are arranged or stored in a sorted sequence.
Tree represent the hierarchical relationship between various
elements. 20
9 40
5 15 35 60
80
Threaded BT & preorder and post order traversal
Set Representation : Trees can be used to represent
disjoint sets and perform operations like union and find
on the set efficiently.
Game Trees: Trees are widely used in playing games
using computers. Games such as tic-tac-toe, chess etc
use trees. A tree is used to identify current status and
plan strategies so as to make the “best” move.
Decision Making : A binary tree is very useful when two-
way decisions have to be made.
Searching : Search trees are very widely used to store
record keys and search them in an efficient manner.
Data Encoding : Binary trees are used to encode large
volumes of data using the Huffman Coding algorithm.
Sorting: A sorting method called “Heap Sort” is based on
the binary tree structure.
Graph as an ADT, representation of graphs using adjacency
matrix, adjacency list, Depth First Search and Breadth First
Search, algorithms for minimal spanning tree (Prim’s and
Kruskal’s )and shortest path- Dijkstra’s algorithm , application
of these algorithms.
V1
G1= (V,E)
V = { V1, V2 V3, V4}
V2 V4 E = { ( V1, V2), (V2, V3) }
(V3 , V4), (V4, V1) }
V3
G1
V1 V1 V1
V2 V4 V2 V3 V2 V3
V3 V4
V4 V5 V6 V7
G2 G3 G4
Representation of electric circuits. Calculation
of current flows, voltage drops at various
points in the circuits.
Maps indicating connectivity and distances
between different places.
Telephone and computer networking.
Routing from one location to another.
Computing project completion time, delays,
early start and late finish times for a project,
which is made up of several tasks.
Notionof symbol table, AVL (Adelson-Velskii
and Landis) Trees, heap data structure its
application in heap sort.
Linked List concept can be used to deal with many practical
problems.
Problem 1:
Suppose you need to program an application that has a pre-
defined number of categories, but the exact items in each
category is unknown.
Solution:
Pre-defined number of categories implies that we can
use a simple static structure like array to represent the
categories. Since we do not know the number of items
in each category, we can represent items in each
category using a linked list. So what we need is an array
of linked lists
A simple real life example is a Train, here each coach is
connected to its previous and next coach
Our brain is also a good example of linked list. E.g Consider the
thinking process when you placed your bike key somewhere and
couldn't remember.
dynamic queues / stacks are efficiently implemented using linked
lists.
history section of web browsers
common sighted example is low level memory management (i.e.
the heap as managed by malloc in C or new in Java, etc)
Hash tables that use chaining to resolve hash collisions typically
have one linked list per bucket for the elements in that bucket.
Program 2: Use function to Create
delete and display –array
Note use array variable = arr
Two functions = Create delete and
Display
Program 2: Use function to Create
delete and display –array
Note use array variable = arr
Two functions = Create delete and
Display
Note: use size of array: ‘size’ as global
varibale