DATA STRUCTURES THROUGH C-2023

UNIT – I: Introduction to Data Structures: Introduction to the Theory of Data Structures, Data
Representation, Abstract Data Types, Data Types, Primitive Data Types, Data Structure and Structured
Type, Atomic Type, Difference between Abstract Data Types, Data Types, and Data Structures, Refinement
Stages.
Principles of Programming and Analysis of Algorithms: Software Engineering, Program Design,
Algorithms, Different Approaches to Designing an Algorithm, Complexity, Big „O‟ Notation, Algorithm
Analysis, Structured Approach to Programming, Recursion, Tips and Techniques for Writing Programs in
“C”.
UNIT – II: Arrays: Introduction to Linear and Non- Linear Data Structures, One- Dimensional Arrays,
Array Operations, Two- Dimensional arrays, Multidimensional Arrays, Pointers and Arrays, an Overview of
Pointers
Linked Lists: Introduction to Lists and Linked Lists, Dynamic Memory Allocation, Basic Linked List
Operations, Doubly Linked List, Circular Linked List, Atomic Linked List, Linked List in Arrays, Linked
List versus Arrays
UNIT – III: Stacks: Introduction to Stacks, Stack as an Abstract Data Type, Representation of Stacks
through Arrays, Representation of Stacks through Linked Lists, Applications of Stacks, Stacks and
Recursion
Queues: Introduction, Queue as an Abstract data Type, Representation of Queues, Circular Queues, Double
Ended Queues- Deques, Priority Queues, Application of Queues
UNIT – IV: Binary Trees: Introduction to Non- Linear Data Structures, Introduction Binary Trees, Types
of Trees, Basic Definition of Binary Trees, Properties of Binary Trees, Representation of Binary Trees,
Operations on a Binary Search Tree, Binary Tree Traversal, Counting Number of Binary Trees, Applications
of Binary Tree
UNIT – V: Searching and sorting: Sorting – An Introduction, Bubble Sort, Insertion Sort, Merge Sort,
searching – An Introduction, Linear or Sequential Search, Binary Search, Indexed Sequential Search
Graphs: Introduction to Graphs, Terms Associated with Graphs, Sequential Representation of Graphs,
Linked Representation of Graphs, Traversal of Graphs, Spanning Trees, Shortest Path, Application of
Graphs.

Syllabus designed by BRAU UNIVERSITY under the premises of APSCHE

Lvr Degree College

 UNIT-1
Introduction to Data Structures:
Data Structure can be defined as the group of data elements which provides an efficient way of storing and
organising data in the computer so that it can be used efficiently. Some examples of Data Structures are
arrays, Linked List, Stack, Queue, etc. Data Structures are widely used in almost every aspect of Computer
Science i.e., Operating System, Compiler Design, Artificial intelligence, Graphics and many more.
For example, we have some data which has, Teacher name "jitin" and age 36. Here "jitin" is of String data
type and 36 is of integer data type.

We can organize this data as a record like Teacher record, which will have both teacher's name and age in
it. Now we can collect and store teacher's records in a file or database as a data structure.

For example: "srinu" 30, "dilip" 31, "ravi" 33.

In simple language, Data Structures are structures programmed to store ordered data, so that various
operations can be performed on it easily. It represents the knowledge of data to be organized in memory. It
should bedesigned and implemented in such a way that it reduces the complexity and increases the
efficiency.

Advantages of Data Structures

Efficiency: Efficiency of a program depends upon the choice of data structures. For
example: suppose, we have some data and we need to perform the search for a
perticular record. In that case, if we organize our data in an array, we will have to
search sequentially element by element. hence, using array may not be very efficient
here. There are better data structures which can make the search process efficient
like ordered array, binary search tree or hash tables.

Reusability: Data structures are reusable, i.e. once we have implemented a

particular data structure, we can use it at any other place. Implementation of data
structures can be compiled into libraries which can be used by different clients.

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.

Lvr Degree College

Data Structure Classification (imp)

*Linear Data Structures: A data structure is called linear if all of its elements are arranged in the
linear order. In linear data structures, the elements are stored in non-hierarchical way where each element
has the successors and predecessors except the first and last element.

Types of Linear Data Structures are given below:

Arrays: An array is a collection of similar type of data items and each data item is called an element of the
array. The data type of the element may be any valid data type like char, int, float or double.

The elements of array share the same variable name but each one carries a different index number known as
subscript. The array can be one dimensional, two dimensional or multidimensional.

The individual elements of the array age are:

age[0], age[1], age[2], age[3],......... age[98], age[99].

Linked List: Linked list is a linear data structure which is used to maintain a list in the memory. It can be
seen as the collection of nodes stored at non-contiguous memory locations. Each node of the list contains a
pointer to its adjacent node.

Stack: Stack is a linear list in which insertion and deletions are allowed only at one end, called top.

A stack is an abstract data type (ADT), can be implemented in most of the programming languages. It is
named as stack because it behaves like a real-world stack, for example: - piles of plates or deck of cards etc.

Lvr Degree College

Queue: Queue is a linear list in which elements can be inserted only at one end called rear and deleted only
at the other end called front.

It is an abstract data structure, similar to stack. Queue is opened at both end therefore it follows First-In-
First-Out (FIFO) methodology for storing the data items.

*Non Linear Data Structures: This data structure does not form a sequence i.e. each item or element
is connected with two or more other items in a non-linear arrangement. The data elements are not arranged
in sequential structure.

Types of Non Linear Data Structures are given below:

Trees: Trees are multilevel data structures with a hierarchical relationship among its elements known as
nodes. The bottommost nodes in the herierchy are called leaf node while the topmost node is called root
node. Each node contains pointers to point adjacent nodes.

Tree data structure is based on the parent-child relationship among the nodes. Each node in the tree can have
more than one children except the leaf nodes whereas each node can have atmost one parent except the root
node. Trees can be classified into many categories which will be discussed later in this tutorial.

Graphs: Graphs can be defined as the pictorial representation of the set of elements (represented by
vertices) connected by the links known as edges. A graph is different from tree in the sense that a graph can
have cycle while the tree can not have the one.

The data structures can also be classified on the basis of the following characteristics:

Characteristics Description
In Linear data structures, the data items are
Linear
arranged in a linear sequence. Example: Array
In Non-Linear data structures, the data items are not
Non-Linear
in sequence. Example: Tree, Graph
In homogeneous data structures, all the elements
Homogeneous
are of same type. Example: Array
In Non-Homogeneous data structure, the elements
Non-Homogeneous may or may not be of the same type.
Example: Structures
Static data structures are those whose sizes and
Static structures associated memory locations are fixed, at
compile time. Example: Array
Dynamic structures are those which expands or
shrinks depending upon the program need and its
Dynamic execution. Also, their associated memory locations
changes. Example: Linked List created using
pointers

Lvr Degree College

Difference between PRIMITIVE and NON-PRIMITIVE

Primitive data structure Non-primitive data structure

Primitive data structure is a kind of data Non-primitive data structure is a type of data
structure that stores the data of only one structure that can store the data of more than one
type. type.

Examples of primitive data structure are Examples of non-primitive data structure are Array,
integer, character, float. Linked list, stack.

Primitive data structure will contain some Non-primitive data structure can consist of a NULL
value, i.e., it cannot be NULL. value.

The size depends on the type of the data In case of non-primitive data structure, size is not
structure. fixed.

It starts with a lowercase character. It starts with an uppercase character.

Primitive data structure can be used to call Non-primitive data structure cannot be used to call
the methods. the methods.

Difference between DATA TYPE and DATA STRUCTURE

DATA TYPE DATA STRUCTURE

Data Type is the form of a variable which is being
Data Structure is the collection of different kinds
used throughout the program. It defines that the of data. That entire data can be represented using
particular variable will assign the values of thean object and can be used throughout the entire
given data type only program.
Implementation through Data Types is a form of Implementation through Data Structures is called
abstract implementation concrete implementation
Can hold values and not data, so it is data less Can hold different kind and types of data within
one single object
Values can directly be assigned to the data type The data is assigned to the data structure object
variables using some set of algorithms and operations like
push, pop and so on.
No problem of time complexity Time complexity comes into play when working
with data structures
Examples: int, float, double Examples: stacks, queues, tree

Lvr Degree College

ATOMIC DATA TYPES(imp)
An instance of an atomic data type is a single, indivisible unit of data. The following table lists the atomic
types currently available.

Data Type Description Example

INTEGER An integer between -2^31 to 2^31-1. 2147483647

LONG An integer between -2^63 to 2^63-1. 9223372036854775807

FLOAT A single precision IEEE 754 floating point 100.1234567

number.

DOUBLE A double precision IEEE 754 floating point 100.12345678901234

number.

NUMBER An arbitrary-precision signed decimal number 100.123456789

(equivalent to the Java Big Decimal type).

STRING A sequence of zero or more unicode characters. "Oracle"

BOOLEAN Has only two possible values. TRUE and FALSE. TRUE

ABSTRACT DATA TYPES(imp)

An abstract data type is an abstraction of a data structure that provides only the interface to which the data
structure must adhere. The keyword “Abstract” is used as we can use these datatypes, we can perform
different operations. But how those operations are working that is totally hidden from the user. The ADT is
made of with primitive datatypes, but operation logics are hidden.
Some examples of ADT are Stack, Queue, List etc.
A Stack is implemented using linked list-based Stack, array-based Stack, A queue is
implemented using linked list-based queue, array-based queue, List is an abstract data type
that is implemented using a dynamic array and linked list.

Abstract data type model

Before knowing about the abstract data type model, we should know about
abstraction and encapsulation.

