What Is A Computer and What Can It Do? An Algorithms-Oriented Introduction to the Theory of Computation |

By the time students reach the end of a course on algorithm design, they are starting to ask questions about what computers can and cannot do: Is there a polynomial-time algorithm for every computational problem? Can every problem be solved using dynamic programming? Can every problem be formulated as a graph problem?