Crack
GATE
C
G
Topic
Divide and Conquer
Algorithms
0
/ 7 done
Questions per paper
All
MCQ
MSQ
NAT
2015 to 2026. Point at a year to read it.
0
1
2
2015
2019
2021
2023
2025
2026
Show as a table
Year
All
MCQ
MSQ
NAT
2015
0.7
0.7
0
0
2018
0
0
0
0
2019
2
1
0
1
2020
0
0
0
0
2021
0.5
0
0.5
0
2022
0
0
0
0
2023
0
0
0
0
2024
0
0
0
0
2025
0
0
0
0
2026
1
0.5
0.5
0
1
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
.
2
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:
3
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:
4
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.)
5
CS 2019 · 2 marks · MCQ · Moderate
Let
G
G
G
be any connected, weighted, undirected graph.
6
CS 2015 Set 1 · 1 mark · MCQ · Easy
Match the following:
7
CS 2015 Set 2 · 2 marks · MCQ · Easy
Given below are some algorithms, and some algorithm design paradigms.