AI&DS, Jio Institute, Navi Mumbai, India

Assignment-I Solutions
Subject: Data Structures and Algorithm (AI&DS-103) Quarter: I
th
Date of Submission: 24 April 2024 Maximum marks :10

Question 1:
a. This code segment contains a nested loop where the outer loop iterates 'n'
times, and the inner loop iterates 'i' times for each iteration of the outer loop.
The total number of iterations can be represented by the sum of the arithmetic
series from 0 to n-1, which is (n*(n-1))/2. Therefore, the time complexity is
O(n^2).
b. The loops run n times each, resulting in n^3 total iterations. The time
complexity is O(n^3).
c. Time complexity: O(log(length of array))
Let N be the length of the array.
Here we are using binary search on the array “arr” to search the element item.
Here in each search half of the array is eliminated. Thus the time complexity
can also be written as
T(N) = T(N/2) + 1.
Now T(N/2) = T(N/4) + 1 substituting it in the above equation we get T(N) =
T(N/4) + 2.
Thus T(N) = T(N/2k) + k.
Let us find the smallest integer k such that 2k >=N, thus k >= log2(N). As k is
integer k= ceil(log2(N))
Thus T(N) = T(1) + ceil(log2(N)). Since T(1) = constant , T(N)= constant+
ceil(log2(N)).
Thus we get T(N) =O( log2(N))

Question 2:
This database requires us to maintain a sequence of images ordered
extrinsically, but also support searching intrinsically for images based on their
ID. So, we will implement the database with a combination of both a sequence
data structure, specifically a doubly linked list (as implemented in PS1-4)
storing image IDs, and a set data structure, specifically a sorted array storing
pairs (x, vx) sorted by x values, where x is the ID of an image, and vx is a
pointer to the linked list node containing x.
To implement make document(), simply initialize an empty linked list L and an
empty sorted array S, each in O(1) time. There is no output to this operation, so
it is trivially correct.
To implement import image(x), add x to the front of L in node vx in O(1) time
and add (x, vx) to S in O(n) time. Delegating to these data structures ensures
that x is added to front of the sequence stored in L, and that S now contains (x,
vx) and remains sorted after insertion.
To implement display(), construct and return an array by iterating the items of
L in sequence order which can be done in O(n). To implement move below(x,
y), use binary search to find pairs (x, vx) and (y, vy) in S, each in O(log n) time.
Then we can remove node vx from L in O(1) time and insert it after node vy,
also in O(1) time, by relinking pointers. For completeness, here is one way to
relink the pointers in a doubly linked list:

Question 3:
Explanation –
f2 > f4 because we can write f2(n) = 2^(n/2)*2^(n/2), f4(n) = n^(10)*2^(n/2)
which clearly shows that f2 > f4
f4 > f3 because we can write f4(n) = n^10.〖√2〗^n = n10.(1.414)n , which
clearly shows f4> f3
f3> f1:
f1 (n) = n^√n take log both side log f1 = √n log n
f3 (n) = (1.000001)^n take log both side log f3 = n log(1.000001), we can
write as log f3 = √n*√n log(1.000001) and √n > log(1.000001).
So, correct order is f2> f4> f3> f1. Option (b) is correct.

Question 4:
For each of the following recurrences, give an expression for the runtime T (n)
if the recurrence can be solved with the Master Theorem. Otherwise, indicate
that the Master Theorem does not apply.
1. T (n) = 3T (n/4) + n log n =⇒ T (n) = Θ(n log n) (Case 3)
2. T (n) = 3T (n/3) + n/2 =⇒ T (n) = Θ(n log n) (Case 2)
3. T (n) = 6T (n/3) + n^2 log n =⇒ T (n) = Θ(n 2 log n) (Case 3)
4. T (n) = 4T (n/2) + n/ log n =⇒ T (n) = Θ(n 2 ) (Case 1)
5. T (n) = 64T (n/8) – n^2 log n =⇒ Does not apply (f(n) is not positive)
6. T (n) = 7T (n/3) + n 2 =⇒ T (n) = Θ(n 2 ) (Case 3)
7. T (n) = 4T (n/2) + log n =⇒ T (n) = Θ(n 2 ) (Case 1)
8. T (n) = T (n/2) + n(2 − cos n) =⇒ Does not apply. We are in Case 3, but
the regularity condition is violated. (Consider n = 2πk, where k is odd and
arbitrarily large. For any such choice of n, you can show that c ≥ 3/2,
thereby violating the regularity condition.)
Question 5:
1. Algorithm X:
• Divides the array into two subarrays of size n/2.
• Recursively sorts each subarray.
• Merges the sorted subarrays in linear time.
The recurrence relation for Algorithm X can be expressed as T(n) = 2T(n/2) +
O(n) for the merge operation. By using the Master Theorem, we can determine
that the time complexity of Algorithm X is O(n*log n).
2. Algorithm Y:
• Divides the array into two subarrays of size n - 1.
• Recursively sorts each subarray.
• Merges the sorted subarrays in constant time.
The recurrence relation for Algorithm Y can be expressed as T(n) = 2T(n - 1) +
O(1) for the merge operation. This can be seen as a linear recurrence relation,
and its time complexity is O(n).
3. Algorithm Z:
• Divides the array into three subarrays of size n/3.
• Recursively sorts each subarray.
• Merges the sorted subarrays in O(n*log n) time.
The recurrence relation for Algorithm Z can be expressed as T(n) = 3T(n/3) +
O(nlog n) for the merge operation. By using the Master Theorem, we can
determine that the time complexity of Algorithm Z is also O(nlog n).
Now, comparing the running times:
• Algorithm X: O(n*log n)
• Algorithm Y: O(n)
• Algorithm Z: O(n*log n)
Based on the analysis, if we're concerned about the fastest algorithm in terms of
asymptotic runtime efficiency, we would choose Algorithm X or Algorithm Z
since both have O(n*log n) time complexity. However, practical factors such as
implementation complexity and the specific characteristics of the input data
should also be considered.
Question 6:
A naive approach is to run three loops and check sum of three element form
different arrays equal to given number if find then print exist and otherwise
print not exist.
Algorithm:
 Define a function findTriplet that takes in three integer arrays a1,
