GATE CSE 2021 Paper 1 — page 17

Questions 49–51 of 65. Imported answers require review unless explicitly marked reviewed.

For a Turing machine

denotes an encoding of

. Consider the following two languages.

Which one of the following options is correct?

Your answerChoose one option.

Both

and

are decidable.

is decidable and

is undecidable.

is undecidable and

is decidable.

Both

and

are undecidable.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Define

to be the maximum amount earned by cutting a rod of length

meters into one or more pieces of integer length and selling them. For

, let

denote the selling price of a rod whose length is

meters. Consider the array of prices:

Which of the following statements is/are correct about

Your answerSelect all correct options. You can choose more than one.

is achieved by three different solutions.

cannot be achieved by a solution consisting of three pieces.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

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. Let

be a DFS tree obtained by doing DFS in a connected undirected graph

. Which of the following options is/are correct?

Your answerSelect all correct options. You can choose more than one.

Root of

can never be an articulation point in

Root of

is an articulation point in

if and only if it has 2 or more children.

A leaf of

can be an articulation point in

is an articulation point in

such that

is an ancestor of

and

is a descendent of

, then all paths from

must pass through

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

2021 · Paper 1

Question 39

Question 40

Question 41