[19.1] Imagine you are trying to find the largest number in a small list of numbers using brute force. Describe how you would do this and what would the runtime be in that case?.
To find the largest number using brute force, you would iterate over the list once, while keeping track of the largest number and comparing the current largest with each element. This method would run in O(n) time.
[19.2] What does it mean for an algorithm to be in the class P? Give a simple example of an operation or task that would be in class P.
A problem is in class P if it can be solved in polynomial time, meaning the time it takes to solve the problem increases polynomially with the size of the input. An example of a task in class P is finding the sum of all numbers in a list by scanning through the list once, which has a linear time complexity, O(n).
[19.3] Explain what the NP class represents. Provide an example of a problem that is in the NP class.
The NP class represents problems for which a solution, once found, can be verified in polynomial time. An example problem is determining whether a graph has a Hamiltonian cycle (a cycle that visits each vertex exactly once). Verifying a given cycle is quick, but finding one (if it exists) can be very slow. Another example is the Boolean Satisfiability problem that we discussed in class.
[19.4] What makes a problem tractable? Give an example of a tractable problem.
A problem is tractable if it can be solved in polynomial time, meaning there exists an algorithm that can solve the problem efficiently as the size of the input grows. An example of a tractable problem is using binary search in a list of numbers O(logn).
[19.5] Describe what a heuristic is in the context of solving problems and provide an example of when one might be used.
A heuristic is a technique that finds a good-enough solution for a problem quickly, often by sacrificing completeness, accuracy, or optimality. An example of using a heuristic is in solving the traveling salesperson problem, where instead of finding the shortest possible route, we settle for a route that is short (i.e., less than a value X) but not necessarily the shortest.
[19.6] Which of the following complexity classes represents problems that can be solved in polynomial time?
A. O(n!)
B. O(2^n)
C. O(n^2)
D. O(n^n)
Answer: C. O(n^2)
[19.7] The Traveling Salesperson Problem (TSP) can be efficiently solved in polynomial time.
Answer: False
[19.8] A problem is considered _______ if it can be solved in a time that increases polynomially with the size of the input.
Answer: tractable
[19.9] Match the following problems with their likely complexity class:
Problems:
Sorting a list of numbers.
Finding a specific path in a maze.
Checking if a large number is prime.
Complexity Classes:
A. P
B. NP
The answers are matched as follows: Sorting a list of numbers (P), Finding a specific path in a maze (NP), Checking if a large number is prime (P)
[19.10] Can all NP problems be verified in polynomial time?
Answer: Yes
[19.11] Which of the following is NOT a characteristic of NP-complete problems?
A. They can be solved in polynomial time.
B. They are at least as hard as the hardest problems in NP.
C. Their solution can be verified in polynomial time.
D. They can be used to solve all other NP problems.
Answer: A. They can be solved in polynomial time.
[19.12] Every problem in NP is also in P.
Answer: As far as we know, scientists have not found the answer to this problem. But currently, we consider this statement False.