Lesson 28: What cannot be computed

Outline:

  1. Review of merge sort
  2. Mini-quiz
  3. Hard Problems
    • review: bin packing
    • another intractable problem: Towers of Hanoi
    • an unsolvable problem: The Halting Problem

Reading assignment (to be completed by the next class):

  • Zelle section 13.4 (pp. 484-494)