Explain complexity of an algorithm.

Is
there any time-space trade-off between
the complexity.
The trade-offs between time and space complexity are often inversely
proportional, meaning that improving one may worsen the other. For
example, a hash table is a data structure that can perform insertions,
deletions, and searches in constant time, O(1), regardless of the input
size.

What Is Time Complexity?

Time complexity is defined in terms of how many times it takes to run a given algorithm,
based on the length of the input. Time complexity is not a measurement of how much
time it takes to execute a particular algorithm because such factors as programming
language, operating system, and processing power are also considered.

Time complexity is a type of computational complexity that describes the time required
to execute an algorithm.

What Is Space Complexity?

When an algorithm is run on a computer, it necessitates a certain amount of memory

space. The amount of memory used by a program to execute it is represented by its
space complexity. Because a program requires memory to store input data and
temporal values while running, the space complexity is auxiliary and input space.

Know about Algorithm Complexity:

Complexity in algorithms refers to the amount of resources (such as time or
memory) required to solve a problem or perform a task. The most common
measure of complexity is time complexity, which refers to the amount of time
an algorithm takes to produce a result as a function of the size of the input.

Advantages of Algorithms
 Easy to understand: Since it is a stepwise representation of a solution to
a given problem, it is easy to understand.
 Language Independent: It is not dependent on any programming
language, so it can easily be understood by anyone.
 Debug / Error Finding: Every step is independent / in a flow so it will be
easy to spot and fix the error.
 Sub-Problems: It is written in a flow so now the programmer can divide
the tasks which makes them easier to code.
Disadvantages of Algorithms
 Creating efficient algorithms is time-consuming and requires good logical
skills.
 Nasty to show branching and looping in algorithms.

 Compressed or Uncompressed data

 Re Rendering or Stored images
 Smaller code or loop unrolling
 Lookup tables or Recalculation
A space-time trade-off can be applied
to the problem of data storage. If data stored is uncompressed, it takes
more space but less time. But if the data is stored compressed, it takes less
space but more time to run the decompression algorithm.

Re-Rendering or Stored images: In this case, storing only the source and
rendering it as an image would take more space but less time i.e., storing an
image in the cache is faster than re-rendering but requires more space in
memory.

Smaller code or Loop Unrolling: Smaller code occupies less space in

memory but it requires high computation time that is required for jumping
back to the beginning of the loop at the end of each iteration. Loop unrolling
can optimize execution speed at the cost of increased binary size. It
occupies more space in memory but requires less computation time.

Lookup tables or Recalculation: In a lookup table, an implementation can

include the entire table which reduces computing time but increases the
amount of memory needed. It can recalculate i.e., compute table entries as
needed, increasing computing time but reducing memory requirements.

Write the algorithm for Quick Sort.

 Quick Sort Algorithm. Step 1: Initialize two pointers, i and j, at the
beginning and end of the array (excluding the pivot). Step 2:
Increment i until you find an element greater than or equal to the pivot.
Step 3: Decrement j until you find an element less than or equal to the
pivot.

QuickSort is a sorting algorithm based on the Divide and Conquer

algorithm that picks an element as a pivot and partitions the given array
around the picked pivot by placing the pivot in its correct position in the
sorted array.

How does QuickSort work?

The key process in quickSort is a partition(). The target of partitions is to
place the pivot (any element can be chosen to be a pivot) at its correct
position in the sorted array and put all smaller elements to the left of the
pivot, and all greater elements to the right of the pivot.
Partition is done recursively on each side of the pivot after the pivot is placed
in its correct position and this finally sorts the array.

Algorithm
Algorithm:

1. QUICKSORT (array A, start, end)

2. {
3. 1 if (start < end)
4. 2{
5. 3 p = partition(A, start, end)
6. 4 QUICKSORT (A, start, p - 1)
7. 5 QUICKSORT (A, p + 1, end)
8. 6 }
9. }

Partition Algorithm:

The partition algorithm rearranges the sub-arrays in a place.

1. PARTITION (array A, start, end)

2. {
3. 1 pivot ? A[end]
4. 2 i ? start-1
5. 3 for j ? start to end -1 {
6. 4 do if (A[j] < pivot) {
7. 5 then i ? i + 1
8. 6 swap A[i] with A[j]
9. 7 }}
10. 8 swap A[i+1] with A[end]
11. 9 return i+1
12. }

Working of Quick Sort Algorithm

Let the elements of array are -

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 -
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, piv

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 -
What is the need of dynamic data
structure? Discuss.
Data structure is a way of storing and organizing data efficiently such that
the required operations on them can be performed be efficient with respect
to time as well as memory. Simply, Data Structure are used to reduce
complexity (mostly the time complexity) of the code. Data structures can be
two types : 1. Static Data Structure 2. Dynamic Data Structure

A dynamic data structure has a dynamic size, that is, its size can grow
and shrink based on the elements present in it at runtime. It makes
efficient use of memory by using only that amount of space in memory
that is required at any time. Dynamic memory allocation can be done
in both the stack and the heap.
What is a Static Data structure?
In Static data structure the size of the structure is fixed. The content of the data
structure can be modified but without changing the memory space allocated to it.

