Name Subhranshu Pati
Semester 2nd Sem
Roll Number 2414500297
Course Code & Name DCA –1207 DATA STRUCTURES
Program Bachelors of Computer Application
Set-1
Q1. What do you understand by Algorithm Complexity? Discuss Time and Space Complexity
in detail by taking suitable examples.
Ans:-
Complexity of an algorithm is the quantity of resources needed by an algorithm to resolve a
problem. These main resources consist of time and space (memory). Complexity can be used
to understand why algorithms exist and how to compare algorithms respectively so that they
can select the most effective algorithm to perform a particular task.
Time Complexity is the attribute of an Algorithm that gauges how much time is required to run
the algorithm given a size of input. It gives an upper radius of the performance as well as is
often stated with an asterisk O notation (e.g., O(n), O(n2), O(log n)). As an example, a linear
search algorithm applied to a list containing n elements which verifies each of the elements
takes time where as a binary search algorithm which at each step halves the list takes time.
Example:
• Linear Search: O(n)
• Binary Search: O(log n)
• Bubble Sort: O(n^2)
• Merge Sort: O(n log n)
The space Complexity is the size of memory that an algorithm uses. It contains the input, as
well as the auxiliary space (temporary variables, call stacks, etc.).
Example:
• A recursive Fibonacci function uses O(n) space due to call stack usage.
• An iterative version uses O(1) auxiliary space.
To write scalable efficient algorithms, understanding the time and space complexity is
important. As an example, an O(n log n) sorting algorithm is usually advantageous compared
to O(n 2), particularly when presented with large inputs. On the same note, an algorithm that
has a low space complexity is perfectly applicable in memory limited settings.
Through learning the complexities of an algorithm, a programmer can be able to make sure that
their programs efficiently execute, especially with large sets of data or with limited resource
inputs.
Q2. Write an algorithm to find a particular number in an array and replace it with some other
value.
Ans:-
Problem Statement:
Write an algorithm when there is an array, find the specific number (target) and instead of that
number, put another number (replacement).
Algorithm:
1. Start
2. Input the size of the array (n)
3. Input the array elements
4. Input the target number to find
5. Input the replacement number
6. Loop from i = 0 to n-1 a. If array[i] == target, then i. Replace array[i] with replacement
7. Print the modified array
8. End
Example Implementation in Pseudocode:
Input: arr[] = {2, 4, 6, 4, 8}, target = 4, replacement = 9
Output: arr[] = {2, 9, 6, 9, 8}
Explanation:
The algorithm traverses through the array and in instances they encounter an element similar
to the target, they convert this element to new value. This method is used to make sure that
every instance of target value is substituted. Time complexity is O(n) and space complexity is
O(1) which is for in-place swap.
Such a form of an algorithm is applicable in many areas including search-and-replace
interactions in text editing, database record updates, and data modifications in data analytics
activities.
Q3. Explain the working of a Queue data structure. What are its applications in real-world
scenarios?
Ans:-
Queues Queue is a non-circular linear structure that has the First In First Out (FIFO) rule. What
this entails is that the first element added will be the one removed first. It is like a queue at a
ticket counter someone gets on and someone gets off at the other end.
Operations in a Queue:
1. Enqueue – Add an element to the rear of the queue
2. Dequeue – Remove an element from the front
3. Peek – Get the front element without removing it
4. isEmpty – Check if the queue is empty
5. isFull – Check if the queue is full (for bounded queues)
Implementation:
Queues can either be with the use of arrays or linked lists. Circular queues are very common
where space is utilized adequately.
Example of Queue Usage in Code:
queue<int> q;
q.push(10); // Enqueue
q.pop(); // Dequeue
Real Life Uses of Queue:
• Operating Systems: The process scheduling and print queues use queues as operating
systems.
• Customer Service Systems: Queues are used in the call centers to regulate phone calls.
• Network Routers: It queues the data packets and then processes them.
• Simulation Systems: Simulations also organize events with the help of queues.
• Breadth-First Search: BFS algorithm on graphs traverses a graph level-3-by-level
based on the use of a queue.
Queues are indispensable with regard to processing data with regard to which order of
processing is important. They create equitable entry and an effective processing of the system
that uses sequential execution of tasks.
SET-2
Q4. What is a linked list and its types? Discuss the benefits of using them over array in detail.
Ans:-
A linked list is a linear data structure where each element, called a node, contains two parts:
1. Data: Stores the actual data.
2. Pointer (or link): Points to the next node in the sequence.
Linked lists differ with arrays because they do not keep data elements in consecutive memory
addresses. It is this kind of dynamism in memory allocation that makes linked lists to be flexible
with respect to memory management.
Types of Linked Lists:
1. Singly Linked List:
o Each node points to the next node.
o The last node points to NULL.
o Traversal is one-directional.
o Example: A → B → C → NULL
2. Doubly Linked List:
o Each node contains two pointers: one for the next node and one for the previous
node.
o Allows two-way traversal.
o Example: NULL ← A ↔ B ↔ C → NULL
3. Circular Linked List:
o The last node points to the first node.
o Can be singly or doubly linked.
o No NULL pointers; it loops continuously.
4. Doubly Circular Linked List:
o A circular version of a doubly linked list.
o Each node points to both its previous and next node.
o The head’s previous points to the tail and the tail’s next points to the head.
Advantages of Linked Lists Over Arrays:
1. Dynamic Memory Allocation:
o Linked lists use memory as needed. Arrays require pre-defining the size.
2. Efficient Insertion/Deletion:
o Adding/removing elements in a linked list is faster, especially in the middle, as
it involves pointer updates.
o In arrays, this requires shifting elements.
3. No Wasted Space:
o Arrays may waste memory if not fully used. Linked lists use only the memory
they need.
4. Implementation of Advanced Data Structures:
o Data structures like stacks, queues, graphs, and hash tables can be efficiently
implemented using linked lists.
5. Size Flexibility:
o Arrays are of fixed size, while linked lists can grow or shrink during runtime.
Of the linked lists, their cons include:
o Access speed is slower (there is no indexing of this kind as in A arrays).
o Will need additional memory (one pointer on every node).
o Complex navigations and control.
Finally, the arrays are easy and quick to work with (static data), but the linked lists are more
suitable when it comes to dynamic data, frequent operations of insertion/delete, or memory
optimization.
Q5. What is a doubly circular queue? Write an algorithm to display the contents of the circular
queue.
Ans:-
Double Circular Queue:
Doubly Circular Queue is a specific type of queue which has both features of doubly linked list
and the circular queue.
• In doubly linked list, each node have two pointer:
o One that indicates the next numb (next)
o One that will reference the former node (prev)
• A last node in such a circular structure has an edge back to the starting node.
In this way, in a doubly circular queue:
• The last node has its next as the first node
• The first of these nodes contains prev that points to last node
Such array may be traversed both forward and backward, and provides a loop structure,
producing repeated execution of queue operations without needing to reset any indexes.
Features:
• Supports-FIRST in FIRST out principle.
• Fast inserting and deleting at both end.
• Applied in real-time systems such as circular buffers, scheduling algorithms and media
players, etc.
Algorithm to Display Contents of a Doubly Circular Queue:
Algorithm DisplayDoublyCircularQueue(front):
1. If front is NULL:
Print "Queue is empty"
Exit
2. Initialize temp ← front
3. Do:
Print temp → data
temp ← temp → next
While temp != front
Explanation:
• We start from the front of the queue.
• Traverse using the next pointer.
• Since it's circular, the loop continues until we return to the front.
• This ensures that all elements are printed in a circular fashion.
Sample Code (C++-like Syntax):
struct Node {
int data;
Node* next;
Node* prev;
};
void display(Node* front) {
if (front == NULL) {
cout << "Queue is empty";
return;
Node* temp = front;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != front);
Advantages of Doubly Circular Queue:
• Bidirectional traversal.
• Efficient in memory usage due to circular nature.
• Easy to implement Deque (Double-Ended Queue).
• Avoids underflow/overflow errors seen in static circular queues (array-based).
Applications:
• Media playlist cycling.
• Real-time systems with continuous looping.
• CPU scheduling.
• Gaming logic like players rotating turns.
Q6. Write an algorithm for Merge Sort and explain its divide-and-conquer approach.
Ans:-
What is Merge Sort:
Merge Sort is a sorting algorithm by divide and conquer. It operates by subdividing the unsorted
list in progressively smaller sublists until each sublist contains one element then combines
those sublists in a manner that yields a sorted list.
Divide-and-Conquer Approach:
Merge Sort follows three main steps:
1. Divide – Split the array into two halves.
2. Conquer – Recursively sort each half.
3. Combine – Merge the sorted halves to produce a sorted array.
This recursive nature makes merge sort highly efficient, especially for large datasets.
Characteristics:
• Time Complexity: O(n log n) in all cases (best, average, worst).
• Space Complexity: O(n) – it needs temporary arrays for merging.
• Stable Sort: Maintains relative order of equal elements.
• Non-Adaptive: Doesn't check if array is already sorted.
Algorithm for Merge Sort:
Let A be the array to sort, low be the starting index, and high be the ending index.
MergeSort(A, low, high):
1. If low < high then:
2. mid ← (low + high) / 2
3. MergeSort(A, low, mid)
4. MergeSort(A, mid + 1, high)
5. Merge(A, low, mid, high)
Merge(A, low, mid, high):
1. Create temporary arrays:
Left[] = A[low...mid], Right[] = A[mid+1...high]
2. Set i = 0, j = 0, k = low
3. While i < length(Left) and j < length(Right):
If Left[i] ≤ Right[j]:
A[k] = Left[i]
i++
Else:
A[k] = Right[j]
j++
k++
4. Copy any remaining elements:
While i < length(Left): A[k++] = Left[i++]
While j < length(Right): A[k++] = Right[j++]
Example:
Sort the array: [8, 4, 5, 2, 9, 1]
1. Divide:
[8, 4, 5] and [2, 9, 1]
o
[8] [4, 5] → [4] [5]
o
[2] [9, 1] → [9] [1]
o
2. Conquer & Merge:
o [4] + [5] → [4, 5], then [8] + [4, 5] → [4, 5, 8]
o [9] + [1] → [1, 9], then [2] + [1, 9] → [1, 2, 9]
o Final merge: [4, 5, 8] + [1, 2, 9] → [1, 2, 4, 5, 8, 9]
Use Cases:
• External sorting (e.g., large datasets in files).
• Stable sorting needs like sorting students by name, keeping ID order.
• Linked list sorting.
Conclusion:
Merge Sort is a very powerful and a consistent algorithm that is based on divide-and-conquer
paradigm. Even though it has a worse space usage compared to some in-place algorithms like
Quick Sort, it's inevitable to have higher predictive P.O. and stability cause for a sort method.
