NAME AARON FRANCIS

ROLL NUMBER 2414507868

SEMESTER II

COURSE CODE DCA1207

COURSE NAME DATA STRUCTURES

 SET-I

Q1 A.
Algorithm complexity is a measure of how many resources an algorithm will consume with
comparison to the size of the input. These resources could be time (how long the algorithm
will run) or space (how much memory it will use). Understanding complexity is one of the
most important pieces for assessing the performance of algorithms, especially on larger
datasets or systems with limited resources.

Two Major Types of Complexity

1. Time Complexity.
• Defines how the amount of time it takes for an algorithm to execute will change with
respect to the size of an input.
• It is typically even stated in big O notation (e.g. O(n), O(log n), O(n² )) to show the worst
case for the algorithm.
• For example, a linear search would have a time complexity of O(n) since it could potentially
check every element for one occurrence whereas a binary search would have time complexity
O(log n) since it is halving each time.

2. Space complexity
• Attention of memory (for input size) used by the algorithm
• That includes the memory used by variables, the input data itself, and the memory
knowledge of allocation relatively to recursive calls (if applicable).
• An efficient algorithm will consider both time and space allocations as best as it can and
limit the use of each.
Algorithm complexity helps developers and computer scientists:
 Compare algorithms that solve the same problem.
 Make decisions about trade-offs—e.g., choosing faster algorithms that use more space or
vice versa.
 Optimize performance, especially in systems where speed and memory usage are critical.

Practical Insight
Let’s say you're working with database queries, which you're already exploring—
understanding the complexity of indexing or query planning can greatly impact performance
tuning in systems like SQL.

Q1 B.
Time and Space Complexity are two of the basic measures to characterize algorithms based
on how they respond as the input size, n, increases. Once you understand both of them you
will be able to write code that executes quickly and minimizes memory consumption.
1. Time Complexity
• Definition: The manner in which the number of operations performed by an algorithm
scales with n.
• Big-O will provide you with the worst case, while Θ and Ω provide average and best cases.
Some examples:
o Linear Search (O(n)): Checks each element until it finds the target. In the worst case you
check all n items; in the best case you find it immediately (Ω(1)).
o Binary Search (O(log n)): Divides in half a sorted array repeatedly. Each comparison
divides the search space in half, so it takes about log₂n steps.
Sorting:
o Merge Sort (O(n log n) time, Θ(n log n) average and worst): Divides the array, sorts halves
recursively, then merges.
o Quick Sort: Average O(n log n), worst O(n²) when pivots are unlucky—but with random
pivoting it’s usually fast.
2. Space Complexity
• Definition: the amount of extra memory needed (in addition to the input), also expressed as
a function of n. Examples:
o Recursive Fibonacci (O(n) space): every call remains on the call stack; depth = n, so you
need linear extra space.
o Iterative Fibonacci (O(1) space): only need two variables that track the last two numbers -
only requires constant extra memory!
o Merge Sort (O(n) space): when you merge two halves, you need an additional array of size
n.
3. Trade-Offs and Best Practices
• In-place algorithms (like quick sort) save space, but perhaps you have a worse worst-case
time.
• Divide-and-conquer is faster, but it usually uses up extra memory through additional arrays
or storage.
• Always profile against realistic data, and always use Big-O to guide—not limit or decide—
your options.
Knowing about both would allow you to choose the correct tool for the job—whether you're
trying to optimize another SQL join, or if you're designing systems in real-time!

Q2.

Finding and replacing a value in an array is straightforward, yet it illustrates key

algorithmic concepts: traversal, comparison, and in-place mutation. Below is a clear,
step-by-step algorithm, its analysis, and an example walk-through.

1. Problem Statement
Given an array A of size n, an oldValue you want to replace, and a newValue,
update A so that every occurrence (or just the first, depending on requirement)
of oldValue becomes newValue.

2. Algorithm (Replace All Occurrences)

 Pseudocode:

procedure ReplaceAll(A: array of Integer, n: Integer, oldValue: Integer, newValue:

Integer)
for i ← 0 to n−1 do
if A[i] = oldValue then
A[i] ← newValue
end if
end for
end procedure

Explanation:

 We scan the array from index 0 through n−1.

 At each position i, compare A[i] to oldValue.
 If they match, overwrite A[i] with newValue.
 This runs in a single pass, modifying A in place.

3. Time and Space Complexity

 Time Complexity: O(n) because we perform one comparison (and possibly
one assignment) per element.
 Space Complexity: O(1) extra space since swaps happen in place; we only
need fixed temporaries for indices and values

4. Variant: Replace First Occurrence Only

 If you just want to swap the first match, break out of the loop on replacement
 procedure ReplaceFirst(A, n, oldValue, newValue)
 for i ← 0 to n−1 do
 if A[i] = oldValue then
 A[i] ← newValue
 break
 end if
 end for
 end procedure

