I was offered to teach a novel TCS high school program, which requires constructing a curriculum. I would very much like to hear opinions and suggestions regarding this.
First, does anyone know of high schools where a TCS program has been taught successfully (or unsuccessfully)?
The idea is for a 3-year program (10th-12th grades, ages 16-18), about 8 weekly hours, for selected outstanding students, meaning that it can and should be demanding. Unlike the standard "computers" program, this program should not focus on programming, but rather on selected topics in CS, mostly in TCS. The topics we have in mind so far are, broadly:
- Asymptotic analysis
- Basic data structures and algorithms (lists, arrays)
- Graph algorithms, also as a demonstration of greedy algorithms v.s. dynamic programming.
- Other algorithms (e.g. probabilistic)
- Computability - the concept of a TM, reduction, decidability.
- Complexity - NP, P, perhaps PSPACE and NL. Completeness.
- Automata theory
Basically, this covers the TCS part of the first two years of a B.Sc in CS. However, we must keep in mind that these students lack the mathematical foundation needed for most of this material. In particular, things like set theory, combinatorics, probability, and modular artihmetic are not taught in high school (unfortunately).
To sum up, and to give precise questions:
- Does anyone know of a similar program anywhere?
- Are there suggestions for concrete/general topics which you think can and should be taught in addition/instead of the topics above, while keeping the program interesting as well as important and directly relevant (e.g. group theory is important and interesting, but not relevant enough to justify the time it will take)
- I would have been happy to introduce machine-learning in some form, as it is a really hot topic nowadays. Any ideas as to how machine learning can be presented without tools like measure-concentration theorems are welcome.