Question 1

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?

Accepted Answer

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

Question 2

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.

Accepted Answer

One soluti...

Question 3

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

Accepted Answer

A)     Θ \varThetaΘ (n2) 
B)   O(n2) 
C)     Θ \varThetaΘ (n3) 
D)     Θ \varThetaΘ (n)  E) A) and B)
F) A) and C)

Question 4

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

Accepted Answer

The most l...

Question 5

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

Accepted Answer

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?E) B) and D)
F) B) and C)

Question 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?

Accepted Answer

A)   0
B)   1
C)   5
D)   6E) A) and D)
F) B) and D)

Question 7

Give an example of a universal programming language.
_____________________

Accepted Answer

The most likely answer is Bare...

Question 8

What is a universal programming language?

Accepted Answer

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

Question 9

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

Accepted 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 enormous-even for small inputs.

Question 10

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;

Accepted Answer

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.E) None of the above
F) B) and D)

Question 11

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

Accepted Answer

Not necessarily. To say that p...

Question 12

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

Accepted Answer

A)     Θ \varThetaΘ (lg n) 
B)     Θ \varThetaΘ (n) 
C)     Θ \varThetaΘ (n lg n) 
D)     Θ \varThetaΘ (n2)  E) A) and B)
F) All of the above

Question 13

What action is performed by the Turing machine described below?

Accepted Answer

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 *.E) A) and B)
F) None of the above

Question 14

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

Accepted Answer

First, thi...

Question 15

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.

Accepted Answer

One soluti...

Question 16

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

Accepted Answer

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 = 13E) A) and C)
F) C) and D)

Question 17

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.

Accepted Answer

The answer of Place a T in the blank before...

Question 18

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.

Accepted Answer

The answer of Place an X in the blank before...

Question 19

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

Accepted Answer

A)   Insertion sort
B)   Bubble sort
C)   Selection sort
D)   Merge sortE) B) and C)
F) A) and D)

Question 20

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

Accepted Answer

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

Exam 11: Artificial Intelligence

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?

Correct Answer
verified

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.

Correct Answer
verified
One soluti...
View Answer

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

Correct Answer
verified

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

Correct Answer
verified
The most l...
View Answer

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

Correct Answer
verified

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?

Correct Answer
verified

Give an example of a universal programming language. _____________________

Correct Answer
verified
The most likely answer is Bare...
View Answer

What is a universal programming language?

Correct Answer
verified
A universal programming language is a programming language with which a solution to any solvable problem can be expressed.

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

Correct Answer
verified
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 enormous-even for small inputs.

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;

Correct Answer
verified

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

Correct Answer
verified
Not necessarily. To say that p...
View Answer

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

Correct Answer
verified

What action is performed by the Turing machine described below?

Correct Answer
verified

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

Correct Answer
verified
First, thi...
View Answer

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.

Correct Answer
verified
One soluti...
View Answer

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

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

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

Correct Answer
verified

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

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

Exam 11: Artificial Intelligence

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?

Correct AnswerverifiedShow Answer

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.

Correct AnswerverifiedOne soluti...View AnswerShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedThe most l...View AnswerShow Answer

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

Correct AnswerverifiedShow Answer

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?

Correct AnswerverifiedShow Answer

Give an example of a universal programming language. _____________________

Correct AnswerverifiedThe most likely answer is Bare...View AnswerShow Answer

What is a universal programming language?

Correct AnswerverifiedA universal programming language is a programming language with which a solution to any solvable problem can be expressed.

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

Correct AnswerverifiedNo. 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 enormous-even for small inputs.

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;

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedNot necessarily. To say that p...View AnswerShow Answer

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

Correct AnswerverifiedShow Answer

What action is performed by the Turing machine described below?

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedFirst, thi...View AnswerShow Answer

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.

Correct AnswerverifiedOne soluti...View AnswerShow Answer

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

Correct AnswerverifiedShow Answer

Correct AnswerverifiedShow Answer

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedIt is secure because no one knows a fast way to find the prime factors of the public key n.

Correct Answer
verified

Correct Answer
verified
One soluti...
View Answer

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

Correct Answer
verified

Correct Answer
verified
The most l...
View Answer

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified
The most likely answer is Bare...
View Answer

Correct Answer
verified
A universal programming language is a programming language with which a solution to any solvable problem can be expressed.

Correct Answer
verified
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 enormous-even for small inputs.

Correct Answer
verified

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

Correct Answer
verified
Not necessarily. To say that p...
View Answer

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified
First, thi...
View Answer

Correct Answer
verified
One soluti...
View Answer

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

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