This still runs in O(n) worst case, but best case O(1) if the match is at the
front

Example Walk-Through

Let A = [5, 2, 9, 2, 7], oldValue = 2, newValue = 8, n = 5.

i = 0: A[0] = 5 ≠ 2 → no change.
i = 1: A[1] = 2 = oldValue → A[1] ← 8 → A becomes [5, 8, 9, 2, 7].
i = 2: A[2] = 9 ≠ 2 → skip.
i = 3: A[3] = 2 → replace → A becomes [5, 8, 9, 8, 7].
i = 4: A[4] = 7 → skip.
Final: [5, 8, 9, 8, 7].

5. Edge Cases and Considerations

 Empty array (n = 0): Loop doesn’t execute—nothing to do.
 No matches: Array stays intact.
 All elements match: Every slot is replaced.
 Thread safety: In concurrent contexts, synchronize access if multiple threads
mutate A.

6. Optimizations & Extensions

 If A is sorted and you only replace the first (or all) occurrences, you can binary-
search for the starting index in O(log n) then scan contiguous matches—overall
O(log n + k) where k is count of matches.
 Functional languages often build a new array via map:
B = map(x → x == oldValue ? newValue : x, A)
which uses O(n) time and O(n) extra space.

By mastering this pattern—linear scan plus conditional update—you gain a template

you’ll use in data cleaning, in-memory transformations, and even SQL’s bulk UPDATE
commands. Next, we could explore how to shift and compress arrays, or how to batch-
process replacements in streaming data.

Q3.
A queue is a linear data structure that follows First-In, First-Out (FIFO). Imagine standing
in line at a café: the first customer to arrive is the first one served. A queue mirrors that
behavior in code.

Core Operations

Operation Description Time Complexity

enqueue(x) Add element x to the back O(1)

of the queue

dequeue () Remove and return the O(1)

front element

peek() / front () Inspect the front element O(1)

without removal
 isEmpty() Check if the queue has no O(1)
elements

Basic Implementation Strategies

 Array-based: Use a fixed-size or dynamically resizing array. You maintain two
indices—front and rear—to track where to dequeue and enqueue.

 Linked list: Each node holds a value and a pointer to the next node. You keep
references to both head (front) and tail (rear) for O(1) inserts and deletes.

procedure Enqueue(Q, x):

node ← new Node(value=x)
if [Link] is null then
[Link] ← node
[Link] ← node
else
[Link] ← node
[Link] ← node

procedure Dequeue(Q):
if [Link] is null then
error “Queue is empty”
value ← [Link]
[Link] ← [Link]
if [Link] is null then
[Link] ← null
return value

Real-World Applications

1. Task Scheduling
o CPU Job Queue: Operating systems schedule processes by enqueuing tasks.
Round-robin schedulers pick the next job from the front.
o Print Spooler: Documents sent to a printer are lined up so the first print job
submitted prints first.

2. Breadth-First Search (BFS)

o Used in graph and tree traversals. You enqueue neighbors level by level,
ensuring you explore nodes in increasing distance order.

3. Asynchronous Messaging
o Message Brokers (e.g., RabbitMQ, Kafka) store messages in queues so
producers and consumers can run at different speeds without dropping data.
 4. I/O Buffers
o Network packets or streaming data are buffered in queues, smoothing out
bursts of traffic and preventing data loss.

5. Customer Service Systems

o Call Centers: Incoming calls sit in a queue until an agent becomes available.

o Web Servers: HTTP requests queue up to avoid overwhelming server

resources.

Why Queues Matter

 Predictable Order: Guarantees fairness—no starvation for early arrivals.

 Simplicity: Core operations are constant‐time, making queues efficient building

blocks.

 Flexibility: Variants like circular queues, priority queues, and double-ended queues
(deques) tailor behavior to specific needs.

Beyond basic FIFO, you might explore circular queues (wrap-around indexing), priority
queues (serve highest-priority items first), or delve into back-pressure mechanisms in
distributed systems. These concepts unlock advanced patterns in high-throughput
computing and real-time streaming.

SET-II

Q4.
A linked list is a linear data structure where each element—called a node—contains data and
a reference (or pointer) to the next node in the sequence. Unlike arrays, nodes in a linked list
need not occupy contiguous memory; they can live anywhere, with pointers “linking” them
together.

Core Structure

Node {
value: any
next: Node* // pointer/reference to the next node
}

Types of Linked Lists

1. Singly Linked List

o Each node has a next pointer.
o Traversal is one‐way: head → … → tail.
 2. Doubly Linked List
o Nodes hold both next and prev pointers.

o Bi‐directional traversal: head ↔ … ↔ tail.

