Question 1

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

Accepted Answer

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

Question 2

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

Accepted Answer

The answer of If we were using RSA encryption with...

Question 3

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?

Accepted Answer

The answer of If the prime numbers underlying an RSA...

Question 4

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

Accepted Answer

The answer of A.Give an example of an algorithm for...

Question 5

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

Accepted Answer

The answer of Give an example of a problem in...

Question 6

Identify a problem that does not have an algorithmic solution.

Accepted Answer

The answer of Identify a problem that does not have...

Question 7

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

Accepted Answer

The answer of A _______________ is a relationship between input...

Question 8

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

Accepted Answer

The answer of List the letters associated with the following...

Question 9

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

Accepted Answer

The answer of If we were using RSA encryption with...

Question 10

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.

Accepted Answer

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

Question 11

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 12

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?

Accepted Answer

The answer of Suppose the variable X in the following...

Question 13

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

Accepted Answer

The answer of List the following complexity classes in order...

Question 14

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?
_________
$\begin{array} { l } 
\text { clear } \mathrm { Z } \
\text { while X not } 0 : \
\text { clear } W \
\text { while } Y \text { not } 0 : \
\text { decr } Y \
\text { incr } W \
\text { while } W \text { not } 0 : \
\text { incr } \mathrm { Z } \
\text { incr } Y \
\text { decr } W \
\text { decr } \mathrm { X } \
\text { incr } \mathrm { Z }
\end{array}$

Accepted Answer

The answer of Suppose the variables X and Y in...

Question 15

Give an example of a universal programming language.

Accepted Answer

The answer of Give an example of a universal programming...

Question 16

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 17

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

Accepted Answer

The answer of Complete the following sentence.
An NP-complete problem is...

Question 18

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?

Accepted Answer

The answer of Suppose a problem in $\Theta$ (n³)has been...

Question 19

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?
_________
$\begin{array} { c } 
\text { clear } \mathrm { Z } \
\text { while } \mathrm { X } \text { not } 0 \text { : } \
\text { decr } \mathrm { X } \
\text { incr } \mathrm { Z } \
\text { while } \mathrm { Y } \text { not } 0 : \
\text { decr } \mathrm { Y } \
\text { incr } \mathrm { Z }
\end{array}$

Accepted Answer

The answer of Suppose the variables X and Y in...

Question 20

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.

Accepted Answer

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

Quiz 12: Theory of Computation

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

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

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?

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

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

Identify a problem that does not have an algorithmic solution.

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

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

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.

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

Give an example of a universal programming language.

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

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?

Quiz 12: Theory of Computation

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

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

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

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

Identify a problem that does not have an algorithmic solution.

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

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

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.

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

Give an example of a universal programming language.

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

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?

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

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

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

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.

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

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?