Your shopping cart is empty!

Welcome visitor you can login or create an account.

Categories

Test BankChapter Twelve (Theory of Computation)

Multiple Choice Questions

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

A. while X not 0 do; B. while X not 0 do; C. decr X;

end; decr X; while X not 0 do;

end; end;

ANSWER: B

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.

ANSWER: C

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.

ANSWER: B

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

ANSWER: A

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

ANSWER: C

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 do;

while Y not 0 do;

decr Y;

incr Z;

end;

incr Z;

decr X;

end;

What will be the value of Z when the program terminates?

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

ANSWER: C

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 do;

clear X;

decr Z;

end;

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.

ANSWER: B

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.

ANSWER: D

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.

ANSWER: A

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

ANSWER: C

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

A. (lg n) B. (n) C. (n lg n) D. (n2)

ANSWER: A

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

A. (lg n) B. (n) C. (n lg n) D. (n2)

ANSWER: C

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?

ANSWER: B

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

ANSWER: D

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

ANSWER: D

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

ANSWER: D

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)

ANSWER: B

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

ANSWER: C

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

ANSWER: B

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

ANSWER: A

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

ANSWER: function, computable

2. Identify a problem that does not have an algorithmic solution.

_____________________

ANSWER: The most likely answer is the halting problem.

3. Give an example of a universal programming language.

_____________________

ANSWER: The most likely answer is Bare Bones although almost any programming language is universal and thus a correct answer.

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.

ANSWER: First and fourth

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 do;

decr X;

incr Y;

end;

A. What will be the value of X when the program terminates?

_________

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

_________

ANSWER: A. 0 B. 2

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 do;

decr X;

incr Z;

end;

while Y not 0 do;

decr Y;

incr Z;

end;

ANSWER: 5

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 do;

clear W;

while Y not 0 do;

decr Y;

incr W;

end;

while W not 0 do;

incr Z;

incr Y;

decr W;

end;

decr X;

incr Z;

end;

ANSWER: 6

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.

ANSWER: First, second, and third

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.

ANSWER: First and second

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

______________________

ANSWER: The traveling salesman problem is one answer. (The knapsack problem is also mentioned in the text.)

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

______________________

ANSWER: A. insertion sort B. merge sort

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(lg n).

_____ The problem is in O(n3).

ANSWER: First, third, and fourth

13. List the following complexity classes in order of increasing complexity.

(n3) (2n) (lg n) (n)

___________________________

ANSWER: (lg n), (n), (n3), (2n)

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?

________________

ANSWER: 8 seconds

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

_____________________

ANSWER: C, A, B

16. Complete the following sentence.

An NP-complete problem is a problem in NP for which ___________________________

_________________________________________________________________ .

ANSWER: the existence of a deterministic polynomial time solution would imply that P = NP.

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.

ANSWER: First and third

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?

__________

ANSWER: 111101 (which is binary for 61)

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?

__________

ANSWER: 1101110 (which is binary for 110)

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?

_______

ANSWER: A. 3 and 5 B. 5

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

ANSWER: The Turing-computable functions are the same as the computable functions.

2. What was Alan Turings purpose when developing the concept of the Turing machine?

ANSWER: The purpose was to design a system that could compute any computable function.

3. What is a universal programming language?

ANSWER: A universal programming language is a programming language with which a solution to any solvable problem can be expressed.

4. Write a sequence of statements in the Bare Bones language that is equivalent to the statement

if X not 0 then S1 else S2

where S1 and S2 are sequences of Bare Bones statements.

ANSWER: One solution would be the following:

copy X to Y;

clear Z;

incr Z;

while Y not 0 do;

S1;

clear Y;

clear Z;

end;

while Z not 0 do;

S2;

clear Z;

end;

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.

ANSWER: One solution would be the following:

copy X to Z;

while Z not 0 do;

incr X;

clear Z;

end;

6. Is the following Bare Bones program self-terminating? Explain your answer.

copy X to Z;

decr Z;

while Z not 0 do;

decr Z;

decr X;

end;

while X not 0 do;

end;

ANSWER: No. If the program is run with X and Z containing the programs encoded value, then the last loop will be reached with the variable X assigned the value 1 so the last loop will execute forever.

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.

ANSWER: One solution would be the following:

clear Z;

copy X to V;

copy Y to W;

while V not 0 do;

while W not 0 do;

incr Z;

clear W;

end;

clear V;

end;

8. Explain the distinction between time complexity and space complexity.

ANSWER: Time complexity measures the amount of time required to solve a problem. Space complexity measures the amount of storage space required to solve a problem.

9. Is a problem in O(n3) more complex than a problem in O(n2)? Explain your answer.

ANSWER: Not necessarily. To say that problem is in O(n3) merely means that it is no more complex than (n3). Thus, a problem in O(n3) may actually be in (n).

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

ANSWER: No. Simply because the time complexity of a problem is bounded by a polynomial does not mean that the problem can be solved quickly. If the degree of the polynomial is large, the time required could be enormouseven for small inputs.

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

ANSWER: It is secure because no one knows a fast way to find the prime factors of the public key n.

Welcome to Test bank Fan

Once the order is placed, the order __will be delivered to your email less than 24 hours, mostly within 4 hours. __

If you have questions, you can contact us here

May also like