3. Circular Singly Linked List

o Same as singly, but tail’s next points back to head.

o Useful for round‐robin scheduling.

4. Circular Doubly Linked List

o Tail’s next → head and head’s prev → tail.
o Combines bi‐directionality with circularity.

Why Choose a Linked List Over an Array?

1. Dynamic Size
o Linked List: Grows or shrinks at runtime by allocating or freeing nodes.

o Array: Fixed size (in most languages), or costly resizing (copying all elements
to a larger block).

o Benefit: No upfront guesswork about maximum capacity; memory usage

tracks actual needs.

2. Constant‐Time Insertions/Deletions

o At Front/Middle
 In a linked list, once you have a pointer to a node, you can insert or
remove the next node in O(1) time by relinking pointers.

 In an array, inserting or deleting at any position (except the end)

requires shifting all subsequent elements—O(n) time.

o Use Case: Real‐time systems and freelists where you can’t afford O(n) shifts.

3. Efficient Memory Utilization

o No Contiguous Block Needed: Nodes can be scattered in memory, avoiding
fragmentation issues when large contiguous blocks are unavailable.

o Use Case: Embedded systems with fragmented heaps.

4. Flexible Data Structures

o Stacks, queues, and deques map naturally onto linked lists without wasted
space or re‐allocation headaches.
 o Priority queues or adjacency lists in graphs often leverage linked lists for
dynamic neighbor lists.

5. Splicing and Concatenation

o Joining two lists or cutting out a sublist can be done by redirecting a few
pointers—O(1) time for circular or doubly linked lists.

o Arrays require O(n) copying for concatenation or slicing.

Trade-Offs to Keep in Mind

 Memory Overhead: Each node stores extra pointer(s), so per‐element overhead is
higher than an array’s raw data.

 Cache Locality: Arrays benefit from contiguous memory that plays well with CPU
caches; linked lists suffer more cache misses.

 Random Access: Accessing the k-th element in a linked list is O(k), versus O(1) in an
array.

Wrap-Up
 Linked lists shine when you need dynamic, pointer‐friendly structures that prioritize
fast insertions/deletions over random access or cache performance. They’re the
backbone of many advanced data structures (graphs, LRU caches, free‐lists) and
remain a fundamental tool in your algorithmic toolkit.

Q5.
A doubly circular queue is a variant of a doubly linked list where the last node’s next
pointer links back to the first node, and the first node’s prev pointer links to the last node.
You maintain two external pointers, front and rear. When empty, both are null; after one
enqueue, front = rear = newNode, and

[Link] = front
[Link] = rear
Every enqueue/dequeue adjusts these links to preserve circularity.

Algorithm: Display Contents

procedure DisplayQueue(Q):
if [Link] is null then
print "Queue is empty"
return
end if

node ← [Link]
do
print [Link]
node ← [Link]
while node ≠ [Link]
 end procedure
Explanation
1. Check for an empty queue.

2. Start at front.
3. Use a do…while loop so you print the first node before checking the loop condition.

4. Advance node via [Link] until you cycle back to front.

This runs in O(n) time and O(1) extra space, visiting each element exactly once.

Q6.
Merge Sort is a classic divide-and-conquer sorting algorithm that achieves O(n log n) time by
repeatedly splitting the array, sorting the halves, and then merging them.

Pseudocode
procedure MergeSort(A, l, r):
if l < r then
m ← floor((l + r) / 2)
MergeSort(A, l, m) // sort left half
MergeSort(A, m + 1, r) // sort right half
Merge(A, l, m, r) // merge sorted halves

procedure Merge(A, l, m, r):

L ← copy A[l…m]
R ← copy A[m+1…r]
i ← 0; j ← 0; k ← l
while i < |L| and j < |R| do
if L[i] ≤ R[j] then
A[k] ← L[i]; i ← i + 1
else
A[k] ← R[j]; j ← j + 1
k←k+1
end while
// copy any leftovers
while i < |L| do A[k++] ← L[i++]
while j < |R| do A[k++] ← R[j++]
Divide-and-Conquer Approach

1. Divide
Split the array in half at each recursive call until you reach subarrays of size one
(trivially sorted).

2. Conquer
Recursively sort each half. Because each split halves the problem size, the recursion
depth is O(log n).
 3. Combine
The Merge step walks through both sorted halves in linear time, stitching them into a
single sorted segment. It exploits the fact that each subarray is already sorted, so
merging takes O(n) per level of recursion.

Because you do O(n) work to merge at each of the log n levels, overall time = O(n log n).
Space complexity is O(n) due to the temporary left/right arrays (though you can implement
an in-place variant with more intricate pointer juggling). Merge Sort is stable, predictable,
and ideal for sorting linked lists or external (disk‐based) data where contiguous memory and
random access are expensive.