Example of Static Data Structures: Array

What is Dynamic Data Structure?

In Dynamic data structure the size of the structure is not fixed and can be
modified during the operations performed on it. Dynamic data structures are
designed to facilitate change of data structures in the run time.
Example of Dynamic Data Structures: Linked List

Example for Dynamic Data Structure

Some major examples of the dynamic data structures include -

1. Vector
2. Linked List
3. Stack
4. Queue
5. Tree

Static Data Structure vs Dynamic Data Structure

 Static data structures, such as arrays, have a fixed size and are allocated
at compile-time. This means that their memory size cannot be changed
during program execution. Index-based access to elements is fast and
efficient since the address of the element is known.
 Dynamic data structures, on the other hand, have a variable size and are
allocated at run-time. This means that their memory size can be changed
during program execution. Memory can be dynamically allocated or
deallocated during program execution. Due to this dynamic nature,
accessing elements based on index may be slower as it may require
memory allocation and deallocation.
Aspect Static Data Structure Dynamic Data Structure

Memory Memory is allocated at

Memory is allocated at run-time
allocation compile-time

Size is fixed and cannot be

Size Size can be modified during runtime
modified

Memory Memory utilization may be Memory utilization is efficient as

utilization inefficient memory can be reused
 Access time is faster as it is Access time may be slower due to
Access
fixed indexing and pointer usage

Arrays, Stacks, Queues, Trees Lists, Trees (with variable size), Hash
Examples
(with fixed size) tables
What is the need of dynamic data structure?
The main advantage of dynamic data structures is their flexibility. They can grow or
shrink as needed, which makes them more efficient for large data sets.

Advantages and Disadvantages of Dynamic Data Structures

The advantages of the dynamic data structures are listed below.

1. It makes efficient use of space in the memory.

2. It only uses that amount of space that is needed at any time for storage.
3. The unused space of the memory can be returned to the system for other purposes.

However, the disadvantages of the dynamic data structures are as follows:

1. It is difficult to program the dynamic data structures as the system needs to keep track of
the size and data item's locations at all times.
2. Since the memory allocation is dynamic, there is a possibility
of overflow and underflow in case the structure exceeds its maximum limit or if the
structure becomes empty respectively.
3. It is slow for implementing searches such as accessing an element in a linked list takes a
linear time.

Differentiate between external and

internal nodes.
An internal node (also known as an inner node, inode for short, or
branch node) is any node of a tree that has child nodes. Similarly, an
external node (also known as an outer node, leaf node, or terminal
node) is any node that does not have child nodes.
The nodes from the original tree are internal nodes and the special
nodes are external nodes. All external nodes are leaf nodes and the
internal nodes are non-leaf nodes. Every internal node has exactly two
children and every external node is a leaf.
Discuss various types of arrays and write the
formula to find address of an element in an
array if base address of the array is known.

Types of Arrays
There are majorly three types of arrays:
1. One-dimensional array (1-D arrays)
2. Two-dimensional (2D) array
3. Three-dimensional array

You can imagine a 1d array as a row, where elements are stored one after
another.

1D array

Syntax for Declaration of Single Dimensional Array

Below is the syntax to declare the single-dimensional array

data_type array_name[array_size];
where,
 data_type: is a type of data of each array block.
 array_name: is the name of the array using which we can refer to it.
 array_size: is the number of blocks of memory array going to have.
For Example
int nums[5];

A 1-dimensional array (or single-dimension array) is a type of linear array.

Accessing its elements involves a single subscript that can either represent a
row or column index.
Example:

1-D array

To find the address of an element in an array the following formula is used-

Address of A[I] = B + W * (I – LB)
I = Subset of element whose address to be found,
B = Base address,
W = Storage size of one element store in any array(in byte),
LB = Lower Limit/Lower Bound of subscript(If not specified assume zero).
Example: Given the base address of an array A[1300 …………
1900] as 1020 and the size of each element is 2 bytes in the memory, find
the address of A[1700].
Solution:
Given:
Base address B = 1020
Lower Limit/Lower Bound of subscript LB = 1300
Storage size of one element store in any array W = 2 Byte
Subset of element whose address to be found I = 1700
Formula used:
Address of A[I] = B + W * (I – LB)
Solution:
Address of A[1700] = 1020 + 2 * (1700 – 1300)
= 1020 + 2 * (400)
= 1020 + 800
Address of A[1700] = 1820

Multidimensional arrays can be considered as an array of arrays or as a

matrix consisting of rows and columns.

2D array

Syntax for Declaration of Two-Dimensional Array

Below is the syntax to declare the Two-dimensional array
data_type array_name[sizeof_1st_dimension][sizeof_2nd_dimension];
where,
 data_type: is a type of data of each array block.
 array_name: is the name of the array using which we can refer to it.
 sizeof_dimension: is the number of blocks of memory array going to
have in the corresponding dimension.
For Example
int nums[5][10];

