Teaching high school TCS - existing programs

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

• Advanced Placement Adds New Computer-Science Test WSJ June 2013
• AP computer science, wikipedia
• AP computer science home page
• AP students/College Board computer science
• AP CS Principles
• College board CS principles

Answer 4

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$.