Abstraction: It is a technique of hiding the internal details from the user and only
showing the necessary details to the user.

Encapsulation: It is a technique of combining the data and the member function in a

single unit is known as encapsulation.

Lvr Degree College

The above figure shows the ADT model. There are two types of models in the ADT
model, i.e., the public function and the private function. The ADT model also contains
the data structures that we are using in a program. In this model, first encapsulation
is performed, i.e., all the data is wrapped in a single unit, i.e., ADT. Then, the
abstraction is performed means showing the operations that can be performed on the
data structure and what are the data structures that we are using in a program.

DIFFERENCE BETWEEN ABSTRACT DATA TYPES, DATA TYPES, AND DATA STRUCTURES

Abstract Data Type Data Structure Data Type

Abstract Data Types or Concrete data types or structures Data Type is the form of a
structures describe the data and provide how these operations variable which is being used
the operations to manipulate and are actually implemented. throughout the program
change it.
Most of the program becomes Which is not possible in Can hold values and not data, so
independent of the abstract data Concrete Data Types or structure it is data less
types representation, so it can be (CDT)
improved without breaking the
program.
It’s easier for each part of a It is not so efficient compared to Values can directly be assigned
program to use an ADT. to the data type variables
implementation of its data types
and that will be more efficient.
Implementation of a high level Implementation of a simple Implementation through Data
concept concept Types is a form of abstract
implementation
It hides the internal details. It doesn’t hide anything. It defines that the particular
variable will assign the values of
the given data type only
It uses class. It uses structure. No problem of time complexity
Examples- stacks,queues,list Examples-Arrays, linked lists, Examples: int, float, double
trees, graphs.

REFINEMENTSTAGES
 The best approach to solve a complex problem is to divide it into smaller parts such thateach part
becomes an independent module which is easy to manage. An example of thisapproach is the System
Development Life Cycle (SDLC) methodology.
 This helps in understanding the problem, analyzing solutions, and handling the problemsefficiently.

Lvr Degree College

  The principle underlying writing large programs is the top-down refinement. Whilewriting the main
program, we decide exactly how the work will be divided into variousfunctions and then, in the
refinement process.
 Itis further decided what will be the task of each function, and what inputs are to be givenand results
to be obtained. The data and the actions of the functions are specifiedprecisely.
 Similarly, the purpose of studying Abstract data types is to find out some general principles that will
help in designing efficient programs.
 There exists a similarity between process oftop-down refinement of algorithmsand the top-down
specification of the data structures. In algorithm design, we begin with the problem and slowly
specify more details until we develop a completeprogram. In data specification, we begin with the
selection of mathematical conceptsand abstract data types required for our problem, and slowly
specify more details until finally we can describe our data structures in terms of programming
language.
 The application or the nature of problem determines the number of refinement stages required in the
specification process.
There are 4 levels of refinement process
1. Conceptual or abstract level
2. Algorithmic or data structures
3. Programming or implementation
4. Applications
1.Conceptual Level
 At this level we decide how the data is related to each other, and what operations are needed.
 Details about how to store data and how various operations are performed on that data are not
decided at this level.
2.Algorithmic or Data Structure Level
At data structure level we decide about the operations on the data as needed by our problem for example,
we decide what kind of data structure will be required to solve the problem- contiguous list willbe preferred
forfinding the length of a list, or for retrieving any element, whereas for the evaluation of any expression
into prefix or postfix, stacks will be used.
3.Programming or Implementation Level
At implementation level, we decide the details of how the data structure will be represented in the computer
memory.
For example, we decide whether the linked lists will be implemented with pointers or with the cursors in an
array.
4.Application Level
This level settles all details required for particular application such as names for variables or special
requirements for the operations imposed by applications.

 SOFTWARE ENGINEERING (imp)

 Software engineering is the theory and the practice of methods helpful for the construction and
maintenance of large software systems. Development of a good software is a tedious process which
continues for long time before the software or program takes the final shape and is put into use.
 There are many stages in the software development cycle. The process is often referred to as
software development lifecycle (SDLC). In SDLC, the output from one stage becomes the input to
the next stage.
Lvr Degree College
  In the simplified version. the software development life cycle may contain requirement analysis.
design, implementation and maintenance phases which are implemented in sequence over a period of
time.

 PROGRAM DESIGN

Every computer program is built from components, data, and control.

For a single-user application (used by one person at a time), which normally reads data, saves it in a data
structure, computes on the data, and writes the results, there is a standard way of organizing the component
structure, data structure, and control structure:

1. First, design the program's component structure with three components, organized in a model-view-
controller pattern.
2. Next, decide what form of data structure (array, table, set, list, tree, etc.) will hold the program's
data. The data structure will be inserted in the program's model component.
3. Then, write the algorithm that defines the execution steps --- the control structure. The algorithm
will be placed inside the program's controller.
4. Determine the form of input and output (disk file, typed text in a command window, dialogs, a
graphical-use interface, etc.) that the program uses. This will be embedded in the program's view.

Once the four-step design is finished, then it is time to convert the design into coding.

 ALGORITHMS(imp)
Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to
get the desired output.

Characteristics of an Algorithm
Not all procedures can be called an algorithm. An algorithm should have the following characteristics −
 Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases), and
their inputs/outputs should be clear and must lead to only one meaning.
 Input − An algorithm should have 0 or more well-defined inputs.
 Output − An algorithm should have 1 or more well-defined outputs, and should match the desired
output.
 Finiteness − Algorithms must terminate after a finite number of steps.
 Feasibility − Should be feasible with the available resources.
 Independent − An algorithm should have step-by-step directions, which should be independent of
any programming code.

 Different Approaches to Designing an Algorithm (imp)

The algorithms can be classified in various ways. They are:

1. Implementation Method
Lvr Degree College
 2. Design Method
3. Other Classifications

1.Classification by Implementation Method: There are primarily three main categories into which an
algorithm can be named in this type of classification. They are:

1. Recursion or Iteration: A recursive algorithm is an algorithm which calls itself again and
again until a base condition is achieved whereas iterative algorithms use loops and/or data
structures like stacks, queues to solve any problem. Every recursive solution can be
implemented as an iterative solution and vice versa.
Example: The Tower of Hanoi is implemented in a recursive fashion while Stock
Span problem is implemented iteratively.
2. Exact or Approximate: Algorithms that are capable of finding an optimal solution for any
problem are known as the exact algorithm. For all those problems, where it is not possible to
find the most optimized solution, an approximation algorithm is used. Approximate algorithms
are the type of algorithms that find the result as an average outcome of sub outcomes to a
problem.
Example: For NP-Hard Problems, approximation algorithms are used. Sorting algorithms are
the exact algorithms.
3. Serial or Parallel or Distributed Algorithms: In serial algorithms, one instruction is executed
at a time while parallel algorithms are those in which we divide the problem into subproblems
and execute them on different processors. If parallel algorithms are distributed on different
machines, then they are known as distributed algorithms.

2.Classification by Design Method: There are primarily three main categories into which an algorithm
can be named in this type of classification. They are:
1. Greedy Method: In the greedy method, at each step, a decision is made to choose the local
optimum, without thinking about the future consequences.
Example: Fractional Knapsack, Activity Selection, Dijkstra algorithm.
2. Divide and Conquer: The Divide and Conquer strategy involves dividing the problem into
sub-problem, recursively solving them, and then recombining them for the final answer.
Example: Merge sort, Quicksort.
3. Dynamic Programming: The approach of Dynamic programming is similar to divide and
conquer. The difference is that whenever we have recursive function calls with the same result,
instead of calling them again we try to store the result in a data structure in the form of a table
and retrieve the results from the table. Thus, the overall time complexity is reduced.
“Dynamic” means we dynamically decide, whether to call a function or retrieve values from
the table.
Example: 0-1 Knapsack, subset-sum problem .
4. Linear Programming: In Linear Programming, there are inequalities in terms of inputs and
maximizing or minimizing some linear functions of inputs.
Example: Maximum flow of Directed Graph
5. Reduction(Transform and Conquer): In this method, we solve a difficult problem by
transforming it into a known problem for which we have an optimal solution. Basically, the
goal is to find a reducing algorithm whose complexity is not dominated by the resulting
reduced algorithms.
Example: Selection algorithm for finding the median in a list involves first sorting the list and
then finding out the middle element in the sorted list. These techniques are also
called transform and conquer.

3.Other Classifications : Apart from classifying the algorithms into the above broad categories, the
algorithm can be classified into other broad categories like:

Lvr Degree College

 1. Randomized Algorithms: Algorithms that make random choices for faster solutions are
known as randomized algorithms.
Example: Randomized Quicksort Algorithm .
2. Classification by complexity: Algorithms that are classified on the basis of time taken to get a
solution to any problem for input size. This analysis is known as time complexity analysis .
Example: Some algorithms take O(n), while some take exponential time.
3. Classification by Research Area: In CS each field has its own problems and needs efficient
algorithms.
Example: Sorting Algorithm, Searching Algorithm, Machine Learning etc.
4. Branch and Bound Enumeration and Backtracking: These are mostly used in Artificial
Intelligence.

 Complexity of Algorithm (imp)

The term algorithm complexity measures how many steps are required by the algorithm to solve the given
problem.

The complexity of an algorithm computes the amount of time and spaces required by an algorithm for an
input of size (n). The complexity of an algorithm can be divided into two types. The time complexity and
the space complexity.

There are 2 factors of complexities

1.Time complexity

2.Space complexity

