Computational Complexity - Week 0 Quiz Solutions

Question 1

Suppose a language A is recognised by a nondeterministic push-down automaton. Which of the following is/are always correct?

A.It is also recognised by a Deterministic TM

B.It is also recognised by a Deterministic Push down automaton

C.It is also recognised by a Nondeterministic Finite Automaton

D.It is also recognised by a Nondeterministic TM

Correct Answers: It is also recognised by a Deterministic TM, It is also recognised by a Nondeterministic TM

Question 2

Which of the following is/are true?(all logs are in base 2).

A.2\log\ n\ ∈\ O(n)

B.√(\log\ n)\ ∈ O(\log(\log\ n))

C.3n² + 5\ ∈\ o(n²)

D.\log\ n\ ∈\ o(n)

Correct Answers: 2\log\ n\ ∈\ O(n), \log\ n\ ∈\ o(n)

Question 3

Suppose p and q are propositions. Which of the following is/are equivalent to p \Longrightarrow q?

A.q \Longrightarrow p

B.¬ q \Longrightarrow ¬ p

C.( ¬ p ∨ q)

D.¬ p \Longrightarrow ¬ q

Correct Answers: ¬ q \Longrightarrow ¬ p, ( ¬ p ∨ q)

Question 4

Which of the following statements is/are correct?

A.The complement of a Regular Language is always a Regular Language

B.The complement of a Context Free Language is always a Context Free language

C.The union of two CFL’s is always a CFL

D.The intersection of a regular language and CFL is always a CFL

Correct Answers: The complement of a Regular Language is always a Regular Language, The union of two CFL’s is always a CFL, The intersection of a regular language and CFL is always a CFL

Question 5

Suppose a \text{TM} halts on all inputs. Then the language A recognised by the \text{TM} is:

A.Decidable

B.Undecidable

C.Neither decidable nor undecidable

Correct Answer: Decidable

Question 6

Which of the following statements is/are correct?

A.n⁴ + 3n² + 5 ∈ Ω(n⁵)

B.n³ + 2\ ∈\ ω(n³)

C.n\ log\ n\ ∈\ Ω(log\ n)

D.n² + 2n + 5 ∈ Ω(n²)

Correct Answers: n\ log\ n\ ∈\ Ω(log\ n), n² + 2n + 5 ∈ Ω(n²)

Question 7

A Turing Machine can have an infinite number of states. True or False?

A.True

B.False

Correct Answer: False

Question 8

Which of the following sets are countable?

A.\mathbb{Z} , the set of all integers

B.\mathbb{Q} , the set of all rational numbers

C.\mathbb{R} , the set of all real numbers

D.The set of all finite length strings formed by the alphabet ∑ = {a, b, c}

Correct Answers: \mathbb{Z} , the set of all integers, \mathbb{Q} , the set of all rational numbers, The set of all finite length strings formed by the alphabet ∑ = {a, b, c}

Question 9

Let \mathbb{Z} be the set of all integers and \mathbb{O} be the set of all odd numbers. Then,

A.There is a surjective map from \mathbb{Z} to \mathbb{O}

B.There is an injective map from \mathbb{Z} to \mathbb{O}

C.There is a bijective map from \mathbb{Z} to \mathbb{O}

Correct Answers: There is a surjective map from \mathbb{Z} to \mathbb{O}, There is an injective map from \mathbb{Z} to \mathbb{O}, There is a bijective map from \mathbb{Z} to \mathbb{O}

Q10

Question 10

Given a nondeterministic finite automaton with n states. Then the maximum number of states an equivalent minimised deterministic finite automaton can have is:

A.n

B.n!

C.2ⁿ

D.n²

Correct Answer: 2ⁿ

Q11

Question 11

Which of the following problems are decidable?

A.Deciding whether a \text{DFA} accepts a string w

B.Deciding whether a \text{TM} accepts a string w

C.Deciding whether a \text{TM} accepts a string w in 100 steps

D.Deciding whether the language recognized by a given \text{TM} is a regular language

Correct Answers: Deciding whether a \text{DFA} accepts a string w, Deciding whether a \text{TM} accepts a string w in 100 steps

Q12

Question 12

Let A be a set of cardinality n and B be a set of cardinality m. The number of distinct functions from A to B is:

A.n × m

B.mⁿ

C.nm

D.n + m

Correct Answer: mⁿ

Practice: Week 0 : Assignment