GOVERNMENT COLLEGE OF ENGINEERING & CERAMIC TECHNOLOGY

AN AUTONOMOUS INSTITUTE
AFFILIATED TO MAKAUT (FORMERLY KNOWN AS WBUT)
Theory / [Link]/CSE(AI & ML)/ SEM -I/ /Paper Code- PGCSPC102

QUESTION BANK

Course Outcomes (COs)

After completion of this course, the students will be able to

CO1:Compute complexities of data structures and algorithms for a given problem.
CO2:Implement various balanced tree data structures.
CO3: Implement various Priority Queue data structures.
CO4:Apply disjoint set data structure
CO5: Design algorithms using Hashing, Tries and Suffix trees.

Acronyms:

CD: Cognitive Domain

R: Remember​
U: Understand
Ap: Apply
An: Analyze
E: Evaluate
C: Create

KD: Knowledge Domain

F: Factual​
Con: Conceptual
P: Procedural
M: Metacognitive

QT: Question Type

 O: Objective
S: Short Answer Type
E: Essay Type
N: Numerical type

Resources:
​ R1: Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 3rd Edition.

Hints:
​ H1:
​ H2:

CO1: Compute complexities of data structures and algorithms for a given problem
ILO 1.1 Define big omega, small omega, big theta, Big ‘Oh’, small ‘oh’.
ILO 1.2 Compare the properties of various complexity definitions.
ILO 1.3 Solve numericals related to complexity definitions.
ILO 1.4 Explain the operations of array and linked list data structure.
ILO 1.5 Solve problems related to arrays and linked list.
ILO 1.6 Implement Abstract data structure like stacks and queues.
ILO 1.7 Solve problems related to stacks and queues.
CO2:Implement various balanced tree data structures.
ILO 2.1 Define tree, binary trees, variants of binary trees
ILO 2.2 Represent tree using various data structures
ILO 2.3 Define binary search trees.
ILO 2.4 Implement binary search tree.
ILO 2.5 traverse binary search trees
ILO 2.6 Explain properties of balanced binary trees
ILO 2.7 Define AVL trees
ILO 2.8 Explain operations on AVL trees
ILO 2.9 Define Red-Black trees
ILO 2.10 Explain operations on Red-Black trees
ILO 2.11 Define B trees and B+ trees
ILO 2.12 Explain operations on B trees and B+ trees

CO3: Implement various Priority Queue data structures

ILO 3.1 implement priority queue using array
ILO 3.2 implement priority queue using binary heaps
ILO 3.3 implement priority queue using fibonacci heap
ILO 3.4 Analyze the performance of various priority queue implementation

CO4:Apply disjoint set data structure

ILO 4.1 define the operations related to disjoint set data structure
ILO 4.2 implement disjoint set data structure using linked list
ILO 4.3 implement disjoint set data structure using linked list and union by rank
ILO 4.4 implement disjoint set data structure using forests
ILO 4.5 Compare the performance of various implementation of disjoint set data structures
ILO 4.6 Apply disjoint set data structure in problems

CO5: Design algorithms using Hashing, Tries and Suffix trees.

ILO 4.1 Implement direct addressing
ILO 4.2 Define Hash functions
ILO 4.3 Implement hashing using chaining
ILO 4.4 Implement hashing using probing
ILO 4.5 Explain working of Tries
ILO 4.6 Explain working of Suffix trees

Sl Question Marks QT CO ILO KD CD HO Resou

Ts/ rces &
LO Hints
Ts

1 Define ‘Big Oh’ notation. 2 O 1 1.1. F R LO

T

2 Define ‘small Oh’ notation. 2 O 1 1.1. F R LO

T

3 Define ‘small omega’ notation. 2 O 1 1.1. F R LO

T

4 Define ‘Big omega’ notation. 2 O 1 1.1. F R LO

T

5 Define ‘Big Theta’ notation. 2 O 1 1.1. F R LO

T

6 Show that ‘Big Theta’ is an equivalence relation. 5 S 1 1.2 An Con HO

T

