DATA STRUCTURES AND
ALGORITHMS
Department of CCE
Click to add text
INTRODUCTION
DATA SRUCTURE
Data: Raw facts about an objects.
Structure: Way of storing , organising
and manipulating data.
DEFINITION OF DATA STRUCTURE:
Logical (or) Mathematical model of a
particular organisation of data.
How the data should be organised.
How the flow of data should be controlled.
How a data structure should be designed.
A data structure is a particular way of storing and
organizing data in a computer so that it can be used
efficiently
NEED OF DATA STRUCTURE
THREE ACTIVITIES:
Storing,
Accessing,
Manipulating ,
TYPES OF DATA STRUCTURE
Two types of data structures:
they are
1) Primitive data structure.
int , char, float.
2) Non-Primitive data structure.
1. Arrays
2. Structure
3. Stack
4. Queue
5. Linked list
6. Tree
7. Graph
8. Files.
1) ALGORITHMS
1.1 Definition:
An algorithm consists of a set of explicit and
unambiguous, finite steps when carrying out for a
given set of initial condition ,produce corresponding
output and terminate in a finite time.
1.2) Characteristics:
Each instruction should be unique and concise.
Each instruction should be relative in nature and
should not be repeated infinitely.
Repetition of same tasks should be avoided.
The results should be available to the user after the
algorithm terminates.
2) ANALYSIS OF ALGORITHMS
2.1) Steps to be followed:
Analysis is more reliable than experimentation or
testing.
Analysis help to select better algorithms.
Analysis predicts performance.
Analysis identifies scope of improvement of
algorithms.
3) ANALYSIS OF ALGORITHMS USING
DATA STRUCTURES
3.1) Problem solving.
3.2) Top-down design.
3.1) Problem solving
Part of thinking process.
Describes steps to proceed from a given state
to a desired goal state.
3.1.1) Problem solving phases.
3.1.2) Problem solving strategies.
DEFINITION
An effective program should be
developed by one (or) more users to
obtain a solution to a problem is known
as problem solving.
4) PERFORMANCE ANALYSIS
Measured by the amount of resources it
uses the time and the spaces.
▪ Time – number of steps.
▪ Space – number of units memory storage.
4.1) TIME COMPLEXITY
Time complexity is the amount of time
needed by a program to complete its task.
It can be divided into two
1) Compile time.
2) Run time.
Three types of time complexity.
1) Worst-case.
2) Average-case.
3) Best-case.
1) Worst-case:
The function defined by maximum
number of steps taken on any problem of
size(n).
FORMULA:
T(n)=O (f(n))
2)Average-case:
The function defined by average number
of steps taken on any problem of size(n).
FORMULA:
T(n)=theta(f(n))
3) Best-case:
The function defined by minimum
number of steps taken on any problem of
size(n).
FORMULA:
T(n)=omega((fn))
4.2) SPACE COMPLEXITY
Amount of memory consumed by the
algorithm until it completes its execution.
character = 1 unit.
Integer = 2 units.
Float = 4 units.
Three spaces.
Instruction space.
Data space.
5) ASYMPTOTIC NOTATION
NOTATION:
A method used to estimate the
efficiency of an algorithm.
1)Big-oh notation.
2)Big-omega notation.
3)Big-theta notation.
5.1) Big-oh notation:
O-> Order of.
Big-> very large values of “n”.
Used to define the worst-case running
time of an algorithm.
Example: f(n)=O(g(n))
f(n) and g(n) -> positive integer.
5.2)
Big-Omega Notation:
Used to define the best-case
running time of an algorithm.
Example: f(n)=Omega(g(n))
f(n) and g(n) -> positive integer.
5.3)
Big-Theta Notation:
It is in between Big-oh and Big-
omega notations.
Example: f(n)=Theta(g(n))
f(n) and g(n) -> positive integer.
3. Big-Theta Notation 1. Big-oh notation 2. Big-Omega Notation
LIMITATIONS OF ASYMPTOTIC
NOTATION:
Many algorithms are hard to analyze
mathematically.
Big-Oh analysis only tells you how it grows
with the size of the problem not how efficient
of the algorithm is.
