Unit 1
Data Structures:-
Organized Collection of data
in a particular format called data Structure
(or)
Data Structure is a
Systematic way to organize data in order to use it efficiently.
There are many ways of
organizing the data in a memory like array, stacks, queues, linked list etc.
Array which stores the elements in a Continuous manner.
The data structure is not any
programming language like c, c++ , java etc. It is a set of algorithms that we
can use in any programming language to structure the data in the memory.
To Structure the data is
memory, ‘n’ number of algorithms were proposed and all those are known as
“Abstract data type” Those Abstract data type are the set of Rules.
The following terms are the foundation terms
of the data structure
Interface
Implementation
Interface:-
Each data structure has an
Interface.
Interface represents “set of
operations” that a data structure supports. An Interface only provides the list
of supported operations, the type of parameters they can accept, and the return
type of these operations.
Implementation:-
Implementation provides the
definition of the algorithm used in operations of the data structure.
Types of Data Structures
(or)
Classification of Data Structures
Types of Data Structures:-
There are two types of data
Structures.
Primitive Data Structure
Non-Primitive Data Structure
Primitive Data Structure:- A
Primitive Data Structure is a basic type of data structure that is directly
operated upon by the machine-level instructions, and those data structures are
simple and Pre-defined.
Ex:-int, float, char etc.
Non-Primitive Data
Structure:-A non-Primitive Data Structure is a more complex data structure that
is built using primitive data types. These are used to store multiple values
and are not directly operated upon by machine-level instructions.
Ex:-arrays etc.
The non-primitive data
structure is classified into 2 types, they are:-
Linear data Structure:- In
linear data structures, where data elements are arranged sequentially or
linearly, where each and every element is attached to its previous and next
adjacent is called a linear data structure.
Ex: array, stack, queue, linked list, etc.
Arrays: it is a collection of
homogenous data elements.
Stacks: it is a linear data
structure in which data added at the last will be removed at the first.
Queue: it is a linear data
structure in which elements added at the first and removed at first.
Linked List: it is a
collection of NODES that are made up of two parts, i.e data and address of next
node.
Non-Linear Data Structure:-
In non-linear data structure, where data elements are not arranged sequentially
on linearly are called as non-linear data structure.
Ex:Trees, Graph.
Trees: it is a collection of
NODES where the nodes are arranged hierarchically and from a parent-child
relationship.
Graphs: it is a collection of
finite numbers of vertices and edges.
Static Data Structure:-
In static data structure the
size of the structure is fixed.
The content of data structure
can be modified but without changing the memory pace allocated to it
Ex: array.
|
40 |
55 |
63 |
17 |
22 |
68 |
89 |
97 |
89 |
0 1 2 3 4 5 6 7 8
Dynamic Data Structure:-
In Dynamic data structure the
size of the structure is not fixed and can be modified during the operations
performed on it.
Dynamic data structures are
designed to facilitate change of data structure in the run time.
Ex: Linked List
Basic Terminology in Data Structure
Data structures are the
building blocks of any program on the software.
Following terminology is used in the data structure
Data:-Data can be defined as
the collection of values.
Group item:-Data items which
leave subordinate data item are called group item.
Ex:-The name of a student can
be left as first name & last name
Record:- Record can be
defined as the collection of various data items.
Ex:- If we talk about the
student entity, their its name, address, course and marks can be grouped
together to from the record for the student.
File:-A file is a collection
of various records of one type of entity.
Ex:- If there are 60 students
in the class, then there will be 20 records in the related file where each
record contains the data about each student.
Attribute &Entity:-An
entity represents the class of certain objects.
It contains various
attributes. Each attribute represents the particular property of that entity.
Filed:-A single elementary
unit of information represents the attribute of an entity.
Operations of Data Structure
Insertion:- Insertion can be
defined as the process of adding the elements to the data structure at any
location.
Deletion:-The process of
removing an element from the data structure is called deletion.
Traversing:-Traversing the
data structure means visiting each element exactly once.
Searching:-The process of
finding the location of an element written in the data structure is called
searching.
Merging:-Combining the two
different lists into single list is called Merging.
Advantages of Data Structure
Following are some advantages
of data structure
Efficiency:-Efficiency of a
program depends upon the choice of data structure.
Data structure helps in
efficient storage of data in the storage device.
Data structure provides
effective and efficient processing of small as well as large amount of data.
Reusability:- Data structures
are reusable i.e. once we leave implemented a particular data structure we can
use it at any other place.
Abstraction:- Data structure
is specified by the ADT which provides a level of abstraction.
The client program uses the
data structure through interface only without getting into the implementation
details.
Data Structure and Algorithm
Algorithm:- An algorithm is a
step by step procedure to solve a given problem.
It is not the complete
Program or code, it is just a solution (logic) of a problem, which can be
represented either as an informed description using a flowchart or pseudocode.
Specification of
Algorithm:-Which refers to the process of clearly defining an algorithm. It
involves derailing the steps or rules. That describe how to solve a problem.
Input:-An algorithm has some
input values, we can pass some input value to an algorithm.
Output:- We will get one or
more output at the end of an algorithm.
Definiteness:-An algorithm
should be unambiguous which means that the instructions in an algorithm should
be clear and simple.
Finiteness:-An algorithm
should have finiteness means that the algorithm should be countable.
Effectiveness:- An algorithm
should be effective as each instruction inan algorithm affects the overall
process.
Language Independent:- An
algorithm must be language independent so
that instruction can be
implemented with the same output.
Example:- Algorithm to add 2
numbers.
Step 1:- Start
Step 2:- read a,b
Step 3:- perform c=a+b
Step 4:- Print c
Step 5:- Stop
Performance Analysis:-
Performance analysis involves studying the efficiency of an algorithm in terms
of time and space it seeks to predict how an algorithm will perform based on
the size of the input data.
Key aspects of performance analysis
include:-
1. Time Compexity:- Time
complexity of an algorithm is the totral amount of time required by an
algorithm to complete its execution .
Common Time Complexities are:-
|
Constant time (0(1)) |
Execution time does not
depend on the input size eg:-accessing an
element in an array |
|
Logarithmic Time (0(log n)) |
Execution time grows
logarithmically with input size eg:- Binary
search |
|
Linear Time (0(n)) |
Execution time grows
linearly with input size eg:- Traversing
anarray |
|
Linearithmic Time (0(n log n)) |
A combination of linear
& logarithmic growth eg:- Merge sort or
quick sort |
|
Quadratic Time (0(n2)) |
Execution time grows
quaratically with input size eg:-nested loops |
|
Cubic Time (0(n3)) |
Execution time grows
cubically with input size eg:- matrix multiplication |
|
Exponential Time (0(2n)) |
Execution time doubles with
each additional input size eg:- solving the TSP Problem |
|
Factorial Time (0(n!)) |
Execution time grows as the
factorial of input size eg:- generating
all permutations of a set. |
2. Space Complexity:- This
refers to the amount of memory an algorithm uses relative to the size of the
input.
(or)
Total amount of computer
memory required by an algorithm to complete memory required by an algorithm to
complete its execution is called as space complexity of the algorithm
3. Asymptotic Analysis:-
Analyzes how an algorithm behaves as the input size increases. It can determine
the best, worst and average case performance.
We use Three types of
asymptotic notations majorly
Big ⃝ –oh
Big θ – Theta
Big Ω - Omega
Big ⃝:- Big-oh notation is
used to define the upper bound of an algorithm in terms of time complexity
which always indicates the maximum time required by an algorithm for all input
valve Big-oh notation describes the worst case of an algorithm time complexity.
We can represent Big-oh function as follows:
Consider the function f(n) as
time complexity of an algorithm and g(n) is the most significant term. if
f(n)<=Cg(n) for all n>=no, C>0 and n0>=1. Then we can represent as
follows:
f(n)=O(g(n))
Big θ :- Theta notation is
used to define the average bound of an algorithm in terms of time complexity
which always indicates the average time required by an algorithm for all input
values.
We can represent Big Theta
function as follows:
Consider the function f(n) as
time complexity of an algorithm and g(n) is the most significant term. If
C1g(n)<=f(n)<=C2g(n) for all n>=n0,C1>0,C2>0 n0>=1.Then we
can represent as follows:
f(n)=
θ(g(n))
Big Ω :- Omega notation is
used to define the lower bound of an algorithm in terms of Time Complexity
which always indicates the minimum time required by an algorithm for all input
values.
We can represent Big Omega
function as follows:
Consider the function f(n) as
time complexity of an algorithm and g(n) is the most significant term. If
f(n)>=Cg(n) for all n>=n0,c>0 and n0>=1. Then we can represent as
follows:
4. Best, worst and Average
case Analysis:-
Best case Analysis:- Examines
the scenario where the algorithm performs optionally (typically, the smallest
input or simplest case)
Average case Analysis:-
Calculates the expected performance across many random inputs. It is more
complex to compute but can give a better idea of real world performance.
Worst case Analysis:- looks
at the maximum amount of time or space the algorithm might take
Performance Measurement of an
Algorithm :-
Performance measurement is
the process of evaluating an algorithm by actually executing it on various
inputs. Unlike performance analysis, f(n)=Ω(g(n)) performance measurement
focuses on Real-world data and gives insights into how well an algorithm
performs under practical conditions.
1. Benchmarking :- It
involves running an algorithm on different sets of inputs and measuring the
time and memory usage
2. Profiling :- in identify
which parts of the algorithm consume the most time or memory during execution.
Eg:- Profiling might show that a certain loop or function takes a
disproportionate amount of time, or that a specific data structure is consuming
excessive memory.
3. Real-World Testing :-
Beyond just theoretical or synthetic inputs, real-world testing involves
running the algorithm on actual data or scenarios it is expected to handle .
This is where you can see how the algorithm behaves under real-world
conditions, including large datasets & unexpected inputs.
4. Scalability Testing :-
Testing how well the algorithm scales with increasing input sizes is crucial.
5. Comparative Testing :-
Comparing the performance of different algorithms solving the same problem can
help determine which one is most efficient for a given use case.
6. Hardware and Environmental
Factors :- The performance of an algorithm influenced by the environment it
runs in such as the hardware (CPU, RAM, Storage speed)& the software environment(operating
system)
Recursion :-
A function that calls by
itself again and again is Known as recursion function
Syntax :- return type
recursive function name (arguments/parameters);
Ex:- int factorial(int x)
{
if(x==0)
{
return 1;
}
else
{
Return (x*factorial(n-1));
}
}
Advantages of recursion :-
Recursion reduces length of
code.
Recursion reduces the
unnecessary calling of function
Recursion is very useful in
solving data structure problem.
We can solve the problem by
using simple way
In recursion code is simple
and short than iterative code.
Disadvantages of recursion :-
Recursion programs are
generally shown than iterative
Recursion program requires
memory
Recursion uses more CPU
processing time
Recursion programs are a bit
difficult to understand and debug.
Applications of recursion :-
1. To compute factorial of a
number
2. Tower of Hanoi
3. All searching techniques
uses recursive techniques
4. Candy crush game uses
recursion
5. We use recursion to
determine whether a string is palindrome or not.
6. Stack uses recursion
technique
Types of Recursions :-
There are 2 types of recursions they are
:
1. Direct Recursion
2. Indirect Recursion
1. Direct Recursion :- If a
function explicity call same function by
itself then that type of
recursion is called as direct recursion.
Ex:- int func(int n)
{
if(n==0)
return n;
else
return n+func(n-1)
}
2. Indirect Recursion :- If a function calls another function which
again calls the original function then that type of recursion is called indirect
recursion .
Ex:- int fun 1(int n)
{
if(n==0)
return n;
else
return fun 2(n);
}
Int func 2 (int x)
{
Return x+func 1(x-1);
}
Recursion Technique Example :-
There are 3 types of recursive technique are :-
1. Greatest common
Divisor(GCD)
2. Factorial of a number.
3. Fibonacci number.
1. Greatest common Divisor:-
In this program it is helpful to classify the greatest common factor between
two numbers is called as greatest common factor
Eg:- The gcd of 15am 5 is 5
since both the numbers can be divided by 5, the condition is that the numbers
should be non-zero .
//Program to find GCD of two numbers.
#include<stdio.h>
#include<conio.h>
int gcd(int, int);
void main()
{
int a,b,result;
clrscr();
printf(“enter a and b\n”);
scanf(“%d%d”,&a,&b);
result = gcd(a,b);
printf(“GCD of %d and %d is
%d”, a,b,result);
getch();
}
int gcd (int p, int q)
{
If(q==0)
{
Return P;
}
else
{
return(gcd(q,p%q));
}}
Output:-
Enter a and b
40 60
GCD of 40 and 60 is 20
2. Factorial of a number :-
It is helpful to find the product of all positive integers less than or equal
to n.
Ex:-5*4*3*2*1=120
5! = 120.
//Program to find factorial of number.
#include<stdio.h>
#include<conio.h>
int fact(int);
void main()
{
int n,f;
printf(“enter n value “);
scanf(“%d”,&n);
f=fact(n);
printf(“factorial is %d”, f);
getch();
}
Int fact(int n)
{
If(n==0)
Return(1);
Else
Return(n*fact(n-1));
}
3. Fibonacci series :- The Fibonacci series is a sequence of
numbers where each number is the sum of the two proceeding ones , starting with
0 and 1 . The sequence typically begins as :-
0,1,1,2,3,5,8,13,21,34,......
//Program to find nth Fibonacci number
#include<stdio.h>
#include<conio.h>
{
if(n==1||n==2)
return 1;
else
return fibo(n-1)+fibo(n-2);
}
int a,b;
printf(“enter a number”);
scanf(“%d”,&a);
b=fibo(a);
printf(“%d th Fibonacci
number is %d\n”,a,b);
return 0;
}
Comparision between Iterative and
Rcursion:-
|
Recursion |
Iterative |
|
1.Recursion can be defined
as a function called by itself repeatedly |
1. Iteration can be defined
as when a loop repeatedly executes a set of instructions until the condition
becomes false |
|
2.Recursion is a process always
applied to a function |
2.Iteratio is applied to
the set of instructions which we want to get repeatedly executed the statements
in loop |
|
3.Recursion reduces the
size of code |
3.Iteration makes code
longer |
|
4.Recursion is slow in execution |
4.Iteration is fact in
execution |
|
5.A Conditional statement decides
the termination of recursion |
5.Control variable value decides
the termination of iteration statements |
|
6.The stack is used to implement
the recursion |
6.Iteratiion does not we
stack. |
|
7.Infinite recursion can
lead to system crash. |
7.Infinite loops use CPU
cycles repeatedly |
|
8.Recursive function is
easy to write |
8.Iteration function
statements are bit harder to write |
|
9.Ex:- int gcd(int a, int
b) { If(b==0) { Return a; } Else { Return gcd(b,a%b); } |
9.Ex:- While(condition) { Statement(s); Statement(s); } |