Elements of the Theory of Computation – James Grimmelmann, Harry R. Lewis, Christos H. Papadimitriou – 2nd Edition

This manual contains, with some exceptions, solutions to all the problems raised in Elements of Computation Theory. Certain problems that are intractable are omitted as indicated, although where a correct interpretation was available for a clearly “wrong” problem, a solution to the problem as intended is presented instead.

The level of rigor of the solutions varies: the general approach is to give an accurate formal construct, along with insight into why the construct works, and a brief synopsis of how a rigorous proof of correctness might be given.