a2, a3, their respective sizes n1, n2, n3, and the integer variable sum.
 Loop through each element of a1, a2, and a3 using three nested for-
loops.
 If the sum of the current triplet of elements (a1[i], a2[j], a3[k]) is
equal to sum, return true.
 If no such triplet is found, return false.
 In the main function, define three integer arrays a1, a2, a3, and the
integer variable sum.
 Get the size of each array using sizeof operator and divide it by the
size of a single element to get the size of the array in terms of
number of elements.
 Call the findTriplet function with a1, a2, a3, n1, n2, n3, and sum as
arguments.
 If the function returns true, print “Yes“. Otherwise, print “No“.
Question 7:
Solution: Reverse the order of the last half of the nodes in a list in three stages:
• find the nth node a in the sequence (the end of Jen’s line)
• for each node x from the (n + 1)st node b to the (2n)th node c, change the next
pointer of x to point to the node before it in the original sequence
• change the next pointer of a and b to point to c and nothing respectively
Finding the nth node requires traversing next pointers n−1 times from the head
of the list, which can be done in O(n) time via a simple loop.
We can compute n by halving the size of the list (which is guarenteed to be
even). To change the next pointers of the last half of the sequence, we can
maintain pointers to the current node x and the node before it xp, initially b and
a respectively.
Then, record the node xn after x, relink x to point to the xp, the node before x in
O(1) time. Then we can change the current node to xn and the node before it to
x, maintaining the desired properties for the next node to relink. Repeating n
times, relinks all n nodes in the last half of the sequence in O(n) time. Lastly, by
remembering nodes a, b, and c while the algorithm traverses the list, means that
changing the exceptional next pointers at the front and back of the last half of
the list takes O(1), leading to an O(n) time algorithm overall.
b.
Question 8:
The idea is to sort the A1[] array and then according to A2[] store the
elements.
Let the size of A1[] be m and the size of A2[] be n.
 Create a temporary array temp of size m and copy the contents of
A1[] to it.
 Create another array visited[] and initialize all entries in it as false.
visited[] is used to mark those elements in temp[] which are copied to
A1[].
 Sort temp[]
 Initialize the output index ind as 0.
 Do following for every element of A2[i] in A2[]

 Binary search for all occurrences of A2[i] in temp[], if

present then copy all occurrences to A1[ind] and increment
ind. Also mark the copied elements visited[]
 Copy all unvisited elements from temp[] to A1[]
Time complexity: O(M Log M + N Log M), Sorting Arr1[] of size M i.e M
log M and searching of Arr2[] elements of size N in Arr1[] i.e N log M
Question 9:
Sure, here are the solutions for constructing a queue using stacks and a stack
using queues in Python:

**Construct Queue Using Stack:**

```python
class QueueUsingStack:
def __init__(self):
self.stack_enqueue = []
self.stack_dequeue = []

def enqueue(self, value):

self.stack_enqueue.append(value)

def dequeue(self):
if not self.stack_dequeue:
while self.stack_enqueue:
self.stack_dequeue.append(self.stack_enqueue.pop())
return self.stack_dequeue.pop()

def peek(self):
if not self.stack_dequeue:
while self.stack_enqueue:
self.stack_dequeue.append(self.stack_enqueue.pop())
return self.stack_dequeue[-1]
 def empty(self):
return not self.stack_enqueue and not self.stack_dequeue

# Example usage:
queue = QueueUsingStack()
queue.enqueue(1)
queue.enqueue(2)
print(queue.peek()) # Output: 1
queue.dequeue()
print(queue.peek()) # Output: 2
print(queue.empty()) # Output: False
```

**Construct Stack Using Queue:**

```python
from collections import deque

class StackUsingQueue:
def __init__(self):
self.queue1 = deque()
self.queue2 = deque()

def push(self, value):

self.queue1.append(value)
while len(self.queue1) > 1:
self.queue2.append(self.queue1.popleft())
 self.queue1, self.queue2 = self.queue2, self.queue1

def pop(self):
return self.queue1.popleft()

def top(self):
return self.queue1[0]

def empty(self):
return not self.queue1

# Example usage:
stack = StackUsingQueue()
stack.push(1)
stack.push(2)
print(stack.top()) # Output: 2
stack.pop()
print(stack.top()) # Output: 1
print(stack.empty()) # Output: False
```

These implementations demonstrate how you can use one data structure to
emulate the behavior of another. In the first case, stacks are used to implement
queues, and in the second case, queues are used to implement stacks.