Part I concerns establishing which problems can and cannot be solved in any way at all, using computers. Part II studies which problems can and cannot be solved within given limits on computational resources such as memory space and running time. For example, it will be proven that there exist problems that, while solvable, cannot be solved efficiently, regardless of how clever one is at programming or mathematical analysis. The approach gives more natural definitions, proofs and perspectives on classical theorems by Cook, Hartmanis, Savitch, etc. A course that gives a solid introduction to the mathematics of reduction systems - the basis of operational semantics and abstract machines.
Optimization is achieved by changing the times at which computations are performed.
This has a quite remarkable impact on software development because it allows the design of general and resuable software without the penalty of being too inefficient. This course gives a solid introduction to partial evaluation, compiler generation and other applications. Partial evaluation is an automatic program optimization technique, similar in concept to, but in several ways different from optimizing compilers. Optimization is achieved by changing the times at which computations are performed. This has a quite remarkable impact on software development because it allows the design of general and resuable software without the penalty of being too inefficient.