Test Bank—Chapter Twelve (Theory of Computation)
Multiple Choice Questions
1. 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:
2. 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.
3. 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.
4. What action is performed by the Turing machine described below?
Current Current Value Direction New
state cell content to write to move state
START * * left X
X 1 0 left X
X 0 0 right Y
Y 0 0 right Y
Y * * no move HALT
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 *.
5. What action is performed by the Turing machine described below?
Current Current Value Direction New
state cell content to write to move state
START * * left X
X 1 1 left X
X 0 * right Y
Y 1 1 right Y
Y * * no move HALT
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 *.
6. Suppose the variables X and Y in the following Bare Bones program have the values 3 and 2,
respectively, when execution begins.
clear Z
while X not 0:
while Y not 0:
decr Y
incr Z
incr Z
decr X
What will be the value of Z when the program terminates?
A. 0 B. 1 C. 5 D. 6
7. Which of the following best describes what the following Bare Bones program does?
copy X to Z
clear X
incr X
while Z not 0:
clear X
decr Z
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.
8. 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.
9. 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.
10. 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
11. What is the time complexity of the problem of searching for a particular entry in a list?
A. (log2 n) B. (n) C. (n log2 n) D. (n2)
12. What is the time complexity of the problem of sorting a list?
A. (log2 n) B. (n) C. (n log2 n) D. (n2)
13. 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?
14. 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
15. 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
16. 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(n2).
D. X is in (n2).
17. If a solution with time complexity (n2) is known to exist, then the problem is known to be in which of
the following?
A. (n2) B. O(n2) C. (n3) D. (n)
18. 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
19. 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
20. 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
Fill-in-the-blank/Short-answer Questions
1. 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 _______________ .
2. Identify a problem that does not have an algorithmic solution.
_____________________
3. Give an example of a universal programming language.
_____________________
4. 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.
5. Suppose the variable X in the following Bare Bones program has the value 3 when execution begins.
clear Y
decr X
while X not 0:
decr X
incr Y
A. What will be the value of X when the program terminates?
_________
B. What will be the value of Y when the program terminates?
_________
6. 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
7. 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
8. 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.
9. 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.
10. Give an example of a problem in NP that may not be in P.
______________________
11. A. Give an example of an algorithm for sorting a list with time complexity in (n2).
______________________
B. Give an example of an algorithm for sorting a list with time complexity in (n lg n).
______________________
12. 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(n2).
_____ The problem is in O(2n).
_____ The problem is in O(log2 n).
_____ The problem is in O(n3).
13. List the following complexity classes in order of increasing complexity.
(n3) (2n) (log2 n) (n)
___________________________
14. Suppose a problem in (n3) 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?
________________
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
_____________________
16. Complete the following sentence.
An NP-complete problem is a problem in NP for which ___________________________
_________________________________________________________________ .
17. 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.
18. 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?
__________
19. 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?
__________
20. 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?
_______
Vocabulary (Matching) Questions
The following is a list of terms from the chapter along with descriptive phrases that can be used to produce
questions (depending on the topics covered in your course) in which the students are ask to match phrases
and terms. An example would be a question of the form, “In the blank next to each phrase, write the term
from the following list that is best described by the phrase.”
Term Descriptive Phrase
computable function A relationship between input and output values that can be determined
algorithmically
Turing machine An elementary, yet universal, computing device
Church-Turing thesis The conjecture that the Turing-computable functions are the same as
the computable functions
Turing computable Solvable by a Turing machine
halting problem An example of an unsolvable problem
universal language Allows a solution to any solvable problem to be expressed
unsolvable problem A problem with no algorithmic solution
NP A class of problems whose time complexity is not yet completely
understood
P The problems that have a polynomial time solution
nonpolynomial problems Problems with a high time complexity
nondeterministic algorithm May not perform the same if repeated in the identical environment
merge sort algorithm Has time complexity of (n log2 n)
traveling salesman problem An NP complete problem
private keys The decryption values in a public key encryption system
RSA A public key encryption system
23 (mod 7) The remainder after division
General Format Questions
1. State the Church-Turing thesis.
2. What was Alan Turing’s purpose when developing the concept of the Turing machine?
3. What is a universal programming language?
4. 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.
5. Write a program in Bare Bones that will add one to the variable X if X is not 0 and leave X unchanged
otherwise.
6. 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:
7. 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.
8. Explain the distinction between time complexity and space complexity.
9. Is a problem in O(n3) more complex than a problem in O(n2)? Explain your answer.
10. Are all problems in P solvable in a reasonable amount of time? Explain your answer.
11. Why is a public key encryption system based on the RSA algorithm secure?