Deck 12: Theory of Computation

Question 1

Which of the following algorithms represents an optimal solution (in terms of time complexity)for sorting a list?

A) Insertion sort
B) Bubble sort
C) Selection sort
D) Merge sort

Answer 1

D

Question 2

What is the time complexity of the problem of sorting a list?

A) $\Theta$ (log? n)
B) $\Theta$ (n)
C) $\Theta$ (n log? n)
D) $\Theta$ (n²)

Answer 2

$\Theta$ (n log? n)

Question 3

Which of the following is the most precise classification of a problem X?

A) X is in NP.
B) X is in P.
C) X is in O(n²).
D) X is in $\Theta$ (n²).

Answer 3

X is in $\Theta$ (n²).

Question 4

Which of the following systems does not process the same computational capabilities as the others?

A) Turing machines
B) Universal programming languages
C) Algebraic expressions
D) The Bare Bones language

Question 5

The precise time complexity of which of the following problems has not yet been established by researchers?

A) Sorting a list
B) Searching through a list for a particular entry
C) The traveling salesman problem
D) Listing all possible subcommittees within a given committee

Question 6

What is the time complexity of the problem of searching for a particular entry in a list?

A) $\Theta$ (log? n)
B) $\Theta$ (n)
C) $\Theta$ (n log? n)
D) $\Theta$ (n²)

Question 7

Which of the following sets of values constitutes a valid RSA public key encryption system?

A) p = 5, q = 11, n = 55, e = 17, d = 13
B) p = 5, q = 11, n = 83, e = 17, d = 13
C) p = 5, q = 11, n = 83, e = 10, d = 13
D) p = 5, q = 11, n = 55, e = 10, d = 13

Question 8

The class of problems known as NP is so named because it is composed of which of the following?

A) Non-polynomial problems
B) Non-programmable problems
C) Non-universal problems
D) Non-deterministic polynomial problems

Question 9

What action is performed by the Turing machine described below?

$\begin{array}{ccccc}\begin{array}{c}\text { Current } \\\underline{\text { state }}\end{array} & \begin{array}{c}\text { Current } \\\underline{\text { cell content }}\end{array} & \begin{array}{c}\text { Value } \\\underline{\text { to write }}\end{array} & \begin{array}{c}\text { Direction } \\\underline{\text { to move }}\end{array} & \begin{array}{c}\text { New } \\\underline{\text { state }}\end{array} \\\text { START } & * & * & \text { left } & \text { X } \\\text { X } & 1 & 0 & \text { left } & \text { X } \\\text { X } & 0 & 0 & \text { right } & \mathrm{Y} \\\text { Y } & 0 & 0 & \text { right } & \text { Y } \\\text { Y } & * & * & \text { no move } & \text { HALT }\end{array}$

A) It replaces any string of consecutive 1s to the left of an * with 0s.
B) It leaves the tape unchanged.
C) It places an * at the left end of any string of consecutive 1s appearing to the left of an *.
D) It complements the string of 0s and 1s appearing to the left of an *.

Question 10

Which of the following best describes what the following Bare Bones program does?
$\begin{array} { l } \text { copy } \mathrm { X } \text { to } \mathrm { Z } \\\text { clear } \mathrm { X } \\\text { incr } \mathrm { X } \\\text { while } \mathrm { Z } \text { not } 0 \text { : } \\\text { clear } \mathrm { X } \\\text { decr } \mathrm { Z }\end{array}$

A) It changes the value of X to 1.
B) If the starting value of X is 0, it sets the value of X to 0. Otherwise, it sets the value of X to 1.
C) If the starting value of X is 0, it sets the value of X to 1. Otherwise, it sets the value of X to 0.
D) It ultimately leaves X the same as it was when the program starteD.

Question 11

What action is performed by the Turing machine described below?


$$\begin{array} { c c c c c } \begin{array} { c } \text { Current } \\\underline{\text { state }}\end{array} & \begin{array} { c } \text { Current } \\\underline{\text { cell content }}\end{array} & \begin{array} { c } \text { Value } \\\underline{\text { to write }}\end{array} & \begin{array} { c } \text { Direction } \\\underline{\text { to move }}\end{array} & \begin{array} { c } \text { New } \\\underline{\text { state }}\end{array} \\\text { START } & * & * & \text { left } & \text { X } \\\text { X } & 1 & 1 & \text { left } & \mathrm { X } \\\text { X} & 0 & * &\text { right }& \mathrm { Y }\end{array}$$

