Limitations of Algorithmic power

• Read section 11.1 (pages 386-393)
• What is the goal of a lower-bound argument?
• What is a lower bound for a problem? When is it said to be tight?
• How do we obtain a trivial lower bound for a problem?
  • What would be the trivial lower bound for the problem of sorting \(n\) numbers?
  • What would be the trivial lower bound for the problem of evaluating a polynomial of degree \(n\)?
• What is the main idea behind information-theoretic lower bounds?
  • Explain the idea in the context of an algorithm trying to guess a number from \(1\) to \(n\).
• What is the main idea behind the adversary method for lower bounds?
  • Explain the idea in the context of an algorithm trying to guess a number from \(1\) to \(n\).
  • This method is based around the idea of a malevolent but honest adversary. Explain what that means.
• Describe the problem reduction approach to establishing lower bounds. What is this idea based on?
• Practice problems: 11.1.3, 11.1.5