# Teaching high school TCS - existing programs

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:

1. Does anyone know of a similar program anywhere?
2. 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)
3. 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.
• It seems that you list automata theory at the end as a sort of after thought. I would advocate on making automata theory the central and unifying theme. It can introduce students to formal mathematical reasoning without any specific mathematical background. It has sharp unconditional theorems that are foundational but relatively straightforward to prove. It can be connected directly to machine learning, although from my experience this is difficult to teach to undergrads in a first theory course, so more caution is warranted with HS. – Artem Kaznatcheev Nov 8 '13 at 10:43
• no havent heard of it done before! "selected" students? does that also mean advanced, presumably? try mining popular science books on TCS or also online blogs [several good ones out there]. Turing machines, quantum computing other key/interesting areas. think this could be pulled off if the math is not heavy & done in more of a conceptual rather than mathematical way. also this site comes up a lot in edu questions: cs unplugged. good luck! – vzn Nov 8 '13 at 16:15
• I wonder if it would be best to devote some of your time to teaching those mathematical skills you mention (e.g. probability)...this would also potentially help you cover more advanced topics, but also help prepare students for future studies in math/cs. – usul Nov 8 '13 at 19:00
• @vzn - yes, these are advanced (dare I say - gifted) students. – Shaull Nov 9 '13 at 15:40
• @vzn That is a very interesting suggestion. Somehow, TCS is not yet part of the popular culture. That is, even curious students are usually unaware of questions such as P v.s NP. But we shall definitely ask current CS students for suggestions, and see what they come up with. My guess is that cryptography would be central. – Shaull Nov 9 '13 at 16:15

Many countries organize summer schools for their IOI teams (consisting of high school students aged roughly 16 IIRC). The one we have in Iran used to have the following courses:

• programming,
• data structure and algorithms,
• combinatorics, and
• graph theory.

I think ACM's Computer Science Teachers Association has a K12 curriculum on its Curriculum Resources page though it is probably way too light for talented teenagers.

I think programming must definitely be part of the curriculum. Python should be a good first language to learn.

You might want to also cover some accessible topics with applications (the joy of building something cool can have a big effect on their interest). I think Andrew Ng's ML course on Coursera should be accessible for talented students (specially for those in countries like yours where there is a more serious K12 math curriculum ).