A) It replaces any string of consecutive 1s to the left of an * with 0s.
B) It leaves the tape unchanged.
C) It places an * at the left end of any string of consecutive 1s appearing to the left of an *.
D) It complements the string of 0s and 1s appearing to the left of an *.

Question 12

If a solution with time complexity $\Theta$ (n²)is known to exist,then the problem is known to be in which of the following?

A) $\Theta$ (n²)
B) O(n²)
C) $\Theta$ (n³)
D) $\Theta$ (n)

Question 13

If an RSA public key encryption system were based on the primes p = 3 and q = 7,which of the following pairs of values would be suitable for the encryption and decryption keys e and d?

A) 2 and 6
B) 5 and 29
C) 4 and 9
D) 7 and 23

Question 14

Which of the following statements is true?

A) The Bare Bones programming language would still be a universal language if the clear statement was removed.
B) The Bare Bones programming language would still be a universal language if the incr statement was removed.
C) The Bare Bones programming language would still be a universal language if the decr statement was removed.
D) The Bare Bones programming language would still be a universal language if the while statement was removeD.

Question 15

Which of the following questions has not yet been answered by researchers?

A) Is P contained in NP?
B) Is NP contained in P?
C) Are all the problems in NP solvable?
D) Are all the problems in P solvable?

Question 16

Turing machines represent

A) an effort to define the limits of algorithmic systems.
B) a class of machines that can compute very little.
C) a class of machines that are now out of date and no longer important.
D) a class of machines that can compute all functions.

Question 17

Which of the following statements is false?

A) If a problem can be solved by a Bare Bones program, then it can be solved by a Turing machine.
B) If a problem can be solved by a Turing machine, then it can be solved by a Bare Bones program.
C) The halting problem cannot be solved by a Bare Bones program.
D) The halting problem can be solved only by using a universal programming language.

Question 18

An unsolvable problem is a problem for which

A) no solution exists.
B) no one knows the solution.
C) no algorithm exists for finding the solution.
D) no one wants to known the solution.

Question 19

Which of the following Bare Bones programs is self-terminating?

A) while X not 0:
B) while X not 0:
C) decr X decr X while X not 0:

Question 20

Suppose the variables X and Y in the following Bare Bones program have the values 3 and 2,respectively,when execution begins.
$\begin{array} { l } \text { clear } \mathrm { Z } \\\text { while X not } 0 : \\\text { while } Y \text { not } 0 : \\\text { decr } Y \\\text { incr } Z \\\text { incr } \mathrm { Z } \\\text { decr } X\end{array}$
What will be the value of Z when the program terminates?

A) 0
B) 1
C) 5
D) 6

Question 21

Place an X in the blank before each of the following statements that guarantees that a problem is in P.
_____ The problem is in O(n²).
_____ The problem is in O(2?).
_____ The problem is in O(log? n).
_____ The problem is in O(n³).

Question 22

If we were using RSA encryption with the private keys n = 133 and d = 5,what would be the decrypted version of the encrypted message whose bit pattern is 11?
__________

Question 23

If the prime numbers underlying an RSA encryption system are small,the system is not secure.For example,suppose you were told that the public keys of a system were n = 15 and e = 13.
A.What are the two prime numbers on which the system is based?
_______ ________
B.What is the value of the decryption key d?

Question 24

A.Give an example of an algorithm for sorting a list with time complexity in $\Theta$ (n²).

B.Give an example of an algorithm for sorting a list with time complexity in $\Theta$ (n lg n).

Question 25

Give an example of a problem in NP that may not be in P.

Question 26

Identify a problem that does not have an algorithmic solution.

Question 27

A _______________ is a relationship between input and output values such that any input is associated
with only one output.If the output can be determined algorithmically from the input,the relationship is
said to be _______________ .

Question 28