The 2-dimensional array can be defined as an array of arrays. The 2-

Dimensional arrays are organized as matrices which can be represented as
the collection of rows and columns as array[M][N] where M is the number of
rows and N is the number of columns.
Example:
 2-D array

To find the address of any element in a 2-Dimensional array there are the
following two ways-
1. Row Major Order
2. Column Major Order
1. Row Major Order:
Row major ordering assigns successive elements, moving across the rows
and then down the next row, to successive memory locations. In simple
language, the elements of an array are stored in a Row-Wise fashion.
To find the address of the element using row-major order uses the following
formula:
Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))
I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in an array(in byte),
LR = Lower Limit of row/start row index of the matrix(If not given assume it
as zero),
LC = Lower Limit of column/start column index of the matrix(If not given
assume it as zero),
N = Number of column given in the matrix.
Example: Given an array, arr[1………10][1………15] with base
value 100 and the size of each element is 1 Byte in memory. Find the
address of arr[8][6] with the help of row-major order.
Solution:
Given:
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of column given in the matrix N = Upper Bound – Lower Bound + 1
= 15 – 1 + 1
= 15
Formula:
Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))
Solution:
Address of A[8][6] = 100 + 1 * ((8 – 1) * 15 + (6 – 1))
= 100 + 1 * ((7) * 15 + (5))
= 100 + 1 * (110)
Address of A[I][J] = 210
2. Column Major Order:
If elements of an array are stored in a column-major fashion means moving
across the column and then to the next column then it’s in column-major
order. To find the address of the element using column-major order use the
following formula:
Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))
I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in any array(in byte),
LR = Lower Limit of row/start row index of matrix(If not given assume it as
zero),
LC = Lower Limit of column/start column index of matrix(If not given assume
it as zero),
M = Number of rows given in the matrix.
Example: Given an array arr[1………10][1………15] with a base value
of 100 and the size of each element is 1 Byte in memory find the address of
arr[8][6] with the help of column-major order.
Solution:
Given:
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of Rows given in the matrix M = Upper Bound – Lower Bound + 1
= 10 – 1 + 1
= 10
Formula: used
Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))
Address of A[8][6] = 100 + 1 * ((6 – 1) * 10 + (8 – 1))
= 100 + 1 * ((5) * 10 + (7))
= 100 + 1 * (57)
Address of A[I][J] = 157

A 3-D Multidimensional array contains three dimensions, so it can be

considered an array of two-dimensional arrays.

3D array

Syntax for Declaration of Three-Dimensional Array

Below is the syntax to declare the Three-dimensional array
data_type
array_name[sizeof_1st_dimension][sizeof_2nd_dimension][sizeof_3rd_dim
ension];

where,
 data_type: is a type of data of each array block.
 array_name: is the name of the array using which we can refer to it.
 sizeof_dimension: is the number of blocks of memory array going to
have in the corresponding dimension.

For Example
 int nums[5][10][2];
A 3-Dimensional array is a collection of 2-Dimensional arrays. It is specified
by using three subscripts:
1. Block size
2. Row size
3. Column size
More dimensions in an array mean more data can be stored in that array.
Example:

3-D array

To find the address of any element in 3-Dimensional arrays there are the
following two ways-
 Row Major Order
 Column Major Order
1. Row Major Order:
To find the address of the element using row-major order, use the following
formula:
Address of A[i][j][k] = B + W *(P* N * (i-x) + P*(j-y) + (k-z))
Here:
B = Base Address (start address)
W = Weight (storage size of one element stored in the array)
M = Row (total number of rows)
N = Column (total number of columns)
P = Width (total number of cells depth-wise)
x = Lower Bound of Row
y = Lower Bound of Column
z = Lower Bound of Width

Example: Given an array, arr[1:9, -4:1, 5:10] with a base value of 400 and
the size of each element is 2 Bytes in memory find the address of
element arr[5][-1][8] with the help of row-major order?
Solution:
Given:
Block Subset of an element whose address to be found I = 5
Row Subset of an element whose address to be found J = -1
Column Subset of an element whose address to be found K = 8
Base address B = 400
Storage size of one element store in any array(in Byte) W = 2
Lower Limit of blocks in matrix x = 1
Lower Limit of row/start row index of matrix y = -4
Lower Limit of column/start column index of matrix z = 5
M(row) = Upper Bound – Lower Bound + 1 = 1 – (-4) + 1 = 6
N(Column)= Upper Bound – Lower Bound + 1 = 10 – 5 + 1 = 6

Formula used:
Address of[I][J][K] =B + W (M * N(i-x) + N *(j-y) + (k-z))
Solution:
Address of arr[5][-1][8] = 400 + 2 * {[6 * 6 * (5 – 1)] + 6 * [(-1 + 4)]} + [8 – 5]
= 400 + 2 * (6*6*4)+(6*3)+3
= 400 + 2 * (165)
= 730

2. Column Major Order:

