INTRODUCTION
Data Structures
Topics covered
Data and Information Data structure vs. File Organization
Data Structure Operations on Data Structure
Classification of Data Structures Algorithm
Primitive Data Types Importance of Algorithm Analysis
Abstract Data Types Complexity of an Algorithm
Short description about all DS Asymptotic Analysis and Notations
Big O Notation
Big Omega Notation
Big Theta Notation
Rate of Growth and Big O Notation
Data and Information
Data Information
Raw values Data with context and meaning
Unorganized Processed data (calculations, sorting,
grouping, making decisions)
Plural of word “datum”
Organized data
Refers to a value
Structured data
Facts, statistics and figures
Useful for decision making
Ex. Numbers, words, alphabets, sounds,
pictures Conclusion can be drawn after applying rules
Yes, no, no, yes, yes Ex. Avg(marks) of students, merit list of a
college
12, 34, 5, 32,56, 8,
Data and information
Processing
Data ( Context + Information
Meaning)
Example
34, 45, 30, 70, 60, 67
Information
Marks of students ( marks of
students in
ascending
order)
Sorting in ASC order
Example
24, 25, 28, 32, 30, 38
Temp of a city
AVG
Temp of
the city
Calculate AVG Temp
Questions
With reference to the previous slide-
Which is Data?
Which is Context?
Which is Processing?
Which is information?
After getting information where the arrow is going?
Data + Processing=Information + Rules = Knowledge + Action/Decision = Wisdom
Data vs Information vs knowledge
Wisdom
Knowledge
Information
Data
Data -> Information -> Knowledge -> Wisdom( follow the path)
Topics Covered
Data Structures
Definition 1 : Data Structure is a way of storing data in the computer’s memory so that is can
be used efficiently.
Definition 2 : Data Structure is a logical or mathematical model of organization of data.
DS
using
C
DS
using
CPP
DS needs ADT to be selected
DS
DS allows to perform variety of operations on data using
Python
These operations are designed to perform efficiently .
i.e. in less time, space and memory DS
using
It has several types. JAVA
Classification of DS
integer
float
Primitive
Characters
Array
Boolean
List
DS
Linear
Stacks
Queues
Non Primitive
Tree
Graphs
Non Linear
Tables
Sets
Classification of DS
Different ways to classify Data Structures
Primitive and Non Primitive
Linear and Non Linear
Homogenous (same types for all -array ) and Heterogenous (different types of
element together – structure in C )
Static and Dynamic
ADT (Abstract Data Type)
Abstract + Data Types
Abstract- independent of implementation / behaviour
Data types- types of the value / data with set of operations allowed on that set of
values.
Hence ADT’s are the special data types whose behaviour is defined by set of values
and operations with details hidden.
Examples
Linked list
Stack
Queue
Array
Tree
HashTable
ADT and DS
An abstract data type (ADT) is basically a logical description or a specification of
components of the data and the operations that are allowed, that is independent of
the implementation.
ADT encapsulates the set of values and operations permitted on those values,
Details of operations is hidden from outside program. Operation is defined but its
implementation is not specified.
Whereas in DS ADT is implemented. DS has real time values and operations of ADT
are implemented with the help of programming language.
We can say that ADT is logical representations of data and DS in implementations of
ADT
Example- Linked List is ADT with operations addNode, removeNode, Search, Update
operations. When we implement this concept using any programming language, we
implement all operations of ADT. Hence Linked List in C/ Python is a DS.
A[1] A[3]
Array as a DS A[2] A[4] A[n]
Linear DS (physical memory arrangement )
Homogeneous
Finite number of data elements
Size of an array = ub – lb + 1
Types
Single dimensional
Multi dimensional
Element can be accessed using index
If array A with n elements is assumed then
A[1], A[2], A[3], A[4], A[5], A[6],……….., A[n]
Linked list as DS
Linear data arrangement ( logically linear)
Data is stored in node
Node contains the pointer to next or previous next both nodes.
Beginning of the list is maintained by special pointer variable to hold address of first
node
next • Element 1
next • Element 2
next • Element 3
Stack as DS
Linear
LIFO in behaviour (Last In First Out)
Element added / removed from only one end called top.
Two operations
Push - add element
Pop – remove element
In Out
Queue as DS
Linear
FIFO in behaviour
elements added at rare and removed from front
Two operations
Insert
Delete
Tree as DS
Non linear DS
Used to represent hierarchical relationship
Referred as parent child relationship
A
B C D
E G H
F K I
J
Graph as DS
Non Linear DS
Used to represent non hierarchy relationship
Can be used for maps
Vertex
A
D
B
Edge
C
Questions
Distinguish between data and information
List the types of DS.
Define data type.
Give the ADT for an array.
Why we need DS?
Discuss the ADT for List.
Why ADT is called as logical representation?
In real world/computer applications where stack and queue is
applicable/used?
DS vs File Organization
DS File Organization
Data structure is way storing data in a File organization is a study storing data
computer’s memory so that it can used records in a file.
efficiently.
Types of file organization are sequential,
Types of DS are primitive, non-primitive, linear, random, indexed
non-linear, static, dynamic
To access data in DS, we need to use its set of To access files we need to take help of
operations. system calls
These are assumed as they are in RAM Theses are assumed as they are on disks.
Operation on DS
Insertion • Adding a new element into the data structure
Deletion • Removing an element from the data structure
Traversing • Accessing each element exactly once
Searching • Finding the position of desired element
Merging • Combining two or more lists
Splitting • dividing single into multiple
Copying • Creating duplicate copy
Sorting • Arranging elements in ascending or descending order
Algorithm
Finite set of well defined steps designed Well
to solve a particular problem. defined
input
Characteristics Well
Definit
Input defined
e output
Output
Process
Finiteness
Effectiveness Algorith
Unambiguous Un m
ambiguou
Proces
Feasible
s s
Definite
Feasibl Finite set
of
e operations
Questions
Describe the difference between file organization and DS.
Describe different operations that can be performed on DS
Define an algorithm.
Explain characteristics of an algorithm.
Write an algorithm for following problems
Importance of an algorithm analysis
Why to do analysis?
There are different ways available to solve
a problem.
To make choice from available solutions
It helps to choose efficient algorithm for
problem
Factors to consider for making choice
1. Programming requirements
2. Time requirements
3. Space requirements
Complexity of an algorithm
Space complexity Time complexity
Types of complexity
Worst Case Best Case Average Case
Running time is longest for Running time is shortest for Running time is between
all inputs all inputs best case and worst case
The key operation is
The key Operation executed
executed minimum number Difficult to find
maximum number of times
of times
Upper bound of
complexity / domains
Asymptotic Analysis and Notations
Asymptotic notations used to measure the complexity of an algorithm
Big O
Big ᘯ(omega)
Big Theta (θ)
Little ᘯ(omega)
Little Theta (θ)
Big O notation
Definition:
iff there exists constants c and n0 such
that:
Thus g(n) is upper bound of f(n)
Considered as worst case complexity.
Big O example
Let f(n)=2n+10, n
1
f(n)=2n+10 g(n)=3n f(n)<=g(n)
12 3F
2 14 6F
g(n)=n, 3 16 9F
4 18 12 F
f(n)=O(g(n)) 5 20 15 F
6 22 18 F
iff f(n)<=c*g(n) 7
8
24
26
21 F
24 F
9 28 27 F
where c=3, n0 10 30 30 T
11 32 33 T
n0=10 for all n>=n0 12 34 36 T
13 36 39 T
14 38 42 T
15 40 45 T
16 42 48 T
17 44 51 T
18 46 54 T
19 48 57 T
20 50 60 T
How to get f(n) or g(n) Function rank / names
f(n) or g(n)
Big ᘯ(omega) notation
Definition:
iff there exists constants c and n0 such
that:
Thus g(n) is lower bound of f(n)
Considered as best case complexity.
Big ᘯ(omega) example
Let f(n)=100n2+3n+2,
n f(n)=3n+2 g(n)=n*n f(n)>=g(n)
g(n)=n 2
1 105 3 T
f(n)=O(g(n)) 2 408 12 T
3 911 27 T
iff f(n)>=c*g(n)
4 1614 48 T
where c=3, 5 2517 75 T
n0=1 for all n>=n0 6 3620 108 T
7 4923 147 T
8 6426 192 T
9 8129 243 T
10 10032 300 T
Big Theta (θ) notation
Definition:
iff there exists constants c1, c2 and n0
such that:
Thus it is noted that iff
and
Big θ(theta) notation example
Rate of growth of complexity with input size
As input size increases, complexity of 3n2+5n+7
f(n) increases.
N3+8
This growth can be examined by
comparing f(n) with some standard Log(n)+8
functions like log2n, n,n2, n3, 2n.
Questions
Describe the difference between file organization and DS.
Describe different operations that can be performed on DS
Define an algorithm.
Explain characteristics of an algorithm.
Write an algorithm for following problems
Definitions
Data
Information
Data structures
Abstract Data Type
Algorithm
Complexity of an algorithm
Big o notation
Big ᘯ(omega) notation
Big θ(Theta) notation