List the letters associated with the following problems in the order of increasing complexity of the problems.
15.List the letters associated with the following problems in the order of increasing complexity of the problems.
A.Sorting a list
B.The halting problem
C.Searching through a list for a particular entry

Question 29

If we were using RSA encryption with the public keys n = 91 and e = 5,what would be the encrypted version of the message whose bit pattern is 11?
__________

Question 30

Place a T in the blank before each of the following statements that are true.Leave the other blanks blank.
_____ P is contained in NP.
_____ All solvable problems are in P.
_____ The traveling salesman problem is in NP.
_____ The traveling salesman problem is not solvable.

Question 31

Place an X in the blank before each of the following statements that contradict the Church-Turing thesis.Leave the other blanks blank.
_____ All functions are computable.
_____ Some functions that are not computable by Turing machines are computable by other
means.
_____ All computable functions are Turing-computable.
_____ Some problems cannot be solved by any Turing machine.

Question 32

Suppose the variable X in the following Bare Bones program has the value 3 when execution begins.
$\begin{array} { l } \text { clear } Y \\\text { decr } X \\\text { while X not } 0 : \\\text { decr } X \\\text { incr } Y\end{array}$
A.What will be the value of X when the program terminates?

B.What will be the value of Y when the program terminates?

Question 33

List the following complexity classes in order of increasing complexity.
$$\Theta \left( n ^ { 3 } \right) \quad \Theta \left( 2 ^ { n } \right) \quad \Theta \left( \log _ { 2 } n \right) \quad \Theta ( n )$$

Question 34

Suppose the variables X and Y in the following Bare Bones program have the values 3 and 2,respectively,when execution begins.What will be the value of Z when the program terminates?
_________
clear Z
while X not 0:
clear W
while Y not 0:
decr Y
incr W
while W not 0:
incr Z
incr Y
decr W
decr X
incr Z

Question 35

Give an example of a universal programming language.

Question 36

Place a T in the blank before each of the following statements that are true.Leave the other blanks blank.
_____ All Bare Bones programs that do not contain a while statement are self-terminating.
_____ All Bare Bones programs that contain a while statement are not self-terminating.
_____ Some Bare Bones programs are both self-terminating and not self-terminating.
_____ No Bare Bones program is both self-terminating and not self-terminating.

Question 37

Complete the following sentence.
An NP-complete problem is a problem in NP for which ___________________________.

Question 38

Suppose a problem in $\Theta$ (n³)has been solved in 1 second.How long should you expect the same machine to require to solve a new instance of the problem with input that is twice the size as before?

Question 39

Suppose the variables X and Y in the following Bare Bones program have the values 3 and 2,respectively,when execution begins.What will be the value of Z when the program terminates?
_________
clear Z
while X not 0:
decr X
incr Z
while Y not 0:
decr Y
incr Z

Question 40

Place an F in the blank before each of the following statements that are false.Leave the other blanks blank.
_____ No one has discovered a problem that cannot be solved by a Turing machine.
_____ The Bare Bones programming language would not be a universal language if the clear
statement were removed.
_____ The only problem that cannot be solved by a Turing machine is the halting problem.
_____ Some problems cannot be solved by any Turing machine.

Question 41

Write a program in Bare Bones that terminates with the variable Z equal to 1 if the variables X and Y start with non-zero values and with Z equal to 0 otherwise.

Question 42

What was Alan Turing's purpose when developing the concept of the Turing machine?

Question 43

What is a universal programming language?

Question 44

Why is a public key encryption system based on the RSA algorithm secure?

Question 45

Is a problem in O(n³)more complex than a problem in O(n²)? Explain your answer.

Question 46

State the Church-Turing thesis.

Question 47

Explain the distinction between time complexity and space complexity.

Question 48

Write a program in Bare Bones that will add one to the variable X if X is not 0 and leave X unchanged otherwise.

Question 49

Is the following Bare Bones program self-terminating? Explain your answer.
copy X to Z
decr Z
while Z not 0:
decr Z
decr X
while X not 0:

Question 50

Are all problems in P solvable in a reasonable amount of time? Explain your answer.

Question 51

Write a sequence of statements in the Bare Bones language that is equivalent to the statement
if X not 0:
S1
else:
S2
where S1 and S2 are sequences of Bare Bones statements.