Crack
GATE
C
G
Topic
Algorithms
74 questions
0
/ 74 done
Questions per paper
All
MCQ
MSQ
NAT
2015 to 2026. Point at a year to read it.
0
4
8
2015
2019
2021
2023
2025
2026
Show as a table
Year
All
MCQ
MSQ
NAT
2015
5
3.7
0
1.3
2018
0
0
0
0
2019
4
2
0
2
2020
5
3
0
2
2021
7.5
4
2
1.5
2022
3
2
1
0
2023
3
1
2
0
2024
3
1
0.5
1.5
2025
5
2.5
0.5
2
2026
6.5
3
2.5
1
1
CS 2026 Set 1 · 1 mark · MSQ · Moderate
Consider a hash table
P
[
0
,
1
,
…
,
10
]
P[0, 1, \dots, 10]
P
[
0
,
1
,
…
,
10
]
that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is
h
(
x
)
=
(
x
+
7
)
m
o
d
11
h(x) = (x + 7) \bmod 11
h
(
x
)
=
(
x
+
7
)
mod
11
.
2
CS 2026 Set 1 · 2 marks · MCQ · Moderate
Let
G
(
V
,
E
)
G(V, E)
G
(
V
,
E
)
be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.
3
CS 2026 Set 1 · 2 marks · MSQ · Hard
Let
G
(
V
,
E
)
G(V,E)
G
(
V
,
E
)
be a simple, undirected graph. A vertex cover of
G
G
G
is a subset
V
′
⊆
V
V' \subseteq V
V
′
⊆
V
such that for every
(
u
,
v
)
∈
E
(u,v) \in E
(
u
,
v
)
∈
E
,
u
∈
V
′
u \in V'
u
∈
V
′
or
v
∈
V
′
v \in V'
v
∈
V
′
. Let the size of the smallest vertex cover in
G
G
G
be
k
k
k
. Let
S
S
S
be any vertex cover of size
k
k
k
.
4
CS 2026 Set 1 · 2 marks · MSQ · Hard
Let
G
(
V
,
E
)
G(V, E)
G
(
V
,
E
)
be a simple, undirected, edge-weighted graph with unique edge weights.
5
CS 2026 Set 1 · 2 marks · MSQ · Hard
Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph
G
(
V
,
E
)
G(V, E)
G
(
V
,
E
)
as input, where
d
[
v
]
d[v]
d
[
v
]
and
f
[
v
]
f[v]
f
[
v
]
are the discovery time and finishing time, respectively, of the vertex
v
∈
V
v \in V
v
∈
V
.
6
CS 2026 Set 2 · 1 mark · MCQ · Moderate
Consider the following functions, where
n
n
n
is a positive integer.
7
CS 2026 Set 2 · 1 mark · MSQ · Moderate
Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity
Θ
(
n
)
\Theta(n)
Θ
(
n
)
?
8
CS 2026 Set 2 · 1 mark · NAT · Easy
The keys
5
,
28
,
19
,
15
,
26
,
33
,
12
,
17
,
10
5, 28, 19, 15, 26, 33, 12, 17, 10
5
,
28
,
19
,
15
,
26
,
33
,
12
,
17
,
10
are inserted into a hash table using the hash function
h
(
k
)
=
k
m
o
d
9
h(k) = k \bmod 9
h
(
k
)
=
k
mod
9
. The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is ____. (answer in integer)
9
CS 2026 Set 2 · 1 mark · NAT · Moderate
Consider an array
A
=
[
10
,
7
,
8
,
19
,
41
,
35
,
25
,
31
]
A = [10, 7, 8, 19, 41, 35, 25, 31]
A
=
[
10
,
7
,
8
,
19
,
41
,
35
,
25
,
31
]
. Suppose the merge sort algorithm is executed on array
A
A
A
to sort it in increasing order. The merge sort algorithm will carry out a total of
7
7
7
merge operations.
10
CS 2026 Set 2 · 2 marks · MCQ · Moderate
Consider a complete graph
K
n
K_n
K
n
with
n
n
n
vertices (
n
>
4
n > 4
n
>
4
). Note that multiple spanning trees can be constructed over
K
n
K_n
K
n
. Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets.
11
CS 2026 Set 2 · 2 marks · MCQ · Moderate
Let
G
G
G
be a weighted directed acyclic graph with
m
m
m
edges and
n
n
n
vertices. Given
G
G
G
and a source vertex
s
s
s
in
G
G
G
, which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from
s
s
s
to all vertices that are reachable from
s
s
s
in
G
G
G
?
12
CS 2026 Set 2 · 2 marks · MCQ · Moderate
Consider an array
A
A
A
of integers of size
n
n
n
. The indices of
A
A
A
run from
1
1
1
to
n
n
n
. An algorithm is to be designed to check whether
A
A
A
satisfies the condition given below.
13
CS 2026 Set 2 · 2 marks · MCQ · Moderate
Consider a table
T
T
T
, where the elements
T
[
i
]
[
j
]
,
0
≤
i
,
j
≤
n
T[i][j], 0 \le i, j \le n
T
[
i
]
[
j
]
,
0
≤
i
,
j
≤
n
, represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows:
14
CS 2025 Set 1 · 1 mark · MCQ · Easy
Let
G
G
G
be any undirected graph with positive edge weights, and
T
T
T
be a minimum spanning tree of
G
G
G
. For any two vertices,
u
u
u
and
v
v
v
, let
d
1
(
u
,
v
)
d_1(u, v)
d
1
(
u
,
v
)
and
d
2
(
u
,
v
)
d_2(u, v)
d
2
(
u
,
v
)
be the shortest distances between
u
u
u
and
v
v
v
in
G
G
G
and
T
T
T
, respectively. Which ONE of the options is CORRECT for all possible
G
,
T
,
u
G, T, u
G
,
T
,
u
and
v
v
v
?
15
CS 2025 Set 1 · 1 mark · NAT · Moderate
The pseudocode of a function
f
u
n
(
)
\mathbf{fun}()
fun
(
)
is given below:
16
CS 2025 Set 1 · 2 marks · MCQ · Hard
Let
G
(
V
,
E
)
G(V,E)
G
(
V
,
E
)
be an undirected and unweighted graph with
100
100
100
vertices. Let
d
(
u
,
v
)
d(u,v)
d
(
u
,
v
)
denote the number of edges in a shortest path between vertices
u
u
u
and
v
v
v
in
V
V
V
. Let the maximum value of
d
(
u
,
v
)
d(u,v)
d
(
u
,
v
)
,
u
,
v
∈
V
u,v \in V
u
,
v
∈
V
such that
u
≠
v
u \neq v
u
=
v
, be
30
30
30
. Let
T
T
T
be any breadth-first-search tree of
G
G
G
. Which ONE of the given options is CORRECT for every such graph
G
G
G
?
17
CS 2025 Set 1 · 2 marks · NAT · Moderate
The maximum value of
x
x
x
such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is ____ . (answer in integer)
18
CS 2025 Set 1 · 2 marks · NAT · Moderate
In a double hashing scheme,
h
1
(
k
)
=
k
(
m
o
d
11
)
h_1(k) = k \pmod{11}
h
1
(
k
)
=
k
(
mod
11
)
and
h
2
(
k
)
=
1
+
(
k
(
m
o
d
7
)
)
h_2(k) = 1 + (k \pmod{7})
h
2
(
k
)
=
1
+
(
k
(
mod
7
))
are the auxiliary hash functions. The size
m
m
m
of the hash table is
11
11
11
. The hash function for the
i
i
i
-th probe in the open address table is
[
h
1
(
k
)
+
i
h
2
(
k
)
]
(
m
o
d
m
)
[h_1(k) + i\,h_2(k)] \pmod{m}
[
h
1
(
k
)
+
i
h
2
(
k
)]
(
mod
m
)
. The following keys are inserted in the given order:
63
,
50
,
25
,
79
,
67
,
24
63, 50, 25, 79, 67, 24
63
,
50
,
25
,
79
,
67
,
24
.
19
CS 2025 Set 2 · 1 mark · MCQ · Easy
Consider an unordered list of
N
N
N
distinct integers.
20
CS 2025 Set 2 · 1 mark · MSQ · Moderate
Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph
G
G
G
is/are TRUE?
21
CS 2025 Set 2 · 2 marks · MCQ · Moderate
Let
G
G
G
be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant
α
\alpha
α
is added to the weight of every edge.
22
CS 2025 Set 2 · 2 marks · MCQ · Moderate
An array
A
A
A
of length
n
n
n
with distinct elements is said to be bitonic if there is an index
1
≤
i
≤
n
1 \le i \le n
1
≤
i
≤
n
such that
A
[
1
…
i
]
A[1 \dots i]
A
[
1
…
i
]
is sorted in the non-decreasing order and
A
[
i
+
1
…
n
]
A[i + 1 \dots n]
A
[
i
+
1
…
n
]
is sorted in the non-increasing order.
23
CS 2025 Set 2 · 2 marks · NAT · Moderate
Consider the following algorithm
s
o
m
e
A
l
g
o
\mathtt{someAlgo}
someAlgo
that takes an undirected graph
G
G
G
as input.
24
CS 2024 Set 1 · 1 mark · MCQ · Moderate
Given an integer array of size
N
N
N
, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is
25
CS 2024 Set 1 · 2 marks · MCQ · Hard
Consider the following recurrence relation:
26
CS 2024 Set 1 · 2 marks · MSQ · Moderate
Let
G
G
G
be a directed graph and
T
T
T
a depth first search (DFS) spanning tree in
G
G
G
that is rooted at a vertex
v
v
v
. Suppose
T
T
T
is also a breadth first search (BFS) tree in
G
G
G
, rooted at
v
v
v
. Which of the following statements is/are TRUE for every such graph
G
G
G
and tree
T
T
T
?
27
CS 2024 Set 1 · 2 marks · NAT · Easy
The number of edges present in the forest generated by the DFS traversal of an undirected graph
G
G
G
with 100 vertices is 40. The number of connected components in
G
G
G
is ____
28
CS 2024 Set 2 · 1 mark · NAT · Moderate
Let
A
A
A
be an array containing integer values. The distance of
A
A
A
is defined as the minimum number of elements in
A
A
A
that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array
[
2
,
5
,
3
,
1
,
4
,
2
,
6
]
[2,5,3,1,4,2,6]
[
2
,
5
,
3
,
1
,
4
,
2
,
6
]
is ____.
29
CS 2024 Set 2 · 2 marks · NAT · Moderate
The number of distinct minimum-weight spanning trees of the following graph is ____\n
30
CS 2023 · 1 mark · MCQ · Moderate
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
k
k
be the number of keys,
m
m
m
be the number of slots in the hash table, and
k
>
m
k>m
k
>
m
.
31
CS 2023 · 1 mark · MSQ · Easy
Let
f
f
f
and
g
g
g
be functions of natural numbers given by
f
(
n
)
=
n
f(n)=n
f
(
n
)
=
n
and
g
(
n
)
=
n
2
g(n)=n^2
g
(
n
)
=
n
2
. Which of the following statements is/are TRUE?
32
CS 2023 · 2 marks · MSQ · Easy
Consider functions Function-1 and Function-2 expressed in pseudocode as follows:
33
CS 2022 · 1 mark · MCQ · Moderate
Which one of the following statements is TRUE for all positive functions
f
(
n
)
f(n)
f
(
n
)
?
34
CS 2022 · 1 mark · MCQ · Moderate
Suppose we are given
n
n
n
keys,
m
m
m
hash table slots, and two simple uniform hash functions
h
1
h_1
h
1
and
h
2
h_2
h
2
. Further suppose our hashing scheme uses
h
1
h_1
h
1
for the odd keys and
h
2
h_2
h
2
for the even keys. What is the expected number of keys in a slot?
35
CS 2022 · 2 marks · MSQ · Moderate
Consider a simple undirected weighted graph
G
G
G
, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of
G
G
G
is/are TRUE?
36
CS 2021 Set 1 · 1 mark · MCQ · Moderate
Let P be an array containing
n
n
n
integers. Let
t
t
t
be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of
n
n
n
elements. Which one of the following choices is correct?
37
CS 2021 Set 1 · 1 mark · MCQ · Moderate
Consider the following three functions.
38
CS 2021 Set 1 · 1 mark · MCQ · Moderate
Consider the following array.
39
CS 2021 Set 1 · 1 mark · NAT · Moderate
Consider the following undirected graph with edge weights as shown:
40
CS 2021 Set 1 · 2 marks · MCQ · Moderate
Consider the following recurrence relation.
41
CS 2021 Set 1 · 2 marks · MSQ · Hard
Define
R
n
R_n
R
n
to be the maximum amount earned by cutting a rod of length
n
n
n
meters into one or more pieces of integer length and selling them. For
i
>
0
\mathrm{i} > 0
i
>
0
, let
p
[
i
]
\mathrm{p}[\mathrm{i}]
p
[
i
]
denote the selling price of a rod whose length is
i
\mathrm{i}
i
meters. Consider the array of prices:
42
CS 2021 Set 1 · 2 marks · MSQ · Moderate
An
articulation point
in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.
43
CS 2021 Set 1 · 2 marks · MSQ · Hard
Consider a
dynamic
hashing approach for 4-bit integer keys:
44
CS 2021 Set 2 · 1 mark · MCQ · Moderate
Let
G
G
G
be a connected undirected weighted graph. Consider the following two statements.
45
CS 2021 Set 2 · 1 mark · MCQ · Easy
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size
n
n
n
?
46
CS 2021 Set 2 · 1 mark · NAT · Moderate
Consider a complete binary tree with 7 nodes. Let
A
A
A
denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let
B
B
B
denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.
47
CS 2021 Set 2 · 2 marks · MCQ · Moderate
Consider the string
abbccddeee
. Each letter in the string must be assigned a binary code satisfying the following properties:
48
CS 2021 Set 2 · 2 marks · MCQ · Easy
For constants
a
≥
1
a \ge 1
a
≥
1
and
b
>
1
b > 1
b
>
1
, consider the following recurrence defined on the non-negative integers:
49
CS 2021 Set 2 · 2 marks · MSQ · Hard
Consider the following directed graph:
50
CS 2021 Set 2 · 2 marks · NAT · Moderate
In a directed acyclic graph with a source vertex
s
\mathtt{s}
s
, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex
v
v
v
other than
s
\mathtt{s}
s
, the quality-score of
v
v
v
is defined to be the maximum among the quality-scores of all the paths from
s
\mathtt{s}
s
to
v
v
v
. The quality-score of
s
\mathtt{s}
s
is assumed to be
1
1
1
.
51
CS 2020 · 1 mark · MCQ · Hard
For parameters
a
a
a
and
b
b
b
, both of which are
ω
(
1
)
\omega(1)
ω
(
1
)
,
T
(
n
)
=
T
(
n
1
/
a
)
+
1
T(n) = T(n^{1/a}) + 1
T
(
n
)
=
T
(
n
1/
a
)
+
1
, and
T
(
b
)
=
1
T(b) = 1
T
(
b
)
=
1
. Then
T
(
n
)
T(n)
T
(
n
)
is
52
CS 2020 · 1 mark · NAT · Easy
Consider a double hashing scheme in which the primary hash function is
h
1
(
k
)
=
k
m
o
d
23
h_1(k) = k \bmod 23
h
1
(
k
)
=
k
mod
23
, and the secondary hash function is
h
2
(
k
)
=
1
+
(
k
m
o
d
19
)
h_2(k) = 1 + (k \bmod 19)
h
2
(
k
)
=
1
+
(
k
mod
19
)
. Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value
k
=
90
k = 90
k
=
90
is ____.
53
CS 2020 · 2 marks · MCQ · Moderate
Let
G
=
(
V
,
E
)
G = (V, E)
G
=
(
V
,
E
)
be a weighted undirected graph and let
T
T
T
be a Minimum Spanning Tree (MST) of
G
G
G
maintained using adjacency lists. Suppose a new weighted edge
(
u
,
v
)
∈
V
×
V
(u, v) \in V \times V
(
u
,
v
)
∈
V
×
V
is added to
G
G
G
. The worst case time complexity of determining if
T
T
T
is still an MST of the resultant graph is
54
CS 2020 · 2 marks · MCQ · Hard
Let
G
=
(
V
,
E
)
G = (V, E)
G
=
(
V
,
E
)
be a directed, weighted graph with weight function
w
:
E
→
R
w : E \to \mathbb{R}
w
:
E
→
R
. For some function
f
:
V
→
R
f : V \to \mathbb{R}
f
:
V
→
R
, for each edge
(
u
,
v
)
∈
E
(u, v) \in E
(
u
,
v
)
∈
E
, define
w
′
(
u
,
v
)
w'(u, v)
w
′
(
u
,
v
)
as
w
(
u
,
v
)
+
f
(
u
)
−
f
(
v
)
w(u, v) + f(u) - f(v)
w
(
u
,
v
)
+
f
(
u
)
−
f
(
v
)
.
55
CS 2020 · 2 marks · NAT · Moderate
Consider a graph
G
=
(
V
,
E
)
G = (V, E)
G
=
(
V
,
E
)
, where
V
=
{
v
1
,
v
2
,
…
,
v
100
}
V = \{v_1, v_2, \dots, v_{100}\}
V
=
{
v
1
,
v
2
,
…
,
v
100
}
,
E
=
{
(
v
i
,
v
j
)
∣
1
≤
i
<
j
≤
100
}
E = \{(v_i, v_j) \mid 1 \le i < j \le 100\}
E
=
{(
v
i
,
v
j
)
∣
1
≤
i
<
j
≤
100
}
, and weight of the edge
(
v
i
,
v
j
)
(v_i, v_j)
(
v
i
,
v
j
)
is
∣
i
−
j
∣
|i - j|
∣
i
−
j
∣
. The weight of minimum spanning tree of
G
G
G
is ____.
56
CS 2019 · 1 mark · NAT · Easy
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ____.
57
CS 2019 · 1 mark · NAT · Moderate
Consider a sequence of 14 elements:
A
=
[
−
5
,
−
10
,
6
,
3
,
−
1
,
−
2
,
13
,
4
,
−
9
,
−
1
,
4
,
12
,
−
3
,
0
]
A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]
A
=
[
−
5
,
−
10
,
6
,
3
,
−
1
,
−
2
,
13
,
4
,
−
9
,
−
1
,
4
,
12
,
−
3
,
0
]
. The subsequence sum
S
(
i
,
j
)
=
∑
k
=
i
j
A
[
k
]
S(i, j) = \sum_{k=i}^j A[k]
S
(
i
,
j
)
=
∑
k
=
i
j
A
[
k
]
. Determine the maximum of
S
(
i
,
j
)
S(i, j)
S
(
i
,
j
)
, where
0
≤
i
≤
j
<
14
0 \le i \le j < 14
0
≤
i
≤
j
<
14
. (Divide and conquer approach may be used.)
58
CS 2019 · 2 marks · MCQ · Moderate
There are
n
n
n
unsorted arrays:
A
1
,
A
2
,
…
,
A
n
A_1, A_2, \ldots, A_n
A
1
,
A
2
,
…
,
A
n
. Assume that
n
n
n
is odd. Each of
A
1
,
A
2
,
…
,
A
n
A_1, A_2, \ldots, A_n
A
1
,
A
2
,
…
,
A
n
contains
n
n
n
distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of
A
1
,
A
2
,
…
,
A
n
A_1, A_2, \ldots, A_n
A
1
,
A
2
,
…
,
A
n
is
59
CS 2019 · 2 marks · MCQ · Moderate
Let
G
G
G
be any connected, weighted, undirected graph.
60
CS 2015 Set 1 · 1 mark · MCQ · Easy
Match the following:
61
CS 2015 Set 1 · 1 mark · MCQ · Easy
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting
n
n
n
(
≥
2
\ge 2
≥
2
) numbers? In the recurrence equations given in the options below,
c
c
c
is a constant.
62
CS 2015 Set 1 · 2 marks · MCQ · Moderate
Let
G
=
(
V
,
E
)
G = (V, E)
G
=
(
V
,
E
)
be a simple undirected graph, and
s
s
s
be a particular vertex in it called the source. For
x
∈
V
x \in V
x
∈
V
, let
d
(
x
)
d(x)
d
(
x
)
denote the shortest distance in
G
G
G
from
s
s
s
to
x
x
x
. A breadth first search (BFS) is performed starting at
s
s
s
. Let
T
T
T
be the resultant BFS tree. If
(
u
,
v
)
(u,v)
(
u
,
v
)
is an edge of
G
G
G
that is not in
T
T
T
, then which one of the following CANNOT be the value of
d
(
u
)
−
d
(
v
)
d(u) - d(v)
d
(
u
)
−
d
(
v
)
?
63
CS 2015 Set 1 · 2 marks · NAT · Hard
The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges:
{
(
A
,
C
)
,
(
B
,
C
)
,
(
B
,
E
)
,
(
E
,
F
)
,
(
D
,
F
)
}
\{(A, C), (B, C), (B, E), (E, F), (D, F)\}
{(
A
,
C
)
,
(
B
,
C
)
,
(
B
,
E
)
,
(
E
,
F
)
,
(
D
,
F
)}
. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ________.
64
CS 2015 Set 1 · 2 marks · MCQ · Moderate
Consider the following C function.
65
CS 2015 Set 2 · 1 mark · MCQ · Moderate
An unordered list contains
n
n
n
distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
66
CS 2015 Set 2 · 1 mark · MCQ · Easy
Consider the basic COCOMO model where
E
E
E
is the effort applied in person-months,
D
D
D
is the development time in chronological months,
K
L
O
C
\mathrm{KLOC}
KLOC
is the estimated number of delivered lines of code (in thousands) and
a
b
,
b
b
,
c
b
,
d
b
a_b, b_b, c_b, d_b
a
b
,
b
b
,
c
b
,
d
b
have their usual meanings. The basic COCOMO equations are of the form
67
CS 2015 Set 2 · 2 marks · MCQ · Easy
Given below are some algorithms, and some algorithm design paradigms.
68
CS 2015 Set 2 · 2 marks · MCQ · Moderate
Which one of the following hash functions on integers will distribute keys most uniformly over
10
10
10
buckets numbered
0
0
0
to
9
9
9
for
i
i
i
ranging from
0
0
0
to
2020
2020
2020
?
69
CS 2015 Set 3 · 1 mark · MCQ · Easy
Consider the equality
∑
i
=
0
n
i
3
=
X
\sum_{i=0}^{n} i^3 = X
∑
i
=
0
n
i
3
=
X
and the following choices for
X
X
X
70
CS 2015 Set 3 · 1 mark · NAT · Easy
Given a hash table
T
T
T
with
25
25
25
slots that stores
2000
2000
2000
elements, the load factor
α
\alpha
α
for
T
T
T
is ____.
71
CS 2015 Set 3 · 2 marks · MCQ · Moderate
Assume that a mergesort algorithm in the worst case takes
30
s
e
c
o
n
d
s
30\,\mathrm{seconds}
30
seconds
for an input of size
64
64
64
. Which of the following most closely approximates the maximum input size of a problem that can be solved in
6
m
i
n
u
t
e
s
6\,\mathrm{minutes}
6
minutes
?
72
CS 2015 Set 3 · 2 marks · NAT · Easy
Let
G
G
G
be a connected undirected graph of
100
100
100
vertices and
300
300
300
edges. The weight of a minimum spanning tree of
G
G
G
is
500
500
500
. When the weight of each edge of
G
G
G
is increased by five, the weight of a minimum spanning tree becomes ____.
73
CS 2015 Set 3 · 2 marks · NAT · Moderate
Suppose
c
=
⟨
c
[
0
]
,
.
.
.
,
c
[
k
−
1
]
⟩
c = \langle c[0], ..., c[k - 1] \rangle
c
=
⟨
c
[
0
]
,
...
,
c
[
k
−
1
]⟩
is an array of length
k
k
k
, where all the entries are from the set {0, 1}. For any positive integers
a
a
a
and
n
n
n
, consider the following pseudocode.
74
CS 2015 Set 3 · 2 marks · MCQ · Hard
Let
f
(
n
)
=
n
f(n) = n
f
(
n
)
=
n
and
g
(
n
)
=
n
(
1
+
sin
n
)
g(n) = n^{(1 + \sin n)}
g
(
n
)
=
n
(
1
+
s
i
n
n
)
, where
n
n
n
is a positive integer. Which of the following statements is/are correct?