BITS PILANI, DUBAI CAMPUS
DUBAI INTERNATIONAL ACADEMIC CITY, DUBAI
SECOND SEMESTER 2023 - 2024
COURSE : DATA STRUCTURES & ALGORITHMS (CS F211)
COMPONENT : TUTORIAL 4 (Solution)
1. Consider array A[] based implementation of a Circular Queue. Assume that
the array's SIZE is 5 elements maximum. Show the contents of the Circular
Queue (trace through) at each step, for the following sequence of operations:
Make sureto mention exceptions like empty/full etc. Both front and rear are being
0 to begin with. Further, rear always indexes the “free slot” following the rearmost
element and front indexes the frontmost element. The condition for the circular
queue be- ing full is (SIZE+rear-front)%SIZE = SIZE-1 and queue is empty when
front=rear.
Operations: ENQUEUE Z, ENQUEUE X, DEQUEUE, ENQUEUE F, DEQUEUE,
ENQUEUE B, ENQUEUE N, ENQUEUE H, DEQUEUE, ENQUEUE J, EN-
QUEUE L, DEQUEUE, DEQUEUE, DEQUEUE, DEQUEUE, DEQUEUE.
Answer:
Operation A[0] A[1] A[2] A[3] A[4] Exception Value Value of
Conditions (if of front rear
any) /OUTPUT
0 0
ENQUEUE Z Z 0 1
ENQUEUE X Z X 0 2
DEQUEUE X OUTPUT Z 1 2
ENQUEUE F X F 1 3
DEQUEUE F OUTPUT X 2 3
ENQUEUE B F B 2 4
ENQUEUE N F B N 2 0
ENQUEUE H H F B N 2 1
DEQUEUE H B N OUTPUT F 3 1
ENQUEUE J H J B N 3 2
ENQUEUE L H J B N Queue Full 3 2
DEQUEUE H J N OUTPUT B 4 2
DEQUEUE H J OUTPUT N 0 2
DEQUEUE J OUTPUT H 1 2
DEQUEUE OUTPUT J 2 2
DEQUEUE Queue Empty 2 2
Queue Full: (Size + Rear - Front) % Size = Size -1
Queue Empty: Front = Rear
2. Consider array A[] based implementation of a Linear Queue. Assume that the
array's size is 5 elements maximum. Show the contents of the QUEUE (trace
through) at each step, for the following sequence of operations: Make sure to
mention exceptions like empty/full etc.
Operations: ENQUEUE Z, ENQUEUE X, ENQUEUE F, DEQUEUE, ENQUEUE
B, ENQUEUE N, DEQUEUE, DEQUEUE, DEQUEUE, ENQUEUE G, DEQUEUE,
DEQUEUE,
Answer:
Operation A[0] A[1] A[2] A[3] A[4] Exception Value of Value of
Condition (if front rear
any) /
OUTPUT
0 0
ENQUEUE Z Z 0 1
ENQUEUE X Z X 0 2
ENQUEUE F Z X F 0 3
DEQUEUE X F Output Z 1 3
ENQUEUE B X F B 1 4
ENQUEUE N X F B N 1 5
DEQUEUE F B N Output X 2 5
DEQUEUE B N Output F 3 5
DEQUEUE N Output B 4 5
ENQUEUE G N Queue full 4 5
DEQUEUE Output N 5 5
DEQUEUE Queue empty 5 5
Queue Full: Rear = Size
Queue Empty: Front = Rear
3. Which of the following statements are TRUE? Justify
(a) 2n + 7 is not O(1)
(b) 12n2 + 8n + 7 is O(n)
(c) 5n3 + 6n2 is not O(n2)
(d) 15n3 logn + 16n2 is O(n3)
Answer:
(a) f(n) = 2n + 7 and g(n) = 1
As per definition of g(n), we know that f(n) <= c*g(n) for n >= n0 ,c > 0, n0 ≥ 1,
2n + 7 <= c*1. The above inequality cannot be satisfied since the RHS must be a
constant and the LHS can vary as n varies.
(b) f(n)=12n2 + 8n + 7 and g(n) =n
we know that f(n) <=c*g(n) for n>=n0 ,c > 0, n0 ≥ 1.
12n2 + 8n + 7 <=cn
12n+8+7/n <= c
The above inequality cannot be satisfied since the RHS must be a constant and
the LHS can vary as n varies.
(c) 5n3 + 6n2 is not O(n2).
We prove by contradiction.
Assume 5n3 + 6n2 is O(n2). This implies 5n3 + 6n2 <= c*n2 for n>=n0 ,c > 0, n0 ≥ 1.
5n3 + 6n2 <= c*n2
➔ 5n+6<=c
The above inequality cannot be satisfied since the RHS must be a constant and
the LHS can vary as n varies.
(d) 15n3 logn + 16n2 is O(n3)
Assume the claim to be True.
f(n) = 15n3 logn + 16n2 and g(n) = n3
we know that f(n) <=c*g(n) for n >=n0 ,c > 0, n0 ≥ 1. Thus,
15n3 logn + 16n2 <=c n3
But 15logn+16/n >=15logn >=c for arbitrarily large n. We have a
contradiction and hence the claim is false.