To find the address of the element using column-major order, use the
following formula:1
Address of A[i][j][k]= B + W(M * N(i – x) + M *(k – z) + (j – y))
Here:
B = Base Address (start address)
W = Weight (storage size of one element stored in the array)
M = Row (total number of rows)
N = Column (total number of columns)
P = Width (total number of cells depth-wise)
x = Lower Bound of block (first subscipt)
y = Lower Bound of Row
z = Lower Bound of Column

Example: Given an array arr[1:8, -5:5, -10:5] with a base value of 400 and
the size of each element is 4 Bytes in memory find the address of
element arr[3][3][3] with the help of column-major order?
Solution:
Given:
Row Subset of an element whose address to be found I = 3
Column Subset of an element whose address to be found J = 3
Block Subset of an element whose address to be found K = 3
Base address B = 400
Storage size of one element store in any array(in Byte) W = 4
Lower Limit of blocks in matrix x = 1
Lower Limit of row/start row index of matrix y = -5
Lower Limit of column/start column index of matrix z = -10
M (row)= Upper Bound – Lower Bound + 1 = 5 +5 + 1 = 11
N (column)= Upper Bound – Lower Bound + 1 = 5 + 10 + 1 = 16
Formula used:
Address of A[i][j][k]=B+W×(M×P×(k−z)+M×(j−y)+(i−x))
Solution:
Address of arr[3][3][3] = 400 + 4 * ((11*16*(3-1)+11*(3-(-10)+(3-(-5)))
= 400 + 4 * ((176*2 + 11*13 + 8)
= 400 + 4 * (503)
= 400 + 2012
= 2412

Let A be a n*n square matrix array. Write a module which

finds the number of nonzero element in A and finds the
product of diagonal elements of A.
Differentiate between Linear Search and Binary
Search using suitable examples and write the
algorithms for both of them.
Linear Search sequentially checks each element in the list until it finds
a match or exhausts the list. Binary Search continuously divides the
sorted list, comparing the middle element with the target value. The
time complexity is O(n), where n is the number of elements in the list.

Linear Search vs Binary Search

What is a linear search?
A linear search is also known as a sequential search that simply scans each element at a
time. Suppose we want to search an element in an array or list; we simply calculate its
length and do not jump at any item.

Let's consider a simple example.

Suppose we have an array of 10 elements as shown in the below figure:

The above figure shows an array of character type having 10 values. If we want to search
'E', then the searching begins from the 0th element and scans each element until the
element, i.e., 'E' is not found. We cannot directly jump from the 0th element to the
4th element, i.e., each element is scanned one by one till the element is not found.

What is a Binary search?

A binary search is a search in which the middle element is calculated to check whether it
is smaller or larger than the element which is to be searched. The main advantage of
using binary search is that it does not scan each element in the list. Instead of scanning
each element, it performs the searching to the half of the list. So, the binary search takes
less time to search an element as compared to a linear search.

There are three cases used in the binary search:

Case 1: data<a[mid] then left = mid+1.

Case 2: data>a[mid] then right=mid-1

Case 3: data = a[mid] // element is found

In the above case, 'a' is the name of the array, mid is the index of the element calculated
recursively, data is the element that is to be searched, left denotes the left element of the array
and right denotes the element that occur on the right side of the array.

Let's look at the differences in a tabular form.

Basis of Linear search Binary search
comparison

Definition The linear search starts searching from It finds the position of the searched
the first element and compares each element by finding the middle
element with a searched element till the element of the array.
element is not found.

Sorted data In a linear search, the elements don't The pre-condition for the binary
need to be arranged in sorted order. search is that the elements must be
arranged in a sorted order.

Implementation The linear search can be implemented The implementation of binary search
on any linear data structure such as an is limited as it can be implemented
array, linked list, etc. only on those data structures that
have two-way traversal.

Approach It is based on the sequential approach. It is based on the divide and conquer
approach.

Size It is preferrable for the small-sized data It is preferrable for the large-size data
sets. sets.

Efficiency It is less efficient in the case of large- It is more efficient in the case of large-
size data sets. size data sets.

Worst-case In a linear search, the worst- case In a binary search, the worst-case
scenario scenario for finding the element is O(n). scenario for finding the element is
O(log2n).

Best-case In a linear search, the best-case In a binary search, the best-case

scenario scenario for finding the first element in scenario for finding the first element
the list is O(1). in the list is O(1).

Dimensional It can be implemented on both a single It can be implemented only on a

array and multidimensional array. multidimensional array.
 Linear_Search ( Array X, Value i)

 Set j to 1
 If j > n, jump to step 7
 If X[j] == i, jump to step 6
 Then, increment j by 1 i.e. j = j+1
 Go back to step 2
 Display the element i which is found at particular index i, then jump to step 8
 Display element not found in the set of input elements.
 Exit/End
Binary Search Algorithm:
In this algorithm,
 Divide the search space into two halves by finding the middle index
“mid”.

Finding the middle index “mid” in Binary Search Algorithm

 Compare the middle element of the search space with the key.
 If the key is found at middle element, the process is terminated.
 If the key is not found at middle element, choose which half will be used
as the next search space.
 If the key is smaller than the middle element, then the left side is
used for next search.
 If the key is larger than the middle element, then the right side is
used for next search.
 This process is continued until the key is found or the total search space
is exhausted.

What do you understand by Stack? How stack can be

represented in computer? Explain various operations
that can take place on a stack using each
representation with the help of algorithms

What is Stack?
Stack is a linear data structure that follows LIFO (Last In First Out)
Principle , so the last element inserted is the first to be popped out. In this
article, we will cover all the basics of Stack, Operations on Stack, its
implementation, advantages, disadvantages which will help you solve all the
problems based on Stack.

Stack is a linear data structure based on based on LIFO(Last In First Out)

principle in which the insertion of a new element and removal of an existing
element takes place at the same end represented as the top of the stack.
LIFO(Last In First Out) Principle in Stack:
This strategy states that the element that is inserted last will come out first.
You can take a pile of plates kept on top of each other as a real-life example.
The plate which we put last is on the top and since we remove the plate that
is at the top, we can say that the plate that was put last comes out first.
Representation of Stack Data Structure:
Stack follows LIFO (Last In First Out) Principle so the element which is
pushed last is popped first.

Types of Stack:
 Fixed Size Stack : As the name suggests, a fixed size stack has a fixed
size and cannot grow or shrink dynamically. If the stack is full and an
attempt is made to add an element to it, an overflow error occurs. If the
stack is empty and an attempt is made to remove an element from it, an
underflow error occurs.
 Dynamic Size Stack : A dynamic size stack can grow or shrink
dynamically. When the stack is full, it automatically increases its size to
accommodate the new element, and when the stack is empty, it
decreases its size. This type of stack is implemented using a linked list,
as it allows for easy resizing of the stack.
Basic Operations on Stack:
In order to make manipulations in a stack, there are certain operations
provided to us.
 push() to insert an element into the stack
 pop() to remove an element from the stack
 top() Returns the top element of the stack.
 isEmpty() returns true if stack is empty else false.
 isFull() returns true if the stack is full else false.
Push Operation in Stack:
Adds an item to the stack. If the stack is full, then it is said to be an Overflow
condition.
Algorithm for Push Operation:
 Before pushing the element to the stack, we check if the stack is full .
 If the stack is full (top == capacity-1) , then Stack Overflows and we
cannot insert the element to the stack.
 Otherwise, we increment the value of top by 1 (top = top + 1) and the
new value is inserted at top position .
 The elements can be pushed into the stack till we reach the capacity of
the stack.

Pop Operation in Stack:

Removes an item from the stack. The items are popped in the reversed
order in which they are pushed. If the stack is empty, then it is said to be
an Underflow condition.
Algorithm for Pop Operation:
 Before popping the element from the stack, we check if the stack
is empty .
 If the stack is empty (top == -1), then Stack Underflows and we cannot
remove any element from the stack.
 Otherwise, we store the value at top, decrement the value of top by 1 (top
= top – 1) and return the stored top value.
Top or Peek Operation in Stack:
Returns the top element of the stack.
Algorithm for Top Operation:
 Before returning the top element from the stack, we check if the stack is
empty.
 If the stack is empty (top == -1), we simply print “Stack is empty”.
 Otherwise, we return the element stored at index = top .


isEmpty Operation in Stack:
Returns true if the stack is empty, else false.
Algorithm for isEmpty Operation :
 Check for the value of top in stack.
 If (top == -1) , then the stack is empty so return true .
 Otherwise, the stack is not empty so return false .

isFull Operation in Stack :

Returns true if the stack is full, else false.
Algorithm for isFull Operation:
 Check for the value of top in stack.
 If (top == capacity-1), then the stack is full so return true .
 Otherwise, the stack is not full so return false .
Stack Implementation using Array:
Program 11: Write a program to implement stack.
Source Code:
#include<stdio.h>

#include<conio.h>

#define size 6

int top=-1,item;

int stack[size];

int pop()

if(top<0)

printf("\n stack is empty:");

return NULL;

item=stack[top--];

return item;

void push(int item)

{
 if(top>=size-1)

printf("stack is full");

else

stack[++top]=item;

void main()

int choice;

clrscr();

printf("\n Enter 0 for exit");

printf("\nEnter 1 for insertion");

printf("\nEnter 2 for deletion\nEnter your choice: ");

scanf("%d",&choice);

while(choice!=0)

switch(choice)

case 1:

printf("\nEnter item ");

scanf("%d",&choice);

push(item);

break;

case 2:

item=pop();

printf("\nitem %d deleted",item);

break;
 default:

printf("invalid selection");

fflush(stdin);

printf("\n Enter 0 for exit");

printf("\nEnter 1 for insertion");

printf("\n Enter 2 for deletion");

scanf("%d",&choice);

getch();

Output:

Figure 11.1 Figure 11.2

Explain various operations that can be performed on
queues. Also discuss the applications of queues.

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.

Inserts an element at the end of the queue i.e. at the rear end.
The following steps should be taken to enqueue (insert) data into a queue:
 Check if the queue is full.
 If the queue is full, return overflow error and exit.
 If the queue is not full, increment the rear pointer to point to the next
empty space.
 Add the data element to the queue location, where the rear is pointing.
 return success.

This operation removes and returns an element that is at the front end of the queue.
The following steps are taken to perform the dequeue operation:
 Check if the queue is empty.
 If the queue is empty, return the underflow error and exit.
 If the queue is not empty, access the data where the front is pointing.
 Increment the front pointer to point to the next available data element.
 The Return success.

This operation returns the element at the front end without removing it.
The following steps are taken to perform the front operation:
 If the queue is empty return the most minimum value.
 otherwise, return the front value.

This operation returns the element at the rear end without removing it.
The following steps are taken to perform the rear operation:
 If the queue is empty return the most minimum value.
 otherwise, return the rear value.

This operation returns a boolean value that indicates whether the queue is
empty or not.
The following steps are taken to perform the Empty operation:
 check if front value is equal to -1 or not, if yes then return true means
queue is empty.
 Otherwise return false, means queue is not empty

This operation returns a boolean value that indicates whether the queue is
full or not.
The following steps are taken to perform the isFull() operation:
 Check if front value is equal to zero and rear is equal to the capacity of
queue if yes then return true.
 otherwise return false

This operation returns the size of the queue i.e. the total number of elements
it contains.
queuename.size()
Parameters :
No parameters are passed
Returns :
Number of elements in the container

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.

 When a resource is shared among multiple consumers. Examples

include CPU scheduling, Disk Scheduling.
 When data is transferred asynchronously (data not necessarily received
at the same rate as sent) between two processes. Examples include IO
Buffers, pipes, etc.
Semaphores
 FCFS ( first come first serve) scheduling, example: FIFO queue
 Spooling in printers
 Buffer for devices like keyboard
 CPU Scheduling
 Memory management

 Queues in routers/ switches

 Mail Queues
 Variations: ( Dequeue, Priority Queue, Doubly Ended Priority Queue )

Write an algorithm to search an element

from a given linked list.
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. In simple words, a linked list consists of nodes where each
node contains a data field and a reference(link) to the next node in the list.

Types Of Linked List:

It is the simplest type of linked list in which every node contains some data
and a pointer to the next node of the same data type.
The node contains a pointer to the next node means that the node stores the
address of the next node in the sequence. A single linked list allows the
traversal of data only in one way. Below is the image for the same:
A doubly linked list or a two-way linked list is a more complex type of linked
list that contains a pointer to the next as well as the previous node in
sequence.
Therefore, it contains three parts of data, a pointer to the next node, and a
pointer to the previous node. This would enable us to traverse the list in the
backward direction as well. Below is the image for the same:

A circular linked list is that in which the last node contains the pointer to the
first node of the list.
While traversing a circular linked list, we can begin at any node and traverse
the list in any direction forward and backward until we reach the same node
we started. Thus, a circular linked list has no beginning and no end. Below is
the image for the same:

A Doubly Circular linked list or a circular two-way linked list is a more

complex type of linked list that contains a pointer to the next as well as the
previous node in the sequence. The difference between the doubly linked
and circular doubly list is the same as that between a singly linked list and a
circular linked list. The circular doubly linked list does not contain null in the
previous field of the first node. Below is the image for the same:
Search an element in a Linked List (Iterative
Approach):
Follow the below steps to solve the problem:
 Initialize a node pointer, current = head.
 Do following while current is not NULL
 If the current value (i.e., current->key) is equal to the key being
searched return true.
 Otherwise, move to the next node (current = current->next).
 If the key is not found, return false

Search an element in a Linked List (Recursive

Approach):
Follow the below steps to solve the problem:
 If the head is NULL, return false.
 If the head’s key is the same as X, return true;
 Else recursively search in the next node.

Write an algorithm to insert an element

in a linked list after a given node.
Insert a Node after a given Node in Linked List
Given a linked list, the task is to insert a new node after a given node of the
linked list.
 Insert a new node after a given node in the linked list

Example:
Input: LinkedList = 2->3->4->5, NewNode = 1, InsertAfter = 2
Output: LinkedList = 2->1->3->4->5
Input: LinkedList = , NewNode = 1, InsertAfter = 2
Output: No such node found

Given a Linked List, the task is to insert a new node in this given Linked List
at the following positions:
 At the front of the linked list
 After a given node.
 At the end of the linked list.

Approach:
To insert a node at the start/beginning/front of a Linked List, we need to:
 Make the first node of Linked List linked to the new node
 Remove the head from the original first node of Linked List
 Make the new node as the Head of the Linked List.
To insert a node after a given node in a Linked List, we need to:
 Check if the given node exists or not.
 If it do not exists,
 terminate the process.
 If the given node exists,
 Make the element to be inserted as a new node
 Change the next pointer of given node to the new node
 Now shift the original next pointer of given node to the
next pointer of new node

Approach:
To insert a node at the end of a Linked List, we need to:
 Go to the last node of the Linked List
 Change the next pointer of last node from NULL to the new node
 Make the next pointer of new node as NULL to show the end of Linked
List
2. How to Insert a Node after a Given Node in Linked List

// Insert at nth position of LinkedList

node *insertpos(node *head, int position, int data)

{
node *temp = new node(data);

if(position == 1)
{
temp -> next = head;
return temp;
}

node *curr = head;

for(int i = 1;i <= position-2 && curr != NULL; i++)

{
curr = curr -> next;
}

if(curr == NULL)
{
return head;
}

//Insertion and returning head

temp -> next = curr -> next;
curr -> next = temp;
return head;
}

What is doubly linked list? How can you

represent a doubly linked list in memory? Also
discuss the insertion and deletion operations in
a doubly list.
In computer science, a doubly linked list is a linked data structure that
consists of a set of sequentially linked records called nodes. Each
node contains three fields: two link fields (references to the previous
and to the next node in the sequence of nodes) and one data field.
What is Doubly Linked List?

A doubly linked list (DLL) is a special type of linked list in which each node contains a pointer
to the previous node as well as the next node of the linked list.

Doubly Linked List

Memory Representation of a doubly linked list

Memory Representation of a doubly linked list is shown in the following image.
Generally, doubly linked list consumes more space for every node and therefore, causes
more expansive basic operations such as insertion and deletion. However, we can easily
manipulate the elements of the list since the list maintains pointers in both the
directions (forward and backward).
 Operations on doubly linked list
Node Creation

1. struct node
2. {
3. struct node *prev;
4. int data;
5. struct node *next;
6. };
7. struct node *head;

SN Operation Description

1 Insertion at beginning Adding the node into the linked list at beginning.

2 Insertion at end Adding the node into the linked list to the end.

3 Insertion after specified Adding the node into the linked list after the specified node.
node

4 Deletion at beginning Removing the node from beginning of the list

5 Deletion at the end Removing the node from end of the list.

6 Deletion of the node Removing the node which is present just after the node containing the
having given data given data.

7 Searching Comparing each node data with the item to be searched and return the
location of the item in the list if the item found else return null.

8 Traversing Visiting each node of the list at least once in order to perform some
specific operation like searching, sorting, display, etc.
 Insertion in doubly linked list at beginning
o Allocate the space for the new node in the memory. This will be done by using
the following statement.

1. ptr = (struct node *)malloc(sizeof(struct node));

2. ptr->next = NULL;
3. ptr->prev=NULL;
4. ptr->data=item;
5. head=ptr;

6. ptr->next = head;
7. head→prev=ptr;

1. ptr→prev =NULL
2. head = ptr

Algorithm :
o Step 1: IF ptr = NULL

Write-OVERFLOW
Go-to-Step-9
[END OF IF]

o Step 2: SET NEW_NODE = ptr

o Step 3: SET ptr = ptr -> NEXT
o Step 4: SET NEW_NODE -> DATA = VAL
o Step 5: SET NEW_NODE -> PREV = NULL
o Step 6: SET NEW_NODE -> NEXT = START
o Step 7: SET head -> PREV = NEW_NODE
o Step 8: SET head = NEW_NODE
o Step 9: EXIT
Deletion at beginning
Algorithm
o STEP 1: IF HEAD = NULL

WRITE-UNDERFLOW
GOTO STEP 6

o STEP 2: SET PTR = HEAD

o STEP 3: SET HEAD = HEAD → NEXT
o STEP 4: SET HEAD → PREV = NULL
o STEP 5: FREE PTR
o STEP 6: EXIT
Insertion in doubly linked list at the end
Algorithm
o Step 1: IF PTR = NULL

Write OVERFLOW
Go to Step 11
[END OF IF]

o Step 2: SET NEW_NODE = PTR

o Step 3: SET PTR = PTR -> NEXT
o Step 4: SET NEW_NODE -> DATA = VAL
o Step 5: SET NEW_NODE -> NEXT = NULL
o Step 6: SET TEMP = START
o Step 7: Repeat Step 8 while TEMP -> NEXT != NULL
o Step 8: SET TEMP = TEMP -> NEXT

[END OF LOOP]

o Step 9: SET TEMP -> NEXT = NEW_NODE

o Step 10C: SET NEW_NODE -> PREV = TEMP
o Step 11: EXIT
Deletion in doubly linked list at the end
Algorithm

o Step 1: IF HEAD = NULL

Write-UNDERFLOW
Go-to-Step-7
[END OF IF]

o Step 2: SET TEMP = HEAD

o Step 3: REPEAT STEP 4 WHILE TEMP->NEXT != NULL
o Step 4: SET TEMP = TEMP->NEXT

[END OF LOOP]

o Step 5: SET TEMP ->PREV-> NEXT = NULL

o Step 6: FREE TEMP
o Step 7: EXIT
How do you create a Binary Search Tree?
Also explain how to delete an element from
a BST.
What is Binary Search Tree?
Binary Search Tree (BST) is a special type of binary tree in which the left
child of a node has a value less than the node’s value and the right child has
a value greater than the node’s value. This property is called the BST
property and it makes it possible to efficiently search, insert, and delete
elements in the tree.
 Basic Operations on Binary Search Tree:
1. Searching a node in BST:
The steps of searching a node in Binary Search tree are listed as follows -

1. First, compare the element to be searched with the root element of the tree.
2. If root is matched with the target element, then return the node's location.
3. If it is not matched, then check whether the item is less than the root element, if it
is smaller than the root element, then move to the left subtree.
4. If it is larger than the root element, then move to the right subtree.
5. Repeat the above procedure recursively until the match is found.
6. If the element is not found or not present in the tree, then return NULL.

Algorithm to search an element in Binary search tree

1. Search (root, item)
2. Step 1 - if (item = root → data) or (root = NULL)
3. return root
4. else if (item < root → data)
5. return Search(root → left, item)
6. else
7. return Search(root → right, item)
8. END if
9. Step 2 - END

Deletion in Binary Search tree

In a binary search tree, we must delete a node from the tree by keeping in mind that the
property of BST is not violated. To delete a node from BST, there are three possible
situations occur -

o The node to be deleted is the leaf node, or,

o The node to be deleted has only one child, and,
o The node to be deleted has two children

We will understand the situations listed above in detail.

When the node to be deleted is the leaf node

It is the simplest case to delete a node in BST. Here, we have to replace the leaf node
with NULL and simply free the allocated space.

Algorithm
Delete (TREE, ITEM)

Insertion in Binary Search tree

A new key in BST is always inserted at the leaf. To insert an element in BST, we have to
start searching from the root node; if the node to be inserted is less than the root node,
then search for an empty location in the left subtree. Else, search for the empty location
in the right subtree and insert the data.

Discuss the concept of full binary tree and complete

binary tree. Differentiate between the two using
suitable examples.

Binary Tree Data Structure

A Binary Tree Data Structure is a hierarchical data structure in which each node has at most
two children, referred to as the left child and the right child. It is commonly used in computer
science for efficient storage and retrieval of data, with various operations such as insertion,
deletion, and traversal.
Types of Binary Tree based on the number of
children:
Following are the types of Binary Tree based on the number of children:
1. Full Binary Tree
2. Degenerate Binary Tree
3. Skewed Binary Trees
1. Full Binary Tree
A Binary Tree is a full binary tree if every node has 0 or 2 children. The
following are examples of a full binary tree. We can also say a full binary tree
is a binary tree in which all nodes except leaf nodes have two children.
A full Binary tree is a special type of binary tree in which every parent
node/internal node has either two or no children. It is also known as a proper
binary tree.
Complete Binary Tree
We know a tree is a non-linear data structure. It has no limitation on the
number of children. A binary tree has a limitation as any node of the tree
has at most two children: a left and a right child.
What is a Complete Binary Tree?
A complete binary tree is a special type of binary tree where all the levels of
the tree are filled completely except the lowest level nodes which are filled
from as left as possible.

Complete Binary Tree

Some terminology of Complete Binary Tree:

 Root – Node in which no edge is coming from the parent. Example -node
A
 Child – Node having some incoming edge is called child. Example –
nodes B, F are the child of A and C respectively.
 Sibling – Nodes having the same parent are sibling. Example- D, E are
siblings as they have the same parent B.
 Degree of a node – Number of children of a particular parent. Example-
Degree of A is 2 and Degree of C is 1. Degree of D is 0.
 Internal/External nodes – Leaf nodes are external nodes and non leaf
nodes are internal nodes.
 Level – Count nodes in a path to reach a destination node. Example-
Level of node D is 2 as nodes A and B form the path.
 Height – Number of edges to reach the destination node, Root is at
height 0. Example – Height of node E is 2 as it has two edges from the
root.
 Example 2:


 A binary tree

 Height of the given binary tree is 2 and the maximum number of nodes
that should be there are 2h+1 – 1 = 22+1 – 1 = 23 – 1 = 7.
But the number of nodes in the tree is 6. Hence it is not a perfect
binary tree.
Now for a complete binary tree, It is full up to height h-1 i.e.; 1, and the
last level element are stored in left to right order. Hence this is
a complete binary tree. Store the element in an array and it will be
like;


 Element stored in an array level by level

Write Warshall’s algorithm for finding the

shortest path in a graph and explain the
algorithm with the help of a suitable
example.
Floyd-Warshall Algorithm
Floyd-Warshall Algorithm is an algorithm for finding the shortest path between
all the pairs of vertices in a weighted graph. This algorithm works for both the
directed and undirected weighted graphs. But, it does not work for the graphs
with negative cycles (where the sum of the edges in a cycle is negative).

A weighted graph is a graph in which each edge has a numerical value

associated with it.

Floyd-Warhshall algorithm is also called as Floyd's algorithm, Roy-Floyd

algorithm, Roy-Warshall algorithm, or WFI algorithm.

This algorithm follows the dynamic programming approach to find the shortest
paths.