H5

Name:

Homework 5

Question 1 [7 pts]

Describe how an algorithm with linear time complexity behaves.

Describe how an algorithm with exponential time complexity behaves.

Question 2 [7 pts]

Describe time and space complexity of an algorithm. Explain the relationship between them.

Question 3 [7 pts]

Describe polynomial time ( P) and nondeterministic polynomial time ( NP) algorithms. What is the difference between them? Give examples to each.

Question 4 [7 pts]

What is an NP-complete problem? Describe the factoring problem that the RSA algorithm is based on.

Question 5 [7 pts]

Which of the following statements are correct?

· Quadratic time complexity is a type of polynomial complexity

· Superpolynomial time complex algorithms are harder to solve than algorithms with exponential time complexity.

· Trying to find the 128-bit key of a cipher text encrypted with AES is a problem with exponential complexity

· Factoring problem that RSA is using is not probably an NP-complete problem.