I've been thinking about what "computational thinking" actually means ever since a workshop at Microsoft in 2007, where I found that everyone's definition seemed to boil down to, "Whatever I've been pushing for the last decade, but with a new name." My ideas keep evolving, but Lewis Epstein's wonderful book Thinking Physics remains their foundation. In it, he presents dozens of problems in freshman physics that can be solved without calculation, so long as you have a solid grasp of basic Newtonian mechanics. For example: put a large piece of ice in a bathtub, then fill the bathtub exactly to the rim. When the ice melts, will the water overflow, will the water level go down, or will it stay the same? The answer is that it will stay the same, because the ice displaced its own weight in water, so when it melts, it exactly fills the "hole" it created. But that's not the real question; the real question is, imagine you put a large cake of ice in the tub, then put a small iron weight on the ice cake, and then filled the tub to the rim. This time, when the ice melts and the iron weight sinks to the bottom of the tub, what happens to the water level?
Someone who can answer problems like these actually understands physics; someone who has only learned how to pattern-match solution techniques to word problems won't be able to reason them through. I don't know of an equivalent book on computing: things like the Levitins' Algorithmic Puzzles aren't really the same, since there are tricks to the solutions of puzzles, and our driver's license exam isn't really the same thing either. If you know of something that is, we'd welcome a pointer.
Originally posted at Software Carpentry.