BITS PILANI, DUBAI CAMPUS
DUBAI INTERNATIONAL ACADEMIC CITY, DUBAI
SECOND SEMESTER 2024-25
COURSE : DATA STRUCTURES & ALGORITHMS (CS F211)
COMPONENT : TUTORIAL 2 (Solution)
______________________________________________________________________
1. Given two arrays A and B with n distinct elements within itself, but some elements can be
common in both arrays. write a pseudocode to count the number of elements that are
common in both A and B. Further, identify the worst case scenario, count the number of
primitive operations in the worst case and express the corresponding running times T(n)
of the algorithm using big-O notation.
E.g. A={1,3,5,7,9}, B={2,4,6,7, 9}, Common elements count: 2 (7 & 9)
Solution: Primitive operations
Input A[1...n], B[1...n]
Output c
c← 0 1 assignment
For i← 1 to n do 1 assignment, n+1 comparisons
For j← 1 to n do n assignments, n*(n+1) comparisons
if A[i] = B[j] then 3n2 (index,index,comparison)
c← c+1, 2n (increment+assignment)
Exit inner loop n (break loop)
j←j+1 2n2 (increment+assignment)
i←i+1 2n (increment+assignment)
return c 1
Worst case : When there are no common elements.
1+1+(n+1)+n+n(n+1)+3n2+ 2n2+2n+1 = 6n2+6n+4 ------------------------------ O(n2)
2. Consider array based implementation of STACK A. Assume that the array's size is 5
elements maximum. Show the contents of the STACK (trace through) at each step, for the
following sequence of operations: Make sure to mention exceptions like empty/full etc.
Operations: PUSH Z, PUSH X, PUSH F, PUSH D, PUSH B, PUSH N, POP,POP, POP,
POP, POP, POP
Operation A[0] A[1] A[2] A[3] A[4] Exception Value of Element at
Condition (if top(t) top
any)
PUSH Z Z 0 Z
PUSH X Z X 1 X
PUSH F Z X F 2 F
PUSH D Z X F D 3 D
PUSH B Z X F D B 4 B
PUSH N Z X F D B Stack full 4 B
POP Z X F D 3 D
POP Z X F 2 F
POP Z X 1 X
POP Z 0 Z
POP -1 -
POP Stack empty -1 -
3. Write an Algorithm (pseudocode) for the following Problem:
Reverse the contents of an array A of n integers.
Suggested Answer: Let’s use stack as an abstract data type to perform [Link] push
all those elements in the array to the stack and pop allthose elements afterwards and
print so as to get those printed in thereverse order.
For i← 1 to n do
if isStackFull() then
return Error
else
push (A[i])
i← 1
while isStackEmpty() != TRUE do
A[i]← pop()
i←i+1
A solution without stack
For i← 1 to n/2 do
t ← A[i]
A[i] ← A[n+1 - i]
A[n+1-i] ← t
Test your algorithm with each of the following test cases:
i) {1,2,4,9} ii) {1,3,4,7,9}
4. Write an Algorithm (pseudocode) for the following Problem:
- Read an array X of n integers.
- Assume that the elements X[1] ….. X[n] have values in the range 1..1000.
- Return True if each element in the array X is unique else Return False.
Suggested Answer: We exploit the fact that values are in the range 1 to 1000.
for i ← 1 to 1000 do
flag[i]← 0
for j← 1 to n do
x ← A[j]
if flag[x] !=0 then
return False
else
flag[x]← 1
return True
Test your algorithm with each of the following test cases:
i) {100,200,400,900} ii) {100,200,400,200,900}