Design & Analysis of Algorithm GATE Question Answers with Explanation.
Q1 – Which one of the following sequences when stored in an array at locations A[1], . . . , A[10] forms a max-heap? (GATE 2023)
1. 23, 17, 10, 6, 13, 14, 1, 5, 7, 12
2. 23, 17, 14, 7, 13, 10, 1, 5, 6, 12
3. 23, 17, 14, 6, 13, 10, 1, 5, 7, 15
4. 23, 14, 17, 1, 10, 13, 16, 12, 7, 5
Ans – (2)
Explanation –
To determine which sequence forms a max-heap, we need to check if each node in the array satisfies the max-heap property.
In a max-heap, for any given node at index i, the values of its children at indices 2i and 2i + 1 (assuming 1-based indexing) should be smaller or equal to the value at index i.
Let’s analyze each sequence:
23, 17, 10, 6, 13, 14, 1, 5, 7, 12
- This sequence does not form a max-heap. For example, at index 2, the value is 17, but its left child at index 4 has a value of 6, which violates the max-heap property.
23, 17, 14, 7, 13, 10, 1, 5, 6, 12
- This sequence forms a max-heap. All nodes satisfy the max-heap property.
23, 17, 14, 6, 13, 10, 1, 5, 7, 15
- This sequence does not form a max-heap. For example, at index 4, the value is 6, but its right child at index 9 has a value of 15, which violates the max-heap property.
23, 14, 17, 1, 10, 13, 16, 12, 7, 5
- This sequence does not form a max-heap. For example, at index 2, the value is 14, but its right child at index 6 has a value of 13, which violates the max-heap property.
Therefore, the only sequence that forms a max-heap is option 2:
23, 17, 14, 7, 13, 10, 1, 5, 6, 12.
Q2 – The Lucas sequence Ln is defined by the recurrence relation:
Ln = Ln−1 + Ln−2, for n ≥ 3,
with L1 = 1 and L2 = 3.
Which one of the options given is TRUE? (GATE 2023)
Ans – (1)
Explanation – This may be accomplished using the brute force method, as putting L=1 and L=2 in the first recurrence relation results in the first option being correct.
Q3 – An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions.
Let k be the number of keys, m be the number of slots in the hash table, and k >m.
Which one of the following is the best hashing strategy to counteract the adversary? (GATE 2023)
1. Division method, i.e., use the hash function h(k) = k mod m.
2. Multiplication method, i.e., use the hash function h(k) = floor(m(kA – floor(kA))), where A is a carefully chosen constant.
3. Universal hashing method.
4. If k is a prime number, use Division method. Otherwise, use Multiplication method.
Ans – (3)
Explanation –
The best hashing strategy to counter your adversaries in this scenario is option (3) the universal hashing method.
Universal hashing is the technique of taking a family of hash functions and choosing a random hash function from that family each time a key-needs to be hashed. This randomization prevents an attacker from guessing the hash function or manipulating the input keys to cause collisions.
A set of hash functions ensures that each key has a high probability of being associated with a unique hash value, minimizing the number of collisions. This strategy provides strong protection against malicious adversaries trying to maximize collisions. Option (1) The division method with hash function h(k) = k mod m is prone to collisions if the key is specially crafted by an attacker. If an attacker knows the hash function being used, they can intentionally choose keys that collide frequently, resulting in poor performance.
Option (2) The multiplication method using hash function h(k) = Floor(m(kA – Floor(kA))) also avoids collisions if an attacker knows the constant A and manipulates the key accordingly. is more likely to occur.
Option (4) suggests the use of prime division and multiplication, otherwise it will not provide a strong defense against your opponent. The opponent’s keystroke ability is not taken into account, and prime numbers do not guarantee collision resistance. Therefore, the universal hash method option (3) is the best choice to counter malicious adversaries and minimize the number of collisions.
Q4 – Let f and g be functions of natural numbers given by f(n) = n and g(n) = n2.
Which of the following statements is/are TRUE? (GATE 2023)
1. f ∈ O(g)
2. f ∈ Ω(g)
3. f ∈ o(g)
4. f ∈ Θ(g)
Ans – (1, 3)
Explanation –
Option 1, f(n) ≤ O(g(n)) This is true.
Option 2, f(n) ≥ O(g(n)) This is false.
Option 3, f(n) < O(g(n)) This is true.
Option 4, f(n) = O(g(n)) This is false.
Q5 – Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the maximum element from A. The operation Insert(A, key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations.
When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE? (GATE 2023)
1. Both Extract-Max(A) and Insert(A, key) run in O(1).
2. Both Extract-Max(A) and Insert(A, key) run in O(log(n)).
3. Extract-Max(A) runs in O(1) whereas Insert(A, key) runs in O(n).
4. Extract-Max(A) runs in O(1) whereas Insert(A, key) runs in O(log(n)).
Ans – (2)
Explanation – Both the Extract-Max(A) and Insert(A,key) runs the Heapify operation and the heapify takes (nlogn) time.
Q6 – Consider functions Function 1 and Function 2 expressed in pseudocode as follows:
Function 1
while n > 1 do
for i = 1 to n do
x = x + 1;
end for
n = floor(n/2);
end while
Function 2
for i = 1 to 100 ∗ n do
x = x + 1;
end for
Let f1(n) and f2(n) denote the number of times the statement “x = x + 1” is executed in Function 1 and Function 2, respectively.
Which of the following statements is/are TRUE? (GATE 2023)
1. f1(n) ∈ Θ(f2(n))
2. f1(n) ∈ o(f2(n))
3. f1(n) ∈ ω(f2(n))
4. f1(n) ∈ O(n)
Ans – (1, 4)
Explanation –
Time Complexity of Function 1
For loop runs in n + n/2 + n/4 + … + 2 + 1
Suppose n is a power of 2. (2, 4, 8, 16, 32, 64, …)
This is a G.P. Series
T(n) = n(1/2)n-1/(1/2) = O(n)
Time Complexity of Function 2
T(n) = O(n)
Option 1 is correct because it says f1(n) = f2(n).
Option 4 is correct because it says f1(n) ≤ f2(n).
Option 2 is incorrect because it says f1(n) < f2(n).
Option 3 is incorrect because it says f1(n) > f2(n).
Q7 – Let G be a simple, finite, undirected graph with vertex set {v1, . . . , vn}. Let Δ(G) denote the maximum degree of G and let N = {1, 2, . . .} denote the set of all possible colors. Color the vertices of G using the following greedy strategy:
for i = 1, . . . , n
color(vi) ← min{j ∈ N : no neighbour of vi is colored j}
Which of the following statements is/are TRUE? (GATE 2023)
1. This procedure results in a proper vertex coloring of G.
2. The number of colors used is at most Δ(G) + 1.
3. The number of colors used is at most Δ(G).
4. The number of colors used is equal to the chromatic number of G.
Ans – (1, 2)
Explanation –
Let’s analyze the given options:
(1) This procedure results in a proper vertex coloring of G:
A proper vertex coloring of a graph ensures that no adjacent vertices have the same color. In the given procedure, for each vertex vi, we choose the minimum color j such that no neighbor of vi is already colored j. Therefore, this procedure guarantees a proper vertex coloring because we always assign a color that is different from the colors of the adjacent vertices. So option (1) is true.
(2) The number of colors used is at most Δ(G) + 1:
In this greedy coloring strategy, we start with the first vertex and assign it the smallest available color. For each subsequent vertex, we choose the smallest color that is not used by any of its neighbors. Since the maximum degree of G is Δ(G), each vertex can have at most Δ(G) neighbors. Therefore, the number of colors used will be at most Δ(G) + 1 because we need one extra color to avoid conflicts with the maximum degree vertex. So option (2) is true.
(3) The number of colors used is at most Δ(G):
As explained above, the number of colors used can be at most Δ(G) + 1. Therefore, option (3) is false.
(4) The number of colors used is equal to the chromatic number of G:
The chromatic number of a graph is the minimum number of colors needed to properly color the vertices of the graph. In the given procedure, we can use at most Δ(G) + 1 colors. However, it is not guaranteed that this is the minimum number of colors required for a proper coloring. Therefore, option (D) is false.
Q8 – Let U = {1, 2, 3}. Let 2U denote the powerset of U. Consider an undirected graph G whose vertex set is 2U. For any A, B ∈ 2U, (A,B) is an edge in G if and only if (i) A ≠ B, and (ii) either A ⊊ B or B ⊊ A. For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by ẞ(A).
If ∅ denotes the empty set, then the cardinality of ẞ(∅) is __________. (GATE 2023)
Ans – (5040)
Explanation –
Because U = {1,2,3} → |U| = 3 → set of vertices = {∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} and the cardinality is 8.
If one of the vertices is a proper subset of another vertex, there is an edge between A and B.
As we know, ∅ is a proper subset of every other set of vertices except itself.
This means that ∅ is directly related to 7 points, these 7 points can be visited in any order in BFS.
So, number of BFS orders = 7! = 120x6x7 = 5040.