7. Show that if f(n)=O(g(n) then g(n)=Ω(f(n)). 5 N 1 1.2 An Con HO

T
8 Prove or disprove: 2n+2 is O(n^2) 2 O 1 1.3 An P HO
T

9 Prove or disprove: n! is O(n^n) 2 O 1 1.3 An P HO

T

10 Prove or disprove: 3n is O(2n). 2 O 1 1.3 An P HO

T

11 Prove or disprove: If 3n is Ө(2n) then 3^n is Ө(2^n). 5 N 1 1.3 An Con HO

T

12 Prove or disprove: If f(n) is Ө(g(n)) then 2^f(n) is Ө(2^g(n)). 5 N 1 1.3 An Con HO

T

13 Prove or disprove: f(n) is not o(g(n) and f(n) is not ω(g(n) implies f(n) 5 N 1 1.3 An Con HO
is Ө(g(n)). T

14 Find the hierarchy of the following functions in terms of complexity: 5 N 1 1.3 An Con HO
(log n)^2, 2^(n^2), log log n, 2^n, n!, n^(⅘), 𝑛. T

15 Prove or disprove: 2^n is O(n!). 5 N 1 1.3 An Con HO

T

16 Write an algorithm for insertion at the beginning of an array. Discuss 3+2 S 1 1.4 U Con LO
the time complexity of your algorithm. T

17 Write an algorithm for insertion at the end of an array. Discuss the 2+2 S 1 1.4 U Con LO
time complexity of your algorithm. T

18 Write an algorithm for deletion at the beginning of an array. Discuss 3+2 S 1 1.4 U Con LO
the time complexity of your algorithm. T

19 Write an algorithm for deletion at the end of an array. Discuss the 2+2 S 1 1.4 U Con LO
time complexity of your algorithm. T

20 Write an algorithm for insertion at the beginning of a linked list. 3+2 S 1 1.4 U Con LO
 Discuss the time complexity of your algorithm. T

21 Write an algorithm for insertion at the end of a linked list when only 3+2 S 1 1.4 An Con HO
head pointer and value to be inserted is provided. Discuss the time T
complexity of your algorithm.

22 Write an algorithm for insertion at the end of a linked list when head 3+2 S 1 1.4 An Con HO
pointer, rear pointer and value to be inserted is provided. Discuss the T
time complexity of your algorithm.

23 Write an algorithm for deletion at the beginning of a linked list. 3+2 S 1 1.4 U Con LO
Discuss the time complexity of your algorithm. T

24 Write an algorithm for deletion at the end of a linked list. Discuss the 3+2 S 1 1.4 U Con LO
time complexity of your algorithm. T

25 What is the time complexity of linear search? 2 O 1 1.5 R F Lot

26 What is the time complexity of binary search? 2 O 1 1.5 R F Lot

27 What is the recurrence relation of binary search? 2 O 1 1.5 R F Lot

28 Solve the recurrence relation T(n)=T(n/2)+c using recursion tree 5 S 1 1.5 U Con Lot
method. State the complexity in “Big oh” notation.

29 Solve the recurrence relation T(n)=2T(n/2)+c using the recursion tree 5 S 1 1.5 U Con Lot
method. State the complexity in “Big oh” notation.

30 Solve the recurrence relation T(n)=T(n/2)+cn using the recursion tree 5 S 1 1.5 U Con Lot
method. State the complexity in “Big oh” notation.

31 Show that the time complexity of implementing binary search with a 5 S 1 1.5 An Con Hot
linked list is O(n).

32 Write an algorithm to find the first index of the element to be searched 5 S 1 1.5 An Con Hot
using Binary search in O(lg n) time.
33 Write an algorithm to find the last index of the element to be searched 5 S 1 1.5 An Con Hot
using Binary search in O(lg n) time.

34 Given a sorted array, find the frequency of an element in the array in 7 E 1 1.5 An Con Hot
O(lg n) time.

35 Given a sorted array A and a value k, find two indices i,j in the array 7 E 1 1.5 An Con Hot
such that A[i]+A[j]=k. If such values are not present return i=-1, j=-1.
Write an algorithm in O(n) time complexity.

36 Given a head of linked list, write an algorithm to check whether its a 7 E 1 1.5 An Con Hot
linear, circular or linear-circular list.

37 Given a head of linked list, write an algorithm to check whether its a 7+5 E 1 1.5 An Con Hot
linear, circular or linear-circular list. Also find the first node from where
the circle initiates if its linear-circular list.

38 Given a linked list and address of a node of the linked list, insert a 5 S 1 1.5 An Con Hot
value just before the node in the list in O(1) time..

39 Given a linked list and address of a node of the linked list, delete the 5 S 1 1.5 An Con Hot
value in the node from the list in O(1) time.

40 Given a head of the linked list, how can we find middle element of 5 S 1 1.5 An Con Hot
linked list in one pass.

41 Why is an array called a static data structure? 2 O 1 1.4 U Con Lot

42 What is meant by contiguous memory allocation? 2 O 1 1.4 U Con Lot

43 Why is a linked list called a dynamic data structure? 2 O 1 1.4 U Con Lot

44 What is meant by continuous memory allocation? 2 O 1 1.4 U Con Lot

45 Why is array not a good choice to implement queues? 2 O 1 1.6 An Con Lot

46 Why is array a good choice to implement stack? 2 O 1 1.6 An Con Lot

47 Write an algorithm to implement circular queues using arrays? 5 S 1 1.6 U Con Lot

48 Write an algorithm to implement stack using arrays? 5 S 1 1.6 U Con Lot

49 Write an algorithm to implement a stack using linked List? 5 S 1 1.6 U Con Lot

50 Write an algorithm to implement queues using linked list? 5 S 1 1.6 U Con Lot

51 What are stack sortable permutations? 2 O 1 1.7 R F Lot

52 What is a catalan number? 2 O 1 1.7 R F Lot

53 How is Catalan number connected to stack sortable permutations 2 O 1 1.7 An Con Hot

54 Give a stack sortable permutation of 1,2,3,4,5 2 O 1 1.7 An Con Hot

55 Give a non stack sortable permutation of 1,2,3,4,5 2 O 1 1.7 An Con Hot

56 How to do valid parentheses checking using stacks 5 S 1 1.7 An Con Hot

57 What is a dyck language? 2 O 1 1.7 An Con Hot

58 How is dyck language connected to valid parenthesis checking? 2 O 1 1.7 An Con Hot

59 How to implement stacks using queues? 5 S 1 1.7 An Con Hot

60 How to implement queues using stacks? 5 S 1 1.7 An Con Hot

61 What is the mathematical definition of a tree? 2 O 2 2.1 R F Lot

62 What is the definition of a rooted tree? 2 O 2 2.1 R F Lot

63 What is the definition of an ordered tree? 2 O 2 2.1 R F Lot

64 Give a recursive definition of binary tree. 2 O 2 2.1 R F Lot

65 What is the relation between nodes with two children and zero child in 5 S 2 2.1 U Con Lot
binary trees? Prove your relation mathematically.
66 How to represent binary trees using pointers? 5 S 2 2.2 U Con Lot

67 How to represent binary trees using arrays? 5 S 2 2.2 U Con Lot

68 For what kind of binary trees do we use array representation of trees 2+3 S 2 2.2 An Con Hot
and why?

69 Given a binary tree with n nodes what is the space required in the 2 O 2 2.2 An Con Hot
worst case, for what kind of binary trees does this scenario occur?

70 Given a binary tree with n nodes what is the space required in the 2 O 2 2.2 An Con Hot
best case, for what kind of binary trees does this scenario occur?

71 What are the properties of binary search trees, explain with an 5 S 2 2.3 U Con Lot
Example?.

72 Define height of a node. 2 O 2 2.3 R F Lot

73 Define depth of a node. 2 O 2 2.3 R F Lot

74 Define the height of a tree. 2 O 2 2.3 R F Lot

75 Define the depth of a tree. 2 O 2 2.3 R F Lot

76 Construct a binary search tree w.r.t the following sequence of 5 S 2 2.4 Ap P Lot
numbers 12,32,45,97,65,93,79.

77 Construct a binary search tree w.r.t the following sequence of 5+3 E 2 2.4 Ap P Lot
numbers 12,32,45,97,65,93,79. Traverse the tree in Post order.

78 Construct a binary search tree w.r.t the following sequence of 5+3 E 2 2.4 Ap P Lot
numbers 12,32,45,97,65,93,79. Traverse the tree in Pre order.

79 Construct a binary search tree w.r.t the following sequence of 5+2 E 2 2.4 Ap P Lot
numbers 12,32,45,97,65,93,79. Traverse the tree in In order.

80 If we are given a preorder traversal of a binary search tree can we 2 O 2 2.5 An Con Hot
 construct the tree uniquely? Explain your answer.

81 If we are given a preorder traversal and post order traversal of a 5 S 2 2.1 An Con Hot
binary tree can we construct the tree uniquely? Explain your answer
with an Example.

82 What is the time complexity of insertion in a binary search tree? 2 O 2 2.4 R F Lot

83 What is the time complexity of deletion in a binary search tree? 2 O 2 2.4 R F Lot

84 What is the time complexity of searching in a binary search tree? 2 O 2 2.4 R F Lot

85 Write an algorithm for binary search tree insertion. 5 S 2 2.4 U P Lot

86 Discuss the different cases of binary search tree deletion. 6 S 2 2.4 U P Lot

81 If an inorder traversal of a binary search tree containing integers is 2 O 2 2.5 An Con Hot
performed. What is the expected output?

82 What is the balance factor w.r.t to binary search trees? 2 O 2 2.6 U F Lot

83 What is a skew tree, explain with an example? 2 O 2 2.6 U Con Lot

84 What is a zigzag tree, explain with an example? 2 O 2 2.6 U Con Lot

85 What is the height of a skew binary tree with ‘n’ number of nodes? 2 O 2 2.6 U Con Lot

86 What is the height of a zigzag binary tree with ‘n’ number of nodes? 2 O 2 2.6 U Con Lot

87 What is the height of a full binary tree with ‘n’ number of nodes? 2 O 2 2.6 U Con Lot

88 What is the height of a complete binary tree with ‘n’ number of 2 O 2 2.6 U Con Lot
nodes?

89 State the properties of AVL trees. 5 S 2 2.7 R F Lot

90 What balance factors are allowed in AVL trees 2 O 2 2.7 R F Lot

91 What node is considered as the pivot node in AVL tree insertion 2 O 2 2.8 U Con Lot
process?

92 Discuss the AVL tree rotations wrt to insertions with suitable diagrams 8 E 2 2.8 U Con Lot

93 For AVL tree insertions, how many unbalanced node do we need to 2 O 2 2.8 U Con Lot
check?

94 For AVL tree deletions, how many unbalanced node do we need to 2 O 2 2.8 U Con Lot
check?

95 If a value is inserted in AVL tree, the balance factors of which node 2 O 2 2.8 An Con Hot
are affected?

96 What is the time complexity of AVL tree insertion? 2 O 2 2.8 R F Lot

97 What is the time complexity of AVL tree deletion? 2 O 2 2.8 R F Lot

98 What is the time complexity of AVL tree searching? 2 O 2 2.8 R F Lot

99 What is the time complexity of AVL tree rotations? 2 O 2 2.8 R F Lot

100 What is the value of the constant factor associated with AVL tree 2 O 2 2.8 R F Lot
operations such as insertions, deletions, searching?

101 Construct an AVL tree with the following sequence of numbers: 5 S 2 2.8 U P Lot
1,5,7,8,9,4,2,0,17,16,15,14

102 State the properties of Red-Black trees. 5 S 2 2.9 R F Lot

103 What is the time complexity of Red-black tree insertion? 2 O 2 2.10 R F Lot

104 What is the time complexity of Red-black tree deletion? 2 O 2 2.10 R F Lot

105 What is the time complexity of Red-black tree searching? 2 O 2 2.10 R F Lot

106 What is the similarities and differences between Red-Black tree and 2+3 S 2 2.9 An Con Hot
 AVL tree

107 Construct a Red-Black tree with the following sequence of numbers: 5 S 2 2.10 U P Lot
1,5,7,8,9,4,2,0,17,16,15,14

108 State the properties of B-trees. 5 S 2 2.11 R F Lot

109 State the properties of B+-trees. 5 S 2 2.11 R F Lot

110 Compare the properties of B Tree and B+ tree 5 S 2 2.11 An Con Hot

111 Construct a B tree with the following sequence of numbers: 5 S 2 2.10 U P Lot
1,5,7,8,9,4,2,0,17,16,15,14

112 Construct a B+ tree with the following sequence of numbers: 5 S 2 2.10 U P Lot
1,5,7,8,9,4,2,0,17,16,15,14

113 What is the time complexity of implementing insertion deletion and 5 S 3 3.1 U Con Lot
minimum finding in priority queue using arrays

114 Write the algorithm for insertion deletion and minimum finding in 3+3+2 S 3 3.1 U Con Lot
priority queue using arrays

115 What is the time complexity of implementing insertion deletion and 5 S 3 3.2 U Con Lot
minimum finding in priority queue using binary heaps?

116 Write the algorithm for insertion deletion and minimum finding in 3+3+2 S 3 3.2 U Con Lot
priority queue using binary heaps.

117 Show how maxheapify when all the ‘n’ elements of the array are 5 S 3 3.2 An Con Lot
present can be implemented in O(n) time.

118 Construct a min binary heap from the given data :1,5,7,93,41,65,97 5 S 3 3.2 An P Hot

119 What is the time complexity of implementing insertion deletion and 5 S 3 3.3 U Con Lot
minimum finding in priority queue using fibonacci heaps
120 Compare the time complexity of implementing insertion deletion and 3+3+3 S 3 3.4 An Con Hot
minimum finding in priority queues for priority queue implemented
using arrays, using binary heaps and using fibonacci heaps.

121 What are the basic operations of disjoint set data structure explain 2+2+2 S 4 4.1 U Con Lot
with Examples?

122 Explain implementation of disjoint set data structures using linked list 5 S 4 4.2 U Con Lot

123 Explain the time complexity of union, find set and make set 2+2+2 S 4 4.2 An Con Hot
operations when disjoint set is implemented using linked list.

124 Explain implementation of disjoint set data structures using linked list 5 S 4 4.3 U Con Lot
and union by rank.

125 Explain the time complexity of union, find set and make set 2+2+2 S 4 4.3 An Con Hot
operations when disjoint set is implemented using linked list and
union by rank

126 Explain implementation of disjoint set data structures using forest 5 S 4 4.4 U Con Lot

127 What is the time complexity of union, find set and make set 1+1+1 S 4 4.4 An Con Hot
operations when a disjoint set is implemented using a forest?.

128 Compare the time complexities of union, find set and make set for 3+3+3 S 4 4.5 An Con Hot
various implementations of the disjoint set data structure such as
union by rank and linked list, forest implementation, only linked list
implementation.

129 What is path compression? 5 S 4 4.4 U Con Lot

130 How can we use disjoint set data structure to find connected 5 S 4 4.6 An Con Hot
components in graph?

131 Explain direct addressing. 5 S 5 4.1 U Con Lot

132 What is the time complexity of insertion, deletion and searching when 1+1+1 O 5 4.1 R F Lot
 employing direct addressing?

133 What is a hash function? 2 O 5 4.2 U Con Lot

134 What is load factor? 2 O 5 4.2 U Con Lot

135 Explain hashing using chaining with an example. 5 S 5 4.3 U Con Lot

136 Give the status of the hash table when hashing using chaining is 5 S 5 4.3 An P Hot
used for the following sequence of values 1,22,31,41,56,79,92, 41.
The hash function used is h(k)=k%5, slots(m)=5.

137 What is a uniform hash function? 2 O 5 4.3 U Con Lot

138 Derive the average time complexity of hashing using chaining for an 5 S 5 4.3 An Con Hot
unsuccessful search.

139 Derive the average time complexity of hashing using chaining for a 5 S 5 4.3 An Con Hot
successful search.

140 Explain hashing using probing with an example. 5 S 5 4.4 U Con Lot

141 Give the status of the hash table when hashing using probing is used 5 S 5 4.4 An P Hot
for the following sequence of values 1,22,31,41,56,79,92, 41. The
hash function used is h(k,i)=(k+i)%10, slots(m)=10.

142 Derive the average time complexity of hashing using probing for an 5 S 5 4.4 An Con Hot
unsuccessful search.

143 Derive the average time complexity of hashing using probing for a 5 S 5 4.4 An Con Hot
successful search.

144 What is linear probing? 2 O 5 4.4 U Con Lot

145 What is quadratic probing? 2 O 5 4.4 U Con Lot

146 What is double hashing? 2 O 5 4.4 U Con Lot

147 What is primary clustering? 5 S 5 4.4 U Con Lot

148 Does linear probing lead to primary clustering? Justify your answer. 5 S 5 4.4 An Con Hot

149 State the properties of tries 5 S 5 4.5 R F Lot

150 State the properties of suffix trees 5 S 5 4.6 R F Lot