Deck 11: Artificial Intelligence

Question 1

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 1

C

Question 2

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 2

A

Question 3

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 3

B

Question 4

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 5

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 6

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

A) $\varTheta$ (lg n)
B) $\varTheta$ (n)
C) $\varTheta$ (n lg n)
D) $\varTheta$ (n²)

Question 7

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

Question 8

What action is performed by the Turing machine described below?

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 9

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 10

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 11

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

A) $\varTheta$ (lg n)
B) $\varTheta$ (n)
C) $\varTheta$ (n lg n)
D) $\varTheta$ (n²)

Question 12

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

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

Question 13

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 14

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.

Question 15

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 16

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;

Question 17

What action is performed by the Turing machine described below?

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 18

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 19

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 $\varTheta$ (n²).

Question 20

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 21

Place an X in the blank before each of the following statements that guarantees that a problem is in P.

Question 22

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 23

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 24

State the Church-Turing thesis.

Question 25

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

Question 26

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 27

Give an example of a universal programming language.
_____________________

Question 28

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

Question 29

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 30

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 31

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

Question 32

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 33

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

Question 34

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.

Question 35

What is a universal programming language?

Question 36

Explain the distinction between time complexity and space complexity.

Question 37

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

Question 38

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

Question 39

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