1.Time Complexity
Time Complexity of an algorithm is the representation of the amount of time required by the algorithm to
execute to completion. Time requirements can be denoted or defined as a numerical function t(N), where
t(N) can be measured as the number of steps, provided each step takes constant time.
For example, in case of addition of two n-bit integers, N steps are taken. Consequently, the total
computational time is t(N) = c*n, where c is the time consumed for addition of two bits. Here, we observe
that t(N) grows linearly as input size increases.

2.Space Complexity
Space complexity of an algorithm represents the amount of memory space needed the algorithm in its life
cycle.
Space needed by an algorithm is equal to the sum of the following two components
A fixed part that is a space required to store certain data and variables (i.e., simple variables and constants,
program size etc.), that are not dependent of the size of the problem.
A variable part is a space required by variables, whose size is totally dependent on the size of the problem.
For example, recursion stack space, dynamic memory allocation etc.

 Big-O Notation(imp)
Big-O notation represents the upper bound of the running time of an algorithm. Thus, it gives the
worst-case complexity of an algorithm.
Lvr Degree College
 O(g(n))={f(n):there exists positive constants c and n 0 such that 0<=f(n)<=cg(n) for all n >=n 0}
The above expression can be described as a function f(n) belongs to the set O(g(n)) if there exists a positive
constant c such that it lies between 0 and cg(n) , for sufficiently large n .

For any value of n , the running time of an algorithm does not cross the time provided by O(g(n)) .
Since it gives the worst-case running time of an algorithm, it is widely used to analyse an algorithm as we
are always interested in the worst-case scenario.
Big O complexity can be visualized with this graph:

As a programmer first and a mathematician second (or maybe third or last) here the best way to understand
Big O thoroughly examples in code. So, below are some common orders of growth along with descriptions
and examples where possible.

1.O(1)
void printFirstElementOfArray(int arr[])
{
printf("First element of array = %d",arr[0]);
}
This function runs in O(1) time (or "constant time") relative to its input. The input array could be 1 item or
1,000 items, but this function would still just require one step.

2. O(n)
void printAllElementOfArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d\n", arr[i]);
}
}
This function runs in O(n) time (or "linear time"), where n is the number of items in the array. If the array
has 10 items, we have to print 10 times. If it has 1000 items, we have to print 1000 times.

3. O(n2)
void printAllPossibleOrderedPairs(int arr[], int size)
Lvr Degree College
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
printf("%d = %d\n", arr[i], arr[j]);
}
}
}
Here we're nesting two loops. If our array has n items, our outer loop runs n times and our inner loop runs n
times for each iteration of the outer loop, giving us n2 total prints. Thus this function runs in O(n2) time (or
"quadratic time"). If the array has 10 items, we have to print 100 times. If it has 1000 items, we have to print
1000000 times.

4. O(2n)
int fibonacci(int num)
{
if (num <= 1) return num;
return fibonacci(num - 2) + fibonacci(num - 1);
}
An example of an O(2n) function is the recursive calculation of Fibonacci numbers. O(2n) denotes an
algorithm whose growth doubles with each addition to the input data set. The growth curve of an O(2n)
function is exponential - starting off very shallow, then rising meteorically.

 Algorithm Analysis
the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps,
known as time complexity, or volume of memory, known as space complexity.

Analysis of algorithm is the process of analysing the problem-solving capability of the algorithm in terms
of the time and size required (the size of memory for storage while implementation). However, the main
concern of analysis of algorithms is the required time or performance. Generally, we perform the following
types of analysis −
 Worst-case − The maximum number of steps taken on any instance of size a.
 Best-case − The minimum number of steps taken on any instance of size a.
 Average case − An average number of steps taken on any instance of size a.
 Amortized − A sequence of operations applied to the input of size a averaged over time.
To solve a problem, we need to consider time as well as space complexity as the program may run on a
system where memory is limited but adequate space is available or may be vice-versa. In this context, if we
compare bubble sort and merge sort. Bubble sort does not require additional memory, but merge sort
requires additional space. Though time complexity of bubble sort is higher compared to merge sort, we
may need to apply bubble sort if the program needs to run in an environment, where memory is very
limited.

 Structured Approach to Programming

Structured Programming Approach, as the word suggests, can be defined as a programming approach
in which the program is made as a single structure. It means that the code will execute the instruction by
instruction one after the other. It doesn’t support the possibility of jumping from one instruction to some
Lvr Degree College
other with the help of any statement like GOTO, etc. Therefore, the instructions in this approach will be
executed in a serial and structured manner. The languages that support Structured programming approach
are:
 C
 C++
 Java
 C#
..etc
The structured program mainly consists of three types of elements:
 Selection Statements
 Sequence Statements
 Iteration Statements
The structured program consists of well-structured and separated modules. But the entry and exit in a
Structured program is a single-time event. It means that the program uses single-entry and single-exit
elements. Therefore, a structured program is well maintained, neat and clean program. This is the reason
why the Structured Programming Approach is well accepted in the programming world.

 Recursion:
 Recursion is one of the most powerful tools in a programming language.
 When function is called within the same function, it is known as recursion in C.
The function which calls the same function, is known as recursive function.
 Recursion is defined as defining anything in terms of itself. Recursion is used to
solve problems involving iterations, in reverse order.

Types of Recursion
There are two types of Recursion

Direct Recursion
When in the body of a method there is a call to the same method, we say that the
method is directly recursive.
There are three types of Direct Recursion

 Linear Recursion
Lvr Degree College
  Binary Recursion
 Multiple Recursion

Linear Recursion
 Linear recursion begins by testing for a set of base cases there should be at least one.

In Linear recursion we follow as under:

 Perform a single recursive call. This recursive step may involve a test that decides
which of several possible recursive calls to make, but it should ultimately choose to
make just one of these calls each time we perform this step.
 Define each possible recursion call, so that it makes progress towards a base case.

Binary Recursion
 Binary recursion occurs whenever there are two recursive calls for each non base case.

Multiple Recursion
 In multiple recursion we make not just one or two but many recursive calls.

 Polish notation(imp)
Postfix notation is the useful form of intermediate code if the given language is
expressions.Postfix notation is also called as 'suffix notation' and 'reverse
polish'.Postfix notation is a linear representation of a syntax tree.In the postfix
notation, any expression can be written unambiguously without parentheses.The
ordinary (infix) way of writing the sum of x and y is with operator in the middle: x *
y. But in the postfix notation, we place the operator at the right end as xy *.In
postfix notation, the operator follows the operand.

Example:

Infix notation with parenthesis: (3 + 2) * (5 – 1)

Polish notation: * + 3 2 – 5 1

When used as the syntax for programming language interpreters, Polish notation can be
readily parsed into an abstract syntax tree and stored in a stack. In traditional infix notation
with brackets, the equation has to be parsed, the brackets removed, and the operator and
operands repositioned. This is not the case with Polish notation, which is why LISP(LIST
PROCESSING) and other related languages use this notation to define their syntax.

UNIT-II
What is an Array? Explain about Arrays (imp)

Lvr Degree College

Arrays are defined as the collection of similar types of data items stored at contiguous
memory locations. It is one of the simplest data structures where each data element can be
randomly accessed by using its index number.

Representation of an array
We can represent an array in various ways in different programming languages. declaration
of array in C language -

Index starts with 0.

The array's length is 10, which means we can store 10 elements.
Each element in the array can be accessed via its index.
Arrays are useful because -
Sorting and searching a value in an array is easier.
Arrays are best to process multiple values quickly and easily.
Arrays are good for storing multiple values in a single variable
Memory allocation of an array
All the data elements of an array are stored at contiguous locations in the
main memory. The name of the array represents the base address or the
address of the first element in the main memory. Each element of the
array is represented by proper indexing.
We can define the indexing of an array in the below ways -
0 (zero-based indexing): The first element of the array will be arr[0].
1 (one-based indexing): The first element of the array will be arr[1].
n (n - based indexing): The first element of the array can reside at any
random index number.

2.what are the basic operations of array

Basic operations
the basic operations supported in the array -
o Traversal - This operation is used to print the elements of the array.
o Insertion - It is used to add an element at a particular index.
o Deletion - It is used to delete an element from a particular index.
o Search - It is used to search an element using the given index or by the value.

Lvr Degree College

 o Update - It updates an element at a particular index.

Example:
#include <stdio.h>
void main() {
int Arr[5] = {18, 30, 15, 70, 12};
int i;
printf("Elements of the array are:\n");
for(i = 0; i<5; i++) {
printf("Arr[%d] = %d, ", i, Arr[i]);
}
}
Output:

3.what is Complexity of Array operations

Complexity of Array operations
Time and space complexity of various array operations are described in the following
table.

Time Complexity

Operation Average Case Worst Case

Access O(1) O(1)

Search O(n) O(n)

Insertion O(n) O(n)

Deletion O(n) O(n)

Space Complexity

In array, space complexity for worst case is O(n).

Lvr Degree College

4.what are advantages and disadvantages of array
Advantages of Array
o Array provides the single name for the group of variables of the same type. Therefore, it is easy
to remember the name of all the elements of an array.
o Traversing an array is a very simple process; we just need to increment the base address of the
array in order to visit each element one by one.
o Any element in the array can be directly accessed by using the index.

Disadvantages of Array
o Array is homogenous. It means that the elements with similar data type can be stored in it.
o In array, there is static memory allocation that is size of an array cannot be altered.
o There will be wastage of memory if we store less number of elements than the declared size.

5. What is Linked List? How to represent the Linked List? (imp)

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The
elements in a linked list are linked using pointers. Linked list can be defined as the nodes that are randomly
stored in the memory. A node in the linked list contains two parts, i.e., first is the data part and second
is the address part. The last node of the list contains a pointer to the null.

Representation of a Linked list

Linked list can be represented as the connection of nodes in which each node points to the next node
of the list. The representation of the linked list is shown below –

