I recently gave a pair of talks in the Math Department’s Applied Math Seminar on basics of TCS. It was intended for a mathematically mature audience with no background in TCS. The slides for the talk are available here; they are far from perfect — but I will happily take suggestions on things that should be dropped or added. Interest in the talk was pleasantly high. High enough that I plan on doing this again and advertising more broadly — to graduate students in physics, engineering, etc. I also think it acts as a list of topics about which students should be able to answer questions during a comprehensive exam.
Hint. Hint.
You could, of course, mention cryptography. (If complexity is about the limits of computation, and algorithms involves working within those limits, then cryptography exploits those limits for beneficial use.)
It is great that you are spreading the word about TOC. You may be interested in a general audience talk I gave a few years ago: http://research.microsoft.com/en-us/people/omreing/school.ppt
Thanks for the link!
What about stuff like computational logic and automata theory? Do you not consider it TCS?
Given the time limit (< 2hr), I did not attempt to be complete. However, I would be interested to know what you take out in order to add something else.