# Complexity Explorer Santa Few Institute

## Introduction to Computation Theory

• Absolute Limitations on Algorithms
• Resource limitations on algorithms
• Divide and Conquer
• Greedy
• Landscapes
• P versus NP
• Building computers out of other problems
• An algorithmic perspective on complex systems
• Heuristics 2
• Randomized Algorithms I
• Randomized Algorithms II
• Randomized Algorithms III
• Homework

#### 4.4 Quiz » Quiz Explanation

1) Divide-and-conquer can't be used to eciently solve all problems.

True - Some problems, in particular NP-complete problems, seem to be not amenable to divide-and-conquer. And of course, divide-and-conquer doesn't help us solve uncomputable problems like the halting problem.

2) Greedy algorithms always succeed because they make the best choice

at each step.

False - There are problems that are not amenable to greedy algorithms. Most notably, NP-complete problems seem to have this property. In particular, the "best'' choice at one step may force you down a path where, although the algorithm made the best choice at each step, the resulting solution is not optimal.

3) For max-flow, by allowing moves which "push flow backwards''---while respecting the constraint that no edge ever has negative flow---you can always reach the global optimum by the greedy algorithm.

True - True (for an explanation see the lecture video)

4) For any optimization problem, you can add allowable moves such that the resulting greedy algorithm always finds the global optimum.

False - As with the preceding questions, consider NP-complete problems, or even uncomputable optimization problems.