Home › Quizzes › Theory of Computation

Theory of Computation

Fundamental concepts in computability, complexity theory, information theory, and algorithm analysis

14 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

What is the name of the mathematical theory that studies the relationship between computation and information?

  1. Computability Theory
  2. Information Theory
  3. Complexity Theory
  4. Algorithmic Theory
Question 2 Multiple Choice (Single Answer)

Which of the following is a fundamental concept in computability theory?

  1. Turing Machine
  2. Lambda Calculus
  3. Regular Expression
  4. Finite State Machine
Question 3 Multiple Choice (Single Answer)

What is the Halting Problem?

  1. The problem of determining whether a given program will ever halt.
  2. The problem of determining the output of a given program.
  3. The problem of determining the time complexity of a given program.
  4. The problem of determining the space complexity of a given program.
Question 4 Multiple Choice (Single Answer)

What is the Church-Turing Thesis?

  1. The thesis that any computation that can be carried out by a Turing machine can also be carried out by a human computer.
  2. The thesis that any computation that can be carried out by a human computer can also be carried out by a Turing machine.
  3. The thesis that any computation that can be carried out by a computer can also be carried out by a human.
  4. The thesis that any computation that can be carried out by a human can also be carried out by a computer.
Question 5 Multiple Choice (Single Answer)

What is the name of the mathematical theory that studies the complexity of computation?

  1. Complexity Theory
  2. Computability Theory
  3. Information Theory
  4. Algorithmic Theory
Question 6 Multiple Choice (Single Answer)

What is the P versus NP problem?

  1. The problem of determining whether P = NP.
  2. The problem of determining whether P != NP.
  3. The problem of determining whether P is a subset of NP.
  4. The problem of determining whether NP is a subset of P.
Question 7 Multiple Choice (Single Answer)

What is the name of the mathematical theory that studies the relationship between information and communication?

  1. Information Theory
  2. Computability Theory
  3. Complexity Theory
  4. Algorithmic Theory
Question 8 Multiple Choice (Single Answer)

What is the Shannon-Hartley theorem?

  1. The theorem that states the maximum rate at which information can be transmitted over a noisy channel.
  2. The theorem that states the maximum rate at which information can be transmitted over a noiseless channel.
  3. The theorem that states the minimum rate at which information can be transmitted over a noisy channel.
  4. The theorem that states the minimum rate at which information can be transmitted over a noiseless channel.
Question 9 Multiple Choice (Single Answer)

What is the name of the mathematical theory that studies the design and analysis of algorithms?

  1. Algorithmic Theory
  2. Computability Theory
  3. Complexity Theory
  4. Information Theory
Question 10 Multiple Choice (Single Answer)

What is the time complexity of a linear search algorithm?

  1. O(n)
  2. O(log n)
  3. O(n^2)
  4. O(n^3)
Question 11 Multiple Choice (Single Answer)

What is the time complexity of a binary search algorithm?

  1. O(n)
  2. O(log n)
  3. O(n^2)
  4. O(n^3)
Question 12 Multiple Choice (Single Answer)

What is the space complexity of a binary search algorithm?

  1. O(n)
  2. O(log n)
  3. O(n^2)
  4. O(n^3)
Question 13 Multiple Choice (Single Answer)

What is the name of the mathematical theory that studies the relationship between computation and physics?

  1. Quantum Computing Theory
  2. Computability Theory
  3. Complexity Theory
  4. Information Theory
Question 14 Multiple Choice (Single Answer)

What is the name of the mathematical theory that studies the relationship between computation and biology?

  1. Bioinformatics
  2. Computability Theory
  3. Complexity Theory
  4. Information Theory
← Back to Quizzes