A nonstandard topic that you might want to consider is combinational game theory, it might be not very interesting with 16 years old (I don't have experience for it) but it works quite well for a bit younger students in my experience.

I personally think the central and connecting theme should be around algorithms, I think it would work better than automata theory as the central theme and arguably the algorithmic perspective (not Turing machines, automata, etc.) is the essence of computer science.

• The programming part is covered by the standard CS program, which they all take. These are additional topics. Do you happen to have a link for such a summer school website? As for focusing on algorithms - while I agree that they are central to CS, I think computability and complexity are equally the essence of computer science. I remember being much more impressed by the fact that there are things we can't solve, rather than by clever algorithms. But both will be covered, probably. – Shaull Nov 9 '13 at 15:41
• in a way, Turing machines are all about algorithms. also ruby is also an excellent option comparable to python. on same subj another excellent option to learn development is javascript because of many reasons eg its proliferation in browsers, lots of public/sample code, wide features, high usage, etc. – vzn Nov 9 '13 at 15:48
• @Shaull, they have a site (Young Scholars Club) but it is in Persian and doesn't contain much about what is covered in the summer school any way. – Kaveh Nov 9 '13 at 21:13
• @vzn, I don't think you have much experience in teaching TCS to high school students and I have explained to you very clearly that I am not interested in your opinions. Stop trolling my answers. – Kaveh Nov 9 '13 at 21:23
• k, plz do not guess at my bkg & will do the same courtesy. the comment is basically in support of your opinions... sounds like a topic for meta =( – vzn Nov 10 '13 at 16:41

Curiously, there is someone who argued that machine learning is uniquely fit among computer science topics to teach to high school students, because supposedly it is one of the few subfields where basic math can get you to understand enough to appreciate the important challenges. I disagree with this claim -- basic algorithms (say for searching, sorting) can be presented as puzzles, and you can very quickly get to very simple to state but fundamental open problems like "can multiplication be done with essentially the same number of operations as addition", or sorting integers in linear time, or factoring (I assume the concept of primes numbers would not be new to the select group of high school students?). On the other hand, a lot of machine learning would be hard to grasp without a good level of experience with statistics and probability theory. Nevertheless, he has some ideas what material to present to students.

In terms of a teaching program, there is a more detailed one by Essinger and Rosen at Drexel.

In addition to these, I would think one can attempt to sketch some of the more high-level ideas of learning theory:

• what is the basic classification problem
• what is a concept class and what does it mean to learn a concept
• why you can't hope to learn concepts from an unrestricted concept class with less than exponential sampling complexity (as an introduction to counting arguments)
• what is VC-dimension

Another suggestion is to introduce circuits and attempt some sketch of Shannon's lower bound. Depends how comfortable students are with counting. If this is too heavy, it might still help to do the argument while having the students take the counting of circuits itself on faith. I think the idea of "most problems require large circuits because there are too many problems and too few small circuits" will be striking. This idea is important and pervasive in complexity.

• Both suggestions are very nice. Thanks! I have a feeling that for high school, just learning what a VC dimension is might take around 3 months, which may be too much. But it is definitely worth considering, especially since thought has already been put to it. – Shaull Nov 9 '13 at 18:25
• I think even just to understand what it means to learn a concept and having some vague idea that you cannot learn arbitrarily complicated things before the sun freezes over will be a win. – Sasho Nikolov Nov 9 '13 at 18:42

heres one promising direction to go on this. AP/NSF recently announced a new high school advanced placement CS program initiative. there will be many advantages to using such a program such as a standardized lesson plan, college accreditation, etc.

it is currently under development and to be ready for 2016. the tentative course syllabus and materials are available online. (for academic experts, there might even be some possibility at this point to influence the future content via "collective intelligence" type collaboration.)

The College Board's Advanced Placement Program said Thursday that it plans to add a new computer-science program to its class offerings, the first new test in seven years. The move reflects a growing interest in training students for careers in the sciences amid a national push to make the U.S. economy more competitive globally.

The new program, AP Computer Science Principles, will concentrate on the "creative aspects" of computing and will be funded partly by a \$5.2 million grant from the National Science Foundation. The federal agency aims to train an additional 10,000 computer-science teachers across the same number of high schools nationwide by 2016 as part of an effort to improve education in the science, technology, engineering and math, or STEM, fields. The College Board will chip in about \$3.5 million for teacher support and equipment.

the existing program is called AP Computer Science A and the new program is called AP Computer Science Principles. the existing class has been around for many years and is also helpful as a model for teachers developing curriculum.

• see also how to get HS students interested in CS cs.se – vzn Nov 8 '13 at 17:55
• Incidentally, Baker Franke and myself submitted a proposal for a BOF (Birds-of-a-Feather) session at SIGCSE '14 to discuss how to make topics in theory accessible for the CS Principles curriculum. – rahulmehta95 Nov 9 '13 at 23:03
• @rahulmehta95 - is there a link to the proposal I can read? – Shaull Nov 10 '13 at 6:43
• Here you go: cs.ucls.uchicago.edu/~rahulmehta/papers/BOF-Theory.pdf. Hope this helps! – rahulmehta95 Nov 10 '13 at 18:42

An idea I've been kicking around recently is how to teach HS students the notion of a reduction between problems. I found this to be one of the most interesting yet most challenging topics when I was introduced to complexity, since it's quite hard (at least initially) to wrap one's head around the fact that a problem like 3-SAT is "just as hard" as Vertex-Cover.

The example I came up with was a reduction between Vertex Cover (VC) and Independent Set (IND-SET), phrased as follows;

"You're the director of a museum, and are tasked with hiring security to guard the hallways. When placed at an intersection of hallways, a guard can keep an eye on ALL hallways adjacent to him. What is the minimum number of guards needed to patrol the entire museum?"

"A little bit later, some children decide to play a game of hide-and-seek in the museum. Their goal is to hide such that no other child can see them. However, the guards don't want them running around in the hallways, so they are relegated to "hiding" in the intersections. What is the largest number of children that can hide in the museum without seeing each other?"

The main goal would be for students to formulate and prove the following theorem that is central to the reduction showing $\text{V}C \leq_{P} \text{IND-SET}$;

Theorem: For $G=(V,E)$, $S \subseteq V$ is an independent set $\iff$ $V \backslash S$ is a vertex cover (where $\backslash$ denotes set difference).

The reason I selected VC & IND-SET is that it's not too hard to see that the problems are closely related; whenever there's an independent set $S$, it induces a vertex cover $V\backslash S$ in $G$.

• While I understand the motivation behind the (very nice) example, I think that in HS I would start with Turing reductions, which are far more intuitive. Also, I would start with a problem where the input has to be really manipulated, and not just a parameter change. For example, I would start with $CLIQUE\le_p IND-SET$, which is more "involved". – Shaull Nov 10 '13 at 18:55
• as far as reductions, the proof that there exists a universal turing machine is one way to go and probably understandable by advanced high schoolers... [note there are many lego TM videos, some even by cs researchers...] also, maybe the tseitin transform? – vzn Nov 11 '13 at 2:16