6. what are basic operations of linked list

Basic operations on Linked Lists:
o Insertion - This operation is performed to add an element into the list.
o Deletion - It is performed to delete an operation from the list.
o Display - It is performed to display the elements of the list.
o Search - It is performed to search an element from the list using the given key.

7. Explain types of linked lists (imp)

Types of Linked list

Lvr Degree College

Linked list is classified into the following types -

o Singly-linked list - Singly linked list can be defined as the collection of an ordered set of
elements. A node in the singly linked list consists of two parts: data part and link part. Data part
of the node stores actual information that is to be represented by the node, while the link part of
the node stores the address of its immediate successor.

o Doubly linked list - Doubly linked list is a complex type of linked list in which a node contains
a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly-linked
list, a node consists of three parts: node data, pointer to the next node in sequence (next
pointer), and pointer to the previous node (previous pointer).

o Circular singly linked list - In a circular singly linked list, the last node of the list contains a
pointer to the first node of the list. We can have circular singly linked list as well as circular
doubly linked list.

o Circular doubly linked list - Circular doubly linked list is a more complex type of data
structure in which a node contains pointers to its previous node as well as the next node.
Circular doubly linked list doesn't contain NULL in any of the nodes. The last node of the list
contains the address of the first node of the list. The first node of the list also contains the
address of the last node in its previous pointer.

8.Write a program on single linked list

#include<stdlib.h>
Lvr Degree College
#include <stdio.h>

void create();
void display();
void insert_begin();
void insert_end();
void insert_pos();
void delete_begin();
void delete_end();
void delete_pos();

struct node
{
int info;
struct node *next;
};
struct node *start=NULL;
int main()
{
int choice;
while(1){

printf("n MENU n");

printf("n 1.Create n");
printf("n 2.Display n");
printf("n 3.Insert at the beginning n");
printf("n 4.Insert at the end n");
printf("n 5.Insert at specified position n");
printf("n 6.Delete from beginning n");
printf("n 7.Delete from the end n");
printf("n 8.Delete from specified position n");
printf("n 9.Exit n");
printf("n--------------------------------------n");
printf("Enter your choice:t");
scanf("%d",&choice);
switch(choice)
{
case 1:
create();
break;
case 2:
display();
break;
case 3:
insert_begin();
break;
case 4:
insert_end();
break;
case 5:
insert_pos();
break;
case 6:
delete_begin();
break;
Lvr Degree College
case 7:
delete_end();
break;
case 8:
delete_pos();
break;

case 9:
exit(0);
break;

default:
printf("n Wrong Choice:n");
break;
}
}
return 0;
}
void create()
{
struct node *temp,*ptr;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("nOut of Memory Space:n");
exit(0);
}
printf("nEnter the data value for the node:t");
scanf("%d",&temp->info);
temp->next=NULL;
if(start==NULL)
{
start=temp;
}
else
{
ptr=start;
while(ptr->next!=NULL)
{
ptr=ptr->next;
}
ptr->next=temp;
}
}
void display()
{
struct node *ptr;
if(start==NULL)
{
printf("nList is empty:n");
return;
}
else
{
ptr=start;
printf("nThe List elements are:n");
Lvr Degree College
while(ptr!=NULL)
{
printf("%dt",ptr->info );
ptr=ptr->next ;
}
}
}
void insert_begin()
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("nOut of Memory Space:n");
return;
}
printf("nEnter the data value for the node:t" );
scanf("%d",&temp->info);
temp->next =NULL;
if(start==NULL)
{
start=temp;
}
else
{
temp->next=start;
start=temp;
}
}
void insert_end()
{
struct node *temp,*ptr;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("nOut of Memory Space:n");
return;
}
printf("nEnter the data value for the node:t" );
scanf("%d",&temp->info );
temp->next =NULL;
if(start==NULL)
{
start=temp;
}
else
{
ptr=start;
while(ptr->next !=NULL)
{
ptr=ptr->next ;
}
ptr->next =temp;
}
}
void insert_pos()
Lvr Degree College
{
struct node *ptr,*temp;
int i,pos;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("nOut of Memory Space:n");
return;
}
printf("nEnter the position for the new node to be inserted:t");
scanf("%d",&pos);
printf("nEnter the data value of the node:t");
scanf("%d",&temp->info) ;

temp->next=NULL;
if(pos==0)
{
temp->next=start;
start=temp;
}
else
{
for(i=0,ptr=start;i<pos-1;i++) { ptr=ptr->next;
if(ptr==NULL)
{
printf("nPosition not found:[Handle with care]n");
return;
}
}
temp->next =ptr->next ;
ptr->next=temp;
}
}
void delete_begin()
{
struct node *ptr;
if(ptr==NULL)
{
printf("nList is Empty:n");
return;
}
else
{
ptr=start;
start=start->next ;
printf("nThe deleted element is :%dt",ptr->info);
free(ptr);
}
}
void delete_end()
{
struct node *temp,*ptr;
if(start==NULL)
{
printf("nList is Empty:");
exit(0);
Lvr Degree College
}
else if(start->next ==NULL)
{
ptr=start;
start=NULL;
printf("nThe deleted element is:%dt",ptr->info);
free(ptr);
}
else
{
ptr=start;
while(ptr->next!=NULL)
{
temp=ptr;
ptr=ptr->next;
}
temp->next=NULL;
printf("nThe deleted element is:%dt",ptr->info);
free(ptr);
}
}
void delete_pos()
{
int i,pos;
struct node *temp,*ptr;
if(start==NULL)
{
printf("nThe List is Empty:n");
exit(0);
}
else
{
printf("nEnter the position of the node to be deleted:t");
scanf("%d",&pos);
if(pos==0)
{
ptr=start;
start=start->next ;
printf("nThe deleted element is:%dt",ptr->info );
free(ptr);
}
else
{
ptr=start;
for(i=0;i<pos;i++) { temp=ptr; ptr=ptr->next ;
if(ptr==NULL)
{
printf("nPosition not Found:n");
return;
}
}
temp->next =ptr->next ;
printf("nThe deleted element is:%dt",ptr->info );
free(ptr);
}
}
Lvr Degree College
}

9.what are advantages of linked list

Advantages of Linked Lists:
 Dynamic Array.
 Ease of Insertion/Deletion.
 Insertion at the beginning is a constant time operation and takes O(1) time, as compared to arrays where
inserting an element at the beginning takes O(n) time,where n is the number of elements in the array.

10.what are the applications of linked list

● Linked Lists can be used to implement useful data structures like stacks and queues.
● Linked Lists can be used to implement hash tables, each bucket of the hash table can be a linked list.
● Linked Lists can be used to implement graphs (Adjacency List representation of graph).
● Linked Lists can be used in a refined way in implementing different file systems in one form or another.

11.Difference between arrays and linked list (imp)

Array Linked list

An array is a collection of elements of a A linked list is a collection of objects known

similar data type. as a node where node consists of two parts,
i.e., data and address.

Array elements store in a contiguous Linked list elements can be stored anywhere
memory location. in the memory or randomly stored.

Array works with a static memory. Here The Linked list works with dynamic memory.
static memory means that the memory Here, dynamic memory means that the
size is fixed and cannot be changed at the memory size can be changed at the run
run time. time according to our requirements.

Array elements are independent of each Linked list elements are dependent on each
other. other. As each node contains the address of
the next node so to access the next node,
we need to access its previous node.

Array takes more time while performing Linked list takes less time while performing
any operation like insertion, deletion, etc. any operation like insertion, deletion, etc.

Accessing any element in an array is faster Accessing an element in a linked list is

as the element in an array can be directly slower as it starts traversing from the first
accessed through the index. element of the linked list.

In the case of an array, memory is In the case of a linked list, memory is

allocated at compile-time. allocated at run time.

Memory utilization is inefficient in the Memory utilization is efficient in the case of

array. For example, if the size of the array a linked list as the memory can be allocated
is 6, and array consists of 3 elements only or deallocated at the run time according to
then the rest of the space will be unused. our requirement.

Unit-III

1. What is stack? How to represent a stack (imp)

Lvr Degree College

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end.It
contains only one pointer top pointer pointing to the topmost element of the stack. Whenever an element is
added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In
other words, a stack can be defined as a container in which insertion and deletion can be done from the
one end known as the top of the stack.

Representation of Stack:

It follows the principle LIFO (Last In First Out) in which the insertion and deletion take place from
one side known as a top. In stack, we can insert the elements of a similar data type, i.e., the different
data type elements cannot be inserted in the same stack. The two operations are performed in LIFO,
i.e., push and pop operation.

The following are the operations that can be performed on the stack:

o push(x): It is an operation in which the elements are inserted at the top of the stack. In
the push function, we need to pass an element which we want to insert in a stack.
o pop(): It is an operation in which the elements are deleted from the top of the stack. In
the pop() function, we do not have to pass any argument.
o peek()/top(): This function returns the value of the topmost element available in the stack. Like
pop(), it returns the value of the topmost element but does not remove that element from the
stack.
o isEmpty(): If the stack is empty, then this function will return a true value or else it will return a
false value.
o isFull(): If the stack is full, then this function will return a true value or else it will return a false
value.

2.Write about Stack algorithms (imp)

1.push algorithm
1 − Checks if the stack is full.
2 − If the stack is full, produces an error and exit.
Lvr Degree College
3 − If the stack is not full, increments top to point next empty space.
4 − Adds data element to the stack location, where top is pointing.
5 − Returns success.

2.pop algorithm

1 − Checks if the stack is empty.

2 − If the stack is empty, produces an error and exit.
3 − If the stack is not empty, accesses the data element at which top is pointing.
4 − Decreases the value of top by 1.
5 − Returns success.

3.peek algorithm

1. START
2. return the element at the top of the stack
3. END

4.isFull algorithm

1. START
2. If the size of the stack is equal to the top position of the stack, the stack is full.
Return 1.
3. Otherwise, return 0.
4. END

5.isEmpty algorithm
1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END

3.Write a program on Stack using array (imp)

#include <stdio.h>
int stack[100],i,j,choice=0,n,top=-1;
void push();
void pop();
void show();
void main ()
{

printf("Enter the number of elements in the stack ");

scanf("%d",&n);
printf("Stack operations using array");
while(choice != 4)
{
printf("Chose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
Lvr Degree College
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
show();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}

void push ()
{
int val;
if (top == n )
printf("\n Overflow");
else
{
printf("Enter the value?");
scanf("%d",&val);
top = top +1;
stack[top] = val;
}
}

void pop ()
{
if(top == -1)
printf("Underflow");
else
top = top -1;
}
void show()
{
for (i=top;i>=0;i--)

Lvr Degree College

{
printf("%d\n",stack[i]);
}
if(top == -1)
{
printf("Stack is empty");
}
}

4.what is queue ? how to represent a queue (imp)

A Queue is defined as a linear data structure that is open at both ends and the operations are performed in
First In First Out (FIFO) order. Hence, it follows FIFO (First-In-First-Out) structure, i.e. the data item
inserted first will also be accessed first. The data is inserted into the queue through one end and deleted from
it using the other end.

representation
a queue ADT can also be implemented using arrays, linked lists, or pointers. we implement queues using a one-
dimensional array.

Basic Operations on Queue:

Some of the basic operations for Queue in Data Structure are:
 enqueue() – Insertion of elements to the queue.
 dequeue() – Removal of elements from the queue.
 peek() or front()- Acquires the data element available at the front node of the queue without deleting it.
 rear() – This operation returns the element at the rear end without removing it.
 isFull() – Validates if the queue is full.
 isEmpty() – Checks if the queue is empty.
 size(): This operation returns the size of the queue i.e. the total number of elements it contains.

5.write about queue algorithms (imp)

1.Insertion operation: enqueue() algorithm

The following algorithm describes the enqueue() operation in a simpler way.

1 − START
2 – Check if the queue is full.
3 − If the queue is full, produce overflow error and exit.
4 − If the queue is not full, increment rear pointer to point the next empty space.
5 − Add data element to the queue location, where the rear is pointing.
6 − return success.
7 – END

2. Deletion Operation: dequeue()

Lvr Degree College
The following algorithm describes the dequeue() operation in a simpler way.

1 – START
2 − Check if the queue is empty.
3 − If the queue is empty, produce underflow error and exit.
4 − If the queue is not empty, access the data where front is pointing.
5 − Increment front pointer to point to the next available data element.
6 − Return success.
7 – END

3. The peek() Operation

The peek() is an operation which is used to retrieve the frontmost element in the queue, without deleting it.

1 – START
2 – Return the element at the front of the queue
3 – END

4.The isFull() Operation

The isFull() operation verifies whether the stack is full.

Algorithm

1 – START
2 – If the count of queue elements equals the queue size, return true
3 – Otherwise, return false
4 – END

5. The isEmpty() operation

The isEmpty() operation verifies whether the stack is empty. This operation is used to check the status of the stack
with the help of top pointer.

Algorithm
1 – START
2 – If the count of queue elements equals zero, return true
3 – Otherwise, return false
4 – END

6.write a program on QUEUE using array

#include<stdio.h>
#include<stdlib.h>
#define maxsize 5
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main ()
{
int choice;
while(choice != 4)
{
printf("Main Menu\n");
printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");

Lvr Degree College

 printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
void insert()
{
int item;
printf("\nEnter the element\n");
scanf("\n%d",&item);
if(rear == maxsize-1)
{
printf("\nOVERFLOW\n");
return;
}
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear+1;
}
queue[rear] = item;
printf("\nValue inserted ");

}
void delete()
{
int item;
if (front == -1 || front > rear)
{
printf("\nUNDERFLOW\n");
return;

}
else

Lvr Degree College

 {
item = queue[front];
if(front == rear)
{
front = -1;
rear = -1 ;
}
else
{
front = front + 1;
}
printf("\nvalue deleted ");
}
}

void display()
{
int i;
if(rear == -1)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
for(i=front;i<=rear;i++)
{
printf("\n%d\n",queue[i]);
}
}
}

7.write any 5 Applications of queues

1. Task Scheduling: Queues can be used to schedule tasks based on priority or the order in which they
were received.
2. Resource Allocation: Queues can be used to manage and allocate resources, such as printers or CPU
processing time.
3. Batch Processing: Queues can be used to handle batch processing jobs, such as data analysis or image
rendering.
4. Message Buffering: Queues can be used to buffer messages in communication systems, such as
message queues in messaging systems or buffers in computer networks.
5. Event Handling: Queues can be used to handle events in event-driven systems, such as GUI
applications or simulation systems.
6. Traffic Management: Queues can be used to manage traffic flow in transportation systems, such as
airport control systems or road networks.
7. Operating systems: Operating systems often use queues to manage processes and resources. For
example, a process scheduler might use a queue to manage the order in which processes are executed.
8. Network protocols: Network protocols like TCP and UDP use queues to manage packets that are
transmitted over the network. Queues can help to ensure that packets are delivered in the correct order
and at the appropriate rate.
9. Breadth-first search algorithm: The breadth-first search algorithm uses a queue to explore nodes in a
graph level-by-level. The algorithm starts at a given node, adds its neighbors to the queue, and then
processes each neighbor in turn.

Lvr Degree College

8. explain about types of queues (imp)
A queue is a useful data structure in programming. It is similar to the ticket queue outside a cinema hall,
where the first person entering the queue is the first person who gets the ticket.

There are four different types of queues:

1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Double Ended Queue

1.Simple queue
In a simple queue, insertion takes place at the rear and removal occurs at the front. It strictly follows the
FIFO (First in First out) rule.

2. Circular Queue

In a circular queue, the last element points to the first element making a circular link.

The main advantage of a circular queue over a simple queue is better memory utilization. If the last position
is full and the first position is empty, we can insert an element in the first position. This action is not possible
in a simple queue.

3.priority queue:
A priority queue is a special type of queue in which each element is associated with a priority and is served
according to its priority. If elements with the same priority occur, they are served according to their order in
the queue.

4. Deque (Double Ended Queue)

In a double ended queue, insertion and removal of elements can be performed from either from the front or rear.
Thus, it does not follow the FIFO (First In First Out) rule.

Lvr Degree College

9.Write any 5 stack applications (imp)
 Function calls and recursion: When a function is called, the current state of the program is pushed
onto the stack. When the function returns, the state is popped from the stack to resume the previous
function’s execution.
 Undo/Redo operations: The undo-redo feature in various applications uses stacks to keep track of the
previous actions. Each time an action is performed, it is pushed onto the stack. To undo the action, the
top element of the stack is popped, and the reverse operation is performed.
 Expression evaluation: Stack data structure is used to evaluate expressions in infix, postfix, and prefix
notations. Operators and operands are pushed onto the stack, and operations are performed based on the
stack’s top elements.
 Browser history: Web browsers use stacks to keep track of the web pages you visit. Each time you
visit a new page, the URL is pushed onto the stack, and when you hit the back button, the previous
URL is popped from the stack.
 Balanced Parentheses: Stack data structure is used to check if parentheses are balanced or not. An
opening parenthesis is pushed onto the stack, and a closing parenthesis is popped from the stack. If the
stack is empty at the end of the expression, the parentheses are balanced.
 Backtracking Algorithms: The backtracking algorithm uses stacks to keep track of the states of the
problem-solving process. The current state is pushed onto the stack, and when the algorithm
backtracks, the previous state is popped from the stack.

Lvr Degree College

 UNIT-IV
1.What is binary tree

A binary search tree in a data structure is typically used to represent or store hierarchical data. A “binary
tree” is a tree data structure where every node has two child nodes (at the most) that form the tree branches.
These child nodes are called left and right child nodes.

2. How to represent a binary tree

A binary tree is a hierarchical data structure in which each node has at most two children generally referred
as left child and right child.
Each node contains three components:

1. Pointer to left subtree

2. Pointer to right subtree
3. Data element
The topmost node in the tree is called the root. An empty tree is represented by NULL pointer.
A representation of binary tree is shown:

Lvr Degree College

Binary Tree: Common Terminologies

 Root: Topmost node in a tree.

 Parent: Every node (excluding a root) in a tree is connected by a directed
edge from exactly one other node. This node is called a parent.
 Child: A node directly connected to another node when moving away from
the root.
 Leaf/External node: Node with no children.
 Internal node: Node with atleast one children.
 Depth of a node: Number of edges from root to the node.
 Height of a node: Number of edges from the node to the deepest leaf.
Height of the tree is the height of the root.

3.What are the properties of binary tree (imp)

Properties of Binary Tree

o At each level of i, the maximum number of nodes is 2i.

o The height of the tree is defined as the longest path from the root node to the leaf
node. The tree which is shown above has a height equal to 3. Therefore, the
maximum number of nodes at height 3 is equal to (1+2+4+8) = 15. In general, the
maximum number of nodes possible at height h is (20 + 21 + 22+….2h) = 2h+1 -1.
o The minimum number of nodes possible at height h is equal to h+1.
o If the number of nodes is minimum, then the height of the tree would be maximum.
Conversely, if the number of nodes is maximum, then the height of the tree would be
minimum.

3.What are the types of Binary trees (imp)

There are five types of Binary tree:

o Full/proper/ strict Binary tree

o Complete Binary tree
o Perfect Binary tree
o Degenerate Binary tree
o Balanced Binary tree

1. Full/ proper/ strict Binary tree

The full binary tree is also known as a strict binary tree. The tree can only be considered as the full
binary tree if each node must contain either 0 or 2 children. The full binary tree can also be defined as
the tree in which each node must contain 2 children except the leaf nodes.

Lvr Degree College

In the above tree, we can observe that each node is either containing zero or two children; therefore, it
is a Full Binary tree.

2. Complete Binary Tree

The complete binary tree is a tree in which all the nodes are completely filled except the last level. In
the last level, all the nodes must be as left as possible. In a complete binary tree, the nodes should be
added from the left.

The above tree is a complete binary tree because all the nodes are completely filled, and all the nodes
in the last level are added at the left first.

3. Perfect Binary Tree

A tree is a perfect binary tree if all the internal nodes have 2 children, and all the leaf nodes are at the
same level.

4. Degenerate Binary Tree

The degenerate binary tree is a tree in which all the internal nodes have only one children.
Lvr Degree College
The above tree is a degenerate binary tree because all the nodes have only one child. It is also known
as a right-skewed tree as all the nodes have a right child only.

5. Balanced Binary Tree

The balanced binary tree is a tree in which both the left and right trees differ by atmost 1. For
example, AVL and Red-Black trees are balanced binary tree.

4. Explain about Binary tree traversal with algorithm (imp)

Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected
via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree.
There are three ways which we use to traverse a tree

1. In-order Traversal
2. Pre-order Traversal
3. Post-order Traversal

1. in-order traversal:
In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always
remember that every node may represent a subtree itself.
If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order.

Lvr Degree College

We start from A, and following in-order traversal, we move to its left subtree B.
B is also traversed in-order. The process goes on until all the nodes are visited.
The output of in-order traversal of this tree will be −
D→B→E→A→F→C→G

Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

2. Pre-order Traversal
In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.

We start from A, and following pre-order traversal, we first visit A itself and then move to its left subtree B. B is also
traversed pre-order. The process goes on until all the nodes are visited. The output of pre-order traversal of this tree
will be −
A→B→D→E→C→F→G

Algorithm
Until all nodes are traversed −

Lvr Degree College

Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

3.Post-order Traversal
In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right
subtree and finally the root node.

We start from A, and following pre-order traversal, we first visit the left subtree B. B is also traversed post-order. The
process goes on until all the nodes are visited. The output of post-order traversal of this tree will be −
D→E→B→F→G→C→A

Algorithm
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

5.Explain about binary tree applications

o Binary trees are applied in data compression methods in the form of the Huffman coding tree.
o Expression Trees, a binary tree application, are used in compilers.
o Another binary tree application that searches maximum or minimum in O(log N) time complexity
is priority queue.
o Display data that is hierarchical.
o Utilized in spreadsheet and Microsoft Excel editing applications.
o For putting priority queues into action.
o Utilized to provide quick memory allocation in computers (binary search tree) by finding items
more quickly.
o Encoding and decoding operations

Lvr Degree College

 UNIT-V

PART-A
SEARCHING TECHNIQUES

1.What is Searching?

 Searching is the process of finding a given value position in a list of values.

 It decides whether a search key is present in the data or not.
 It is the algorithmic process of finding a particular item in a collection of items.
 It can be done on internal data structure or on external data structure.

Searching Techniques
To search an element in a given array, it can be done in following ways:

1. Sequential Search
2. Binary Search

2.Explain about Sequential Search with algorithm

 Sequential search is also called as Linear Search.

 Sequential search starts at the beginning of the list and checks every element of the list.
 It is a basic and simple search algorithm.
 Sequential search compares the element with all the other elements given in the list. If the element is
matched, it returns the value index, else it returns -1.

The above figure shows how sequential search works. It searches an element or value from an array till the
desired element or value is not found. If we search the element 25, it will go step by step in a sequence
order. It searches in a sequence order. Sequential search is applied on the unsorted or unordered list when
there are fewer elements in a list.

Algorithm:

Linear_Search(a, n, val) // 'a' is the given array, 'n' is the size of given array, 'val' is the value to search
Step 1: set pos = -1
Step 2: set i = 1
Step 3: repeat step 4 while i <= n
Step 4: if a[i] == val
set pos = i
print pos
go to step 6
[end of if]
Lvr Degree College
 set ii = i + 1
[end of loop]
Step 5: if pos = -1
print "value is not present in the array "
[end of if]
Step 6: exit

3. Write a program on linear search

#include <stdio.h>
int linearSearch(int a[], int n, int val)
{
// Going through array sequencially
for (int i = 0; i < n; i++)
{
if (a[i] == val)
return i+1;
}
return -1;
}
int main()
{
int a[] = {70, 40, 30, 11, 57, 41, 25, 14, 52}; // given array
int val = 41; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = linearSearch(a, n, val); // Store result
printf("The elements of the array are - ");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\nElement to be searched is - %d", val);
if (res == -1)
printf("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0;
}

Output:

4. Explain about Binary Search with algorithm (imp)

 Binary Search is used for searching an element in a sorted array.
 It is a fast search algorithm with run-time complexity of O(log n).
 Binary search works on the principle of divide and conquer.
 This searching technique looks for a particular element by comparing the middle most element of the
collection.
 It is useful when there are large number of elements in an array.

Lvr Degree College

 e above array is sorted in ascending order. As we know binary search is applied on sorted lists only for fast
searching.
For example, if searching an element 25 in the 7-element array, following figure shows how binary search
works:

Binary searching starts with middle element. If the element is equal to the element that we are searching
then return true. If the element is less than then move to the right of the list or if the element is greater
than then move to the left of the list. Repeat this, till you find an element.

Algorithm:
Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of
the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search

Step 1: set beg = lower_bound, end = upper_bound, pos = - 1

Step 2: repeat steps 3 and 4 while beg <=end
Step 3: set mid = (beg + end)/2
Step 4: if a[mid] = val
set pos = mid
print pos
go to step 6
else if a[mid] > val
set end = mid - 1
else
set beg = mid + 1
[end of if]
[end of loop]
Step 5: if pos = -1
print "value is not present in the array"
[end of if]
Step 6: exit

5. Write a program on Binary search (imp)

#include <stdio.h>
Lvr Degree College
int binarySearch(int a[], int beg, int end, int val)
{
int mid;
if(end >= beg)
{ mid = (beg + end)/2;
/* if the item to be searched is present at middle */
if(a[mid] == val)
{
return mid+1;
}
/* if the item to be searched is smaller than middle, then it can only be in left subarray */
else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);
}
/* if the item to be searched is greater than middle, then it can only be in right subarray */
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
int main() {
int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array
int val = 40; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = binarySearch(a, 0, n-1, val); // Store result
printf("The elements of the array are - ");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\nElement to be searched is - %d", val);
if (res == -1)
printf("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0;
}

Output

Lvr Degree College

 SORTING TECHNIQUES

PART-A

1.what is sorting and what are its types

Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in
a particular order. Sorting is the process of arranging the elements of an array so that they can be placed
either in ascending or descending order.

There are different types of sorting

1.bubble sort
2.selection sort
3.merge sort
4.insertion sort
5.quick sort. etc.,

SN Sorting Description
Algorithms

1 Bubble Sort It is the simplest sort method which performs sorting by repeatedly
moving the largest element to the highest index of the array. It
comprises of comparing each element to its adjacent element and
replace them accordingly.

2 Insertion As the name suggests, insertion sort inserts each element of the array
Sort to its proper place. It is a very simple sort method which is used to
arrange the deck of cards while playing bridge.

3 Merge Sort Merge sort follows divide and conquer approach in which, the list is
first divided into the sets of equal elements and then each half of the
list is sorted by using merge sort. The sorted list is combined again to
form an elementary sorted array.

4 Quick Sort Quick sort is the most optimized sort algorithms which performs
sorting in O(n log n) comparisons. Like Merge sort, quick sort also
work by using divide and conquer approach.

5 Selection Selection sort finds the smallest element in the array and place it on
Sort the first place on the list, then it finds the second smallest element in
the array and place it on the second place. This process continues
until all the elements are moved to their correct ordering. It carries
running time O(n2) which is worst than insertion sort.

Lvr Degree College

2.write an algorithm and working example of bubble sort (imp)
Bubble sort works on the repeatedly swapping of adjacent elements until they are not in the intended
order. It is called bubble sort because the movement of array elements is just like the movement of air
bubbles in the water. Bubbles in water rise up to the surface; similarly, the array elements in bubble
sort move to the end in each iteration.

Algorithm

In the algorithm given below, suppose arr is an array of n elements. The assumed swap function in the
algorithm will swap the values of given array elements.
begin BubbleSort(arr)
for all array elements
if arr[i] > arr[i+1]
swap(arr[i], arr[i+1])
end if
end for
return arr
end BubbleSort

Working example

To understand the working of bubble sort algorithm, let's take an unsorted array. We are taking a short and accurate
array, as we know the complexity of bubble sort is O(n2).
Let the elements of array are -

First Pass
Sorting will start from the initial two elements. Let compare them to check which is greater.

Here, 32 is greater than 13 (32 > 13), so it is already sorted. Now, compare 32 with 26.

Here, 26 is smaller than 36. So, swapping is required. After swapping new array will look like -

Now, compare 32 and 35.

Here, 35 is greater than 32. So, there is no swapping required as they are already sorted.
Now, the comparison will be in between 35 and 10.

Lvr Degree College

Here, 10 is smaller than 35 that are not sorted. So, swapping is required. Now, we reach at the end of the array. After
first pass, the array will be -

Now, move to the second iteration.

Second Pass
The same process will be followed for second iteration.

Here, 10 is smaller than 32. So, swapping is required. After swapping, the array will be -

Now, move to the third iteration.

Third Pass
The same process will be followed for third iteration.

Here, 10 is smaller than 26. So, swapping is required. After swapping, the array will be -

Now, move to the fourth iteration.

Fourth pass
Similarly, after the fourth iteration, the array will be -

Hence, there is no swapping required, so the array is completely sorted.

3.write a program on Bubble sort (imp)
#include<stdio.h>
void print(int a[], int n) //function to print array elements
{
int i;
Lvr Degree College
for(i = 0; i < n; i++)
{
printf("%d ",a[i]);
}
}
void bubble(int a[], int n) // function to implement bubble sort
{
int i, j, temp;
for(i = 0; i < n; i++)
{
for(j = i+1; j < n; j++)
{
if(a[j] < a[i])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
void main ()
{
int i, j,temp;
int a[5] = { 10, 35, 32, 13, 26};
int n = sizeof(a)/sizeof(a[0]);
printf("Before sorting array elements are - \n");
print(a, n);
bubble(a, n);
printf("\nAfter sorting array elements are - \n");
print(a, n);
}

Output:

4.write an algorithm for insertion sort and working example

Insertion sort works similar to the sorting of playing cards in hands. It is assumed that the first card is
already sorted in the card game, and then we select an unsorted card. If the selected unsorted card is
greater than the first card, it will be placed at the right side; otherwise, it will be placed at the left side.
Similarly, all unsorted cards are taken and put in their exact place.
Algorithm
The simple steps of achieving the insertion sort are listed as follows -
Step 1 - If the element is the first element, assume that it is already sorted. Return 1.
Step2 - Pick the next element, and store it separately in a key.
Step3 - Now, compare the key with all elements in the sorted array.
Step 4 - If the element in the sorted array is smaller than the current element, then move to the next element.
Else, shift greater elements in the array towards the right.
Step 5 - Insert the value.
Step 6 - Repeat until the array is sorted.

Lvr Degree College

Working example
To understand the working of the insertion sort algorithm, we taken an unsorted array. It will be easier to
understand the insertion sort via an example.
Let the elements of array are -

Initially, the first two elements are compared in insertion sort.

Here, 31 is greater than 12. That means both elements are already in ascending order. So, for now, 12 is stored in a
sorted sub-array.

Now, move to the next two elements and compare them.

Here, 25 is smaller than 31. So, 31 is not at correct position. Now, swap 31 with 25. Along with swapping, insertion
sort will also check it with all elements in the sorted array.
For now, the sorted array has only one element, i.e. 12. So, 25 is greater than 12. Hence, the sorted array remains
sorted after swapping.

Now, two elements in the sorted array are 12 and 25. Move forward to the next elements that are 31 and 8.

Both 31 and 8 are not sorted. So, swap them.

After swapping, elements 25 and 8 are unsorted.

So, swap them.

Now, elements 12 and 8 are unsorted.

So, swap them too.

Now, the sorted array has three items that are 8, 12 and 25. Move to the next items that are 31 and 32.

Hence, they are already sorted. Now, the sorted array includes 8, 12, 25 and 31.
Lvr Degree College
Move to the next elements that are 32 and 17.

17 is smaller than 32. So, swap them.

Swapping makes 31 and 17 unsorted. So, swap them too.

Now, swapping makes 25 and 17 unsorted. So, perform swapping again.

Now, the array is completely sorted.

5.write a program on insertion sort

#include <stdio.h>
void insert(int a[], int n) /* function to sort an aay with insertion sort */
{
int i, j, temp;
for (i = 1; i < n; i++)
{
temp = a[i];
j = i - 1;
while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one position ahead from their
current position*/
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}

void printArr(int a[], int n) /* function to print the array */

{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
Lvr Degree College
 printf("Before sorting array elements are - \n");
printArr(a, n);
insert(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}

Output:

6.write about merge sort algorithm and working example

Merge sort is similar to the quick sort algorithm as it uses the divide and conquer approach to sort the
elements. It divides the given list into two equal halves, calls itself for the two halves and then merges
the two sorted halves. We have to define the merge() function to perform the merging.

The sub-lists are divided again and again into halves until the list cannot be divided further. Then we
combine the pair of one element lists into two-element lists, sorting them in the process. The sorted
two-element pairs is merged into the four-element lists, and so on until we get the sorted list.

Algorithm
In the following algorithm, arr is the given array, beg is the starting element, and end is the last
element of the array.

1. MERGE_SORT(arr, beg, end)

2.
3. if beg < end
4. set mid = (beg + end)/2
5. MERGE_SORT(arr, beg, mid)
6. MERGE_SORT(arr, mid + 1, end)
7. MERGE (arr, beg, mid, end)
8. end of if
9. END MERGE_SORT

Working Example

To understand the working of the merge sort algorithm, let's take an unsorted array. It will be easier to
understand the merge sort via an example.

Let the elements of array are –

Lvr Degree College

According to the merge sort, first divide the given array into two equal halves. Merge sort keeps
dividing the list into equal parts until it cannot be further divided.

As there are eight elements in the given array, so it is divided into two arrays of size 4.

Now, again divide these two arrays into halves. As they are of size 4, so divide them into new arrays of
size 2.

Now, again divide these arrays to get the atomic value that cannot be further divided.

Now, combine them in the same manner they were broken.

In combining, first compare the element of each array and then combine them into another array in
sorted order.

So, first compare 12 and 31, both are in sorted positions. Then compare 25 and 8, and in the list of two
values, put 8 first followed by 25. Then compare 32 and 17, sort them and put 17 first followed by 32.
After that, compare 40 and 42, and place them sequentially.

In the next iteration of combining, now compare the arrays with two data values and merge them into
an array of found values in sorted order.

Now, there is a final merging of the arrays. After the final merging of above arrays, the array will look
like

7.write a program on merge sort

#include <stdio.h>
/* Function to merge the subarrays of a[] */
void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;

Lvr Degree College

int n2 = end - mid;

int LeftArray[n1], RightArray[n2]; //temporary arrays

/* copy data to temp arrays */

for (int i = 0; i < n1; i++)
LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];

i = 0; /* initial index of first sub-array */

j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */

while (i < n1 && j < n2)

{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
i++;
k++;
}

while (j<n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}

void mergeSort(int a[], int beg, int end)

{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}

Lvr Degree College

/* Function to print the array */
void printArray(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}

int main()
{
int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArray(a, n);
mergeSort(a, 0, n - 1);
printf("After sorting array elements are - \n");
printArray(a, n);
return 0;
}

Output

8.write an algorithm on quick sort and working example (imp)

Quicksort is the widely used sorting algorithm that makes n log n comparisons in average case for
sorting an array of n elements. It is a faster and highly efficient sorting algorithm. This algorithm follows
the divide and conquer approach. Divide and conquer is a technique of breaking down the algorithms
into subproblems, then solving the subproblems, and combining the results back together to solve the
original problem.

Algorithm
QUICKSORT (array A, start, end)
{
1 if (start < end)
2{
3 p = partition(A, start, end)
4 QUICKSORT (A, start, p - 1)
5 QUICKSORT (A, p + 1, end)
6}
}

Working example

To understand the working of quick sort, let's take an unsorted array. It will make the concept more clear
and understandable.
Let the elements of array are -

Lvr Degree College

In the given array, we consider the leftmost element as pivot. So, in this case, a[left] = 24, a[right] = 27 and
a[pivot] = 24.
Since, pivot is at left, so algorithm starts from right and move towards left.

Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e. -

Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and pivot moves to right, as -

Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so algorithm starts from left and
moves to right.
As a[pivot] > a[left], so algorithm moves one position to right as -

Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so algorithm moves one position to
right as -

Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so, swap a[pivot] and a[left], now
pivot is at left, i.e. -

Since, pivot is at left, so algorithm starts from right, and move to left. Now, a[left] = 24, a[right] = 29, and
a[pivot] = 24. As a[pivot] < a[right], so algorithm moves one position to left, as -

Lvr Degree College

Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so, swap a[pivot] and a[right], now
pivot is at right, i.e. -

Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so the algorithm starts from left and
move to right.

Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right are pointing the same element. It
represents the termination of procedure.

Element 24, which is the pivot element is placed at its exact position.

Elements that are right side of element 24 are greater than it, and the elements that are left side of element 24
are smaller than it.

Now, in a similar manner, quick sort algorithm is separately applied to the left and right sub-arrays. After
sorting gets done, the array will be -

9. Write a program on quick sort (imp)

#include<stdio.h>
void quicksort(int number[25],int first,int last)
{
int i, j, pivot, temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j)
{
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
Lvr Degree College
if(i<j)
{
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main(){
int i, count, number[25];
printf("How many elements are u going to enter: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
}

OUTPUT:

How many elements are u going to enter: 10

Enter 10 elements: 2 3 5 7 1 9 3 8 0 4
Order of Sorted elements: 0 1 2 3 3 4 5 7 8 9

Lvr Degree College

 UNIT-V

PART-B

GRAPHS
1. Define graph? Explain about types of Graph (IMP)
A Graph is a non-linear data structure consisting of vertices and edges. A graph is represented as G = {V, E}, where G
is the graph space, V is the set of vertices are sometimes also referred to as nodes and the E is the edges are lines or
arcs that connect any two nodes in the graph.
More formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by G(V,E).

Different types of graphs:

1.directed graph
2.undirected graph
3.weighted graph
4.finite graph
5.infinite graph

1. directed graph:
In a directed graph, edges form an ordered pair. Edges represent a specific path from some vertex A to another
vertex B. Node A is called initial node while node B is called terminal node.
A directed graph is shown in the following figure.

2. Undirected graph:
in an undirected graph, edges are not associated with the directions with them. An undirected graph is
shown in the above figure since its edges are not attached with any of the directions. If an edge exists
between vertex A and B then the vertices can be traversed from B to A as well as A to B.

Lvr Degree College

3.Weighted Graph:
A graph in which edges have weights or costs associated with them. Example: A road network graph where
the weights can represent the distance between two cities.

4.Finite Graphs
A graph is said to be finite if it has a finite number of vertices and a finite number of edges.

5. Infinite Graph:
A graph is said to be infinite if it has an infinite number of vertices as well as an infinite number of edges.

2.write about graph terminologies

Path:A path can be defined as the sequence of nodes that are followed in order to reach some terminal
node V from the initial node U.

Closed Path:A path will be called as closed path if the initial node is same as terminal node. A path will
be closed path if V0=VN.

Simple Path:If all the nodes of the graph are distinct with an exception V 0=VN, then such path P is called
as closed simple path.

Cycle:A cycle can be defined as the path which has no repeated edges or vertices except the first and
last vertices.

Lvr Degree College

Connected Graph: A connected graph is the one in which some path exists between every two vertices
(u, v) in V. There are no isolated nodes in connected graph.

Complete Graph:A complete graph is the one in which every node is connected with all other nodes. A
complete graph contain n(n-1)/2 edges where n is the number of nodes in the graph.

Weighted Graph:In a weighted graph, each edge is assigned with some data such as length or weight.
The weight of an edge e can be given as w(e) which must be a positive (+) value indicating the cost of
traversing the edge.

Digraph:A digraph is a directed graph in which each edge of the graph is associated with some direction
and the traversing can be done only in the specified direction.

Loop:An edge that is associated with the similar end points can be called as Loop.

Adjacent Nodes:If two nodes u and v are connected via an edge e, then the nodes u and v are called as
neighbours or adjacent nodes.

Degree of the Node:A degree of a node is the number of edges that are connected with that node. A node
with degree 0 is called as isolated node.

3. Explain about representation of graph(imp)

While representing graphs, we must carefully depict the elements (vertices and edges) present in the graph and the
relationship between them. Pictorially, a graph is represented with a finite set of nodes and connecting links between
them. However, we can also represent the graph in other most commonly used ways, like −
 Adjacency Matrix
 Adjacency List

Adjacency Matrix
The Adjacency Matrix is a V×V matrix where the values are filled with either 0 or 1. If the link exists between Vi and Vj,
it is recorded 1; otherwise, 0.
The adjacency matrix –

The adjacency matrix is −

Lvr Degree College

Adjacency List
The adjacency list is a list of the vertices directly connected to the other vertices in the graph.

The adjacency list is −

Lvr Degree College

4. Explain about DFS AND BFS (imp)

1.Depth First Search Traversal (DFS)

Depth First Search is a traversal algorithm that visits all the vertices of a graph in the decreasing order of its depth. In
this algorithm, an arbitrary node is chosen as the starting point and the graph is traversed back and forth by marking
unvisited adjacent nodes until all the vertices are marked.
The DFS traversal uses the stack data structure to keep track of the unvisited nodes.
EXAMPLE:

Lvr Degree College

Lvr Degree College
Lvr Degree College
2.Breadth First Search Traversal(BFS)
Breadth First Search is a traversal algorithm that visits all the vertices of a graph present at one level of the depth
before moving to the next level of depth. In this algorithm, an arbitrary node is chosen as the starting point and the
graph is traversed by visiting the adjacent vertices on the same depth level and marking them until there is no vertex
left.
The DFS traversal uses the queue data structure to keep track of the unvisited nodes.
EXAMPLE:

Lvr Degree College

Lvr Degree College
5. Explain about Sparse Matrix (imp)

In computer programming, a matrix can be defined with a 2-dimensional array. Any array with 'm' columns
and 'n' rows represent a m X n matrix. There may be a situation in which a matrix contains more number of
ZERO values than NON-ZERO values. Such matrix is known as sparse matrix.

Array Representation
In this representation, we consider only non-zero values along with their row and column index values. In
this representation, the 0th row stores the total number of rows, total number of columns and the total number
of non-zerovalues in the sparse matrix.

For example, consider a matrix of size 5 X 6 containing 6 number of non-zero values. This matrix can be
represented as

In above example matrix, there are only 6 non-zero elements ( those are 9, 8, 4, 2, 5 & 2) and matrix size is
5 X 6. We represent this matrix as shown in the above image. Here the first row in the right side table is
filled with values 5, 6 & 6 which indicates that it is a sparse matrix with 5 rows, 6 columns & 6 non-zero
values. The second row is filled with 0, 4, & 9 which indicates the non-zero value 9 is at the 0th-row 4th
column in the Sparse matrix. In the same way, the remaining non-zero values also follow a similar pattern.

6. Explain about minimum Spanning trees (imp)

A minimum spanning tree can be defined as the spanning tree in which the sum of the
weights of the edge is minimum. The weight of the spanning tree is the sum of the weights
given to the edges of the spanning tree. In the real world, this weight can be considered as
the distance, traffic load or any random value.

Algorithms for Minimum spanning tree

A minimum spanning tree can be found from a weighted graph by using the
algorithms given below –

1.Prim's Algorithm
2.Kruskal's Algorithm

1.Prim's algorithm - It is a greedy algorithm that starts with an empty spanning tree. It is
used to find the minimum spanning tree from the graph. This algorithm finds the subset of
Lvr Degree College
edges that includes every vertex of the graph such that the sum of the weights of the edges
can be minimized.
Example:

The working of prim's algorithm using an example. It will be easier to understand the
prim's algorithm using an example.

Suppose, a weighted graph is -

Step 1 - First, we have to choose a vertex from the above graph. Let's choose B.

Step 2 - Now, we have to choose and add the shortest edge from vertex B. There are two
edges from vertex B that are B to C with weight 10 and edge B to D with weight 4. Among the
edges, the edge BD has the minimum weight. So, add it to the MST.

Step 3 - Now, again, choose the edge with the minimum weight among all the other edges. In
this case, the edges DE and CD are such edges. Add them to MST and explore the adjacent of
C, i.e., E and A. So, select the edge DE and add it to the MST.

Lvr Degree College

Step 4 - Now, select the edge CD, and add it to the MST.

Step 5 - Now, choose the edge CA. Here, we cannot select the edge CE as it would create a
cycle to the graph. So, choose the edge CA and add it to the MST.

So, the graph produced in step 5 is the minimum spanning tree of the given graph.
The cost of the MST is given below –
Cost of MST = 4 + 2 + 1 + 3 = 10 units.

2.Kruskal's algorithm - This algorithm is also used to find the minimum spanning tree
for a connected weighted graph. Kruskal's algorithm also follows greedy approach,
which finds an optimum solution at every stage instead of focusing on a global
optimum.

Example:

The working of Kruskal's algorithm using an example. It will be easier to understand

Kruskal's algorithm using an example.

Suppose a weighted graph is -

Lvr Degree College

The weight of the edges of the above graph is given in the below table -

Edge AB AC AD AE BC CD DE

Weight 1 7 10 5 3 4 2

Now, sort the edges given above in the ascending order of their weights.

Edge AB DE BC CD AE AC AD

Weight 1 2 3 4 5 7 10

Now, let's start constructing the minimum spanning tree.

Step 1 - First, add the edge AB with weight 1 to the MST.

Step 2 - Add the edge DE with weight 2 to the MST as it is not creating the cycle.

Step 3 - Add the edge BC with weight 3 to the MST, as it is not creating any cycle or
loop.

Lvr Degree College

Step 4 - Now, pick the edge CD with weight 4 to the MST, as it is not forming the
cycle.

Step 5 - After that, pick the edge AE with weight 5. Including this edge will create the
cycle, so discard it.

Step 6 - Pick the edge AC with weight 7. Including this edge will create the cycle, so
discard it.

Step 7 - Pick the edge AD with weight 10. Including this edge will also create the
cycle, so discard it.

So, the final minimum spanning tree obtained from the given weighted graph by using
Kruskal's algorithm is -

The cost of the MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

7.explain about application of graphs (imp)

 In Computer science graphs are used to represent the flow of computation.

 Google maps uses graphs for building transportation systems, where intersection of two(or more) roads
are considered to be a vertex and the road connecting two vertices is considered to be an edge, thus their
navigation system is based on the algorithm to calculate the shortest path between two vertices.

 In World Wide Web, web pages are considered to be the vertices. There is an edge from a page u to other
page v if there is a link of page v on page u. This is an example of Directed graph. It was the basic idea
behind Google Page Ranking Algorithm.

Lvr Degree College

 In mapping system we use graph. It is useful to find out which is an excellent place from the location as
well as your nearby location. In GPS we also use graphs.

 Facebook uses graphs. Using graphs suggests mutual friends. it shows a list of the f following pages,
friends, and contact list.

 Microsoft Excel uses DAG means Directed Acyclic Graphs.

 On social media sites, we use graphs to track the data of the users. liked showing preferred post
suggestions, recommendations, etc.

 Graphs are used in biochemical applications such as structuring of protein, DNA etc.

textbooks reffered :

1.Data Structures Through C-Yashavant Kanetkar

2.Data Structures Using C 2nd Edition Aaron M Tenenbaum

websites reffered:

1.https://www.geeksforgeeks.org

2.https://www.javatpoint.com

3.https://github.com

Thanks for supporting

Lvr Degree College