Course outline
Module 1
Module 1: Introduction to Complexity Theory
Introduction to Complexity Theory
Knowledge check
Q1. What is the primary focus of complexity theory?
- A. Designing efficient algorithms
- B. Classifying problems based on their inherent difficulty ✓
- C. Optimizing data structures
- D. Analyzing programming languages
Why: Complexity theory primarily focuses on classifying computational problems based on their inherent difficulty and the resources required to solve them.
Q2. Which complexity class contains problems that can be solved in polynomial time?
- A. NP
- B. P ✓
- C. NPC
- D. PSPACE
Why: The complexity class P contains problems that can be solved in polynomial time by a deterministic Turing machine.
Q3. Which of the following is a characteristic of an NP problem?
- A. It can be solved in polynomial time
- B. Its solution can be verified in polynomial time ✓
- C. It requires exponential time to solve
- D. It cannot be solved in polynomial time
Why: NP problems are characterized by the fact that their solutions can be verified in polynomial time, even if they cannot be solved in polynomial time.
Q4. Which of the following is an example of a problem in P?
- A. Traveling Salesman Problem
- B. Sorting a list of numbers ✓
- C. Boolean Satisfiability Problem
- D. Knapsack Problem
Why: Sorting a list of numbers is an example of a problem in P, as it can be solved in polynomial time using algorithms like merge sort or quicksort.
Q5. What does the term 'tractable' refer to in complexity theory?
- A. Problems that are easy to solve but hard to verify
- B. Problems that can be solved in polynomial time ✓
- C. Problems that require exponential time to solve
- D. Problems that are undecidable
Why: In complexity theory, 'tractable' refers to problems that can be solved in polynomial time, typically considered to be efficiently solvable.
Module 2
Module 2: Measuring Problem Difficulty
Measuring Problem Difficulty
Knowledge check
Q1. What is the primary factor used to measure the difficulty of a problem in complexity theory?
- A. The number of inputs
- B. The time required to solve the problem ✓
- C. The size of the output
- D. The number of algorithms available
Why: The difficulty of a problem is primarily measured by the time required to solve it, especially as the input size grows.
Q2. Which complexity class contains problems that can be solved in polynomial time?
- A. NP
- B. P ✓
- C. NP-Hard
- D. PSPACE
Why: The complexity class P contains problems that can be solved in polynomial time by a deterministic Turing machine.
Q3. Which of the following is a characteristic of an NP problem?
- A. It can be solved in polynomial time
- B. Its solution can be verified in polynomial time ✓
- C. It cannot be solved in exponential time
- D. It requires a non-deterministic algorithm to solve
Why: NP problems are characterized by the fact that their solutions can be verified in polynomial time, even if finding the solution might take longer.
Q4. What is the significance of the P vs NP problem?
- A. It determines the efficiency of all algorithms
- B. It determines whether all NP problems can be solved in polynomial time ✓
- C. It determines the size of input for algorithms
- D. It determines the number of algorithms available for a problem
Why: The P vs NP problem is significant because it determines whether all NP problems can be solved in polynomial time, which would have profound implications for computer science.
Q5. Which of the following is an example of a problem in P?
- A. Traveling Salesman Problem
- B. Integer Factorization
- C. Shortest Path Problem ✓
- D. Boolean Satisfiability Problem
Why: The Shortest Path Problem is an example of a problem in P because it can be solved in polynomial time using algorithms like Dijkstra's.
Module 3
Module 3: Time and Space Complexity
Time and Space Complexity
Knowledge check
Q1. What does time complexity measure?
- A. The amount of memory used by an algorithm
- B. The amount of time an algorithm takes to run as a function of input size ✓
- C. The number of operations performed by an algorithm
- D. The size of the input data
Why: Time complexity measures how the runtime of an algorithm increases with the size of the input data.
Q2. Which of the following notations is used to describe the upper bound of an algorithm's time complexity?
- A. Omega notation
- B. Theta notation
- C. Big O notation ✓
- D. Little o notation
Why: Big O notation is used to describe the upper bound of an algorithm's time complexity.
Q3. What is the time complexity of a linear search algorithm in the worst case?
- A. O(1)
- B. O(n) ✓
- C. O(log n)
- D. O(n^2)
Why: In the worst case, a linear search algorithm has to check every element in the list, resulting in a time complexity of O(n).
Q4. Which of the following time complexities is the best for an algorithm?
- A. O(n^2)
- B. O(n log n)
- C. O(1) ✓
- D. O(n)
Why: O(1) is the best time complexity as it indicates constant time, meaning the algorithm's runtime does not depend on the input size.
Q5. What is the space complexity of an algorithm?
- A. The amount of time an algorithm takes to run
- B. The amount of memory an algorithm uses as a function of input size ✓
- C. The number of operations performed by an algorithm
- D. The size of the input data
Why: Space complexity measures the amount of memory an algorithm uses as a function of input size.
Module 4
Module 4: Big O Notation
Big O Notation
Knowledge check
Q1. What does Big O notation describe?
- A. The exact runtime of an algorithm
- B. The upper bound of an algorithm's runtime ✓
- C. The average case runtime of an algorithm
- D. The lower bound of an algorithm's runtime
Why: Big O notation is used to describe the worst-case scenario and gives an upper bound on the time complexity of an algorithm.
Q2. Which of the following time complexities is the most efficient?
- A. O(n²)
- B. O(n log n)
- C. O(2ⁿ)
- D. O(1) ✓
Why: O(1) represents constant time complexity, which is the most efficient as it does not depend on the input size.
Q3. What is the time complexity of a linear search algorithm in the worst case?
- A. O(1)
- B. O(n) ✓
- C. O(log n)
- D. O(n²)
Why: In the worst case, a linear search may have to check every element in the list, resulting in a time complexity of O(n).
Q4. Which of the following is not a valid Big O notation?
- A. O(n)
- B. O(log n)
- C. O(n log n)
- D. O(1/n) ✓
Why: Big O notation is used to describe growth rates, and O(1/n) is not a valid notation as it implies the algorithm's runtime decreases with input size.
Q5. What does O(n) time complexity mean?
- A. The runtime grows exponentially with input size
- B. The runtime grows linearly with input size ✓
- C. The runtime is constant regardless of input size
- D. The runtime grows logarithmically with input size
Why: O(n) indicates that the runtime of the algorithm increases linearly with the size of the input.
Module 5
Module 5: P vs NP Problem
P vs NP Problem
Knowledge check
Q1. What does the P vs NP problem ask?
- A. Whether all problems can be solved in polynomial time
- B. Whether all problems whose solutions can be verified in polynomial time can also be solved in polynomial time ✓
- C. Whether NP problems are more complex than P problems
- D. Whether there are problems that cannot be solved at all
Why: The P vs NP problem specifically asks whether every problem that can be verified in polynomial time (NP) can also be solved in polynomial time (P).
Q2. Which of the following is a characteristic of problems in P?
- A. They cannot be solved efficiently
- B. They can be solved in polynomial time ✓
- C. They require exponential time to solve
- D. They are undecidable
Why: Problems in P are those that can be solved in polynomial time by a deterministic Turing machine.
Q3. Which of the following is an example of an NP problem?
- A. Finding the shortest path in a graph
- B. Sorting a list of numbers
- C. Solving a Sudoku puzzle ✓
- D. Multiplying two matrices
Why: Solving a Sudoku puzzle is an example of an NP problem because it can be verified in polynomial time, but it may not be solvable in polynomial time.
Q4. What would happen if P = NP?
- A. All problems would become unsolvable
- B. All problems would become solvable in polynomial time ✓
- C. NP problems would become easier to verify
- D. No change would occur
Why: If P = NP, it would mean that every problem whose solution can be verified in polynomial time can also be solved in polynomial time.
Q5. What is the significance of the P vs NP problem?
- A. It has no real-world implications
- B. It is one of the most important open questions in computer science ✓
- C. It has already been solved
- D. It is only relevant for theoretical computer scientists
Why: The P vs NP problem is considered one of the most important open questions in computer science due to its implications for cryptography, optimization, and computational complexity.
Module 6
Module 6: NP-Completeness
NP-Completeness
Knowledge check
Q1. What does NP stand for in the context of computational complexity theory?
- A. Non-Polynomial
- B. Nondeterministic Polynomial ✓
- C. Non-Predictable
- D. Numerical Problems
Why: NP stands for Nondeterministic Polynomial, referring to problems that can be solved in polynomial time by a nondeterministic Turing machine.
Q2. Which of the following is a defining characteristic of NP-Complete problems?
- A. They can be solved in logarithmic time
- B. They are the hardest problems in NP ✓
- C. They can be reduced to P problems
- D. They are solvable in exponential time
Why: NP-Complete problems are the hardest problems in NP, as every problem in NP can be reduced to them in polynomial time.
Q3. Which of the following problems is known to be NP-Complete?
- A. Shortest Path Problem
- B. Traveling Salesman Problem ✓
- C. Binary Search Problem
- D. Matrix Multiplication Problem
Why: The Traveling Salesman Problem is a well-known NP-Complete problem, involving finding the shortest possible route that visits each city exactly once and returns to the origin.
Q4. What is the relationship between P and NP?
- A. P is a subset of NP ✓
- B. NP is a subset of P
- C. P and NP are disjoint sets
- D. P and NP are equal
Why: P is a subset of NP, as any problem that can be solved in polynomial time by a deterministic Turing machine can also be solved in polynomial time by a nondeterministic Turing machine.
Q5. What would happen if someone proved that P = NP?
- A. All problems would become solvable in polynomial time
- B. NP-Complete problems would become solvable in polynomial time ✓
- C. It would imply that P is not equal to NP
- D. It would have no impact on computational complexity
Why: If P = NP, then all NP-Complete problems would become solvable in polynomial time, as they would fall within P.
Module 7
Module 7: Reductions and Algorithm Design
Reductions and Algorithm Design
Knowledge check
Q1. What is the primary purpose of a reduction in complexity theory?
- A. To increase the time complexity of an algorithm
- B. To transform one problem into another problem ✓
- C. To find the optimal solution for a problem
- D. To prove that a problem is undecidable
Why: A reduction is a method of transforming one problem into another, often used to show the relative difficulty of problems.
Q2. Which of the following is a common type of reduction used in complexity theory?
- A. Polynomial-time reduction ✓
- B. Exponential-time reduction
- C. Logarithmic-time reduction
- D. Constant-time reduction
Why: Polynomial-time reductions are commonly used to show that one problem can be solved as efficiently as another.
Q3. What does it mean if problem A is reducible to problem B?
- A. Problem B is easier to solve than problem A
- B. Problem A can be transformed into problem B in polynomial time ✓
- C. Problem B can be transformed into problem A in polynomial time
- D. Problem A and problem B are equivalent in difficulty
Why: If problem A is reducible to problem B, it means that solving problem B can help solve problem A, typically within polynomial time.
Q4. Which of the following is a key use of reductions in algorithm design?
- A. To create more complex algorithms
- B. To prove the correctness of an algorithm
- C. To show the equivalence between problems
- D. To simplify a problem into a known problem ✓
Why: Reductions are often used to simplify a new problem into a known one, allowing the use of existing solutions.
Q5. What is a key requirement for a reduction to be useful in complexity theory?
- A. It must be deterministic
- B. It must be computable in polynomial time ✓
- C. It must be reversible
- D. It must be applicable to all problems
Why: A useful reduction in complexity theory must be computable in polynomial time to ensure that the transformation is efficient.