<p>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: </p>

<ul>
<li>programming, </li>
<li>data structure and algorithms, </li>
<li>combinatorics, and </li>
<li>graph theory. </li>
</ul>

<hr>

<p>I think ACM's Computer Science Teachers Association has 
a <a href="http://csta.acm.org/Curriculum/sub/CurrFiles/K-12ModelCurr2ndEd.pdf" rel="nofollow">K12 curriculum</a> on its <a href="http://csta.acm.org/Curriculum/sub/CurrResources.html" rel="nofollow">Curriculum Resources</a> page
though it is probably way too light for talented teenagers. </p>

<hr>

<p>I think programming <em>must</em> definitely be part of the curriculum. 
Python should be a good first language to learn.</p>

<p>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 <a href="https://www.coursera.org/course/ml" rel="nofollow">Andrew Ng's ML course on Coursera</a> 
should be accessible for talented students
(specially for those in countries like yours where 
there is a more serious K12 math curriculum ).</p>

<p>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.</p>

<p>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 <em>the</em> essence of computer science.</p>

CC BY-SA 3.0
2013-11-09T15:41:47.430Z
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
CC BY-SA 3.0
2013-11-09T15:48:43.660Z
in a way, Turing machines are _all about algorithms_. also [ruby](http://en.wikipedia.org/wiki/Ruby_(programming_language)) is also an excellent option comparable to [python](http://en.wikipedia.org/wiki/Python_(programming_language)). on same subj another excellent option to learn development is [javascript](http://en.wikipedia.org/wiki/Javascript) because of many reasons eg its proliferation in browsers, lots of public/sample code, wide features, high usage, etc.
vzn
CC BY-SA 3.0
2013-11-09T21:13:26.190Z
@Shaull, they have a site ([Young Scholars Club](http://www.ysc.ac.ir)) but it is in Persian and doesn't contain much about what is covered in the summer school any way.
Kaveh
CC BY-SA 3.0
2013-11-09T21:23:50.683Z
@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
CC BY-SA 3.0
2013-11-10T16:41:40.410Z
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
CC BY-SA 3.0
2013-11-08T20:37:42.723Z
2013-11-09T21:28:46.397Z
2013-11-09T21:28:46.397Z
Kaveh
<p>Curiously, there is <a href="http://www.lsi.upc.edu/~gavalda/docencia/tml08-revised.pdf">someone</a> who argued that machine learning is <em>uniquely fit</em> 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.</p>

<p>In terms of a teaching program, there is a <a href="http://www.ece.drexel.edu/gailr/papers/essinger_11.pdf">more detailed one</a> by Essinger and Rosen at Drexel.</p>

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

<ul>
<li>what is the basic classification problem</li>
<li>what is a concept class and what does it mean to learn a concept</li>
<li>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)</li>
<li>what is VC-dimension</li>
</ul>

<hr>

<p>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. </p>

CC BY-SA 3.0
2013-11-09T18:25:32.963Z
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
CC BY-SA 3.0
2013-11-09T18:42:12.017Z
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
CC BY-SA 3.0
2013-11-09T18:17:05.670Z
2013-11-09T18:17:05.670Z
Sasho Nikolov
<p>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. </p>

<p>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.)</p>

<blockquote>
  <p>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.</p>
  
  <p>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.</p>
</blockquote>

<p>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.</p>

<ul>
<li><a href="http://online.wsj.com/news/articles/SB10001424127887324049504578543822451290856" rel="nofollow">Advanced Placement Adds New Computer-Science Test</a> WSJ June 2013</li>
<li><a href="http://en.wikipedia.org/wiki/AP_Computer_Science" rel="nofollow">AP computer science</a>, wikipedia</li>
<li><a href="http://apcentral.collegeboard.com/apc/public/courses/teachers_corner/4483.html" rel="nofollow">AP computer science home page</a></li>
<li><a href="https://apstudent.collegeboard.org/apcourse/ap-computer-science-a" rel="nofollow">AP students/College Board computer science</a></li>
<li><a href="http://www.csprinciples.org/" rel="nofollow">AP CS Principles</a></li>
<li><a href="http://www.collegeboard.com/html/computerscience/" rel="nofollow">College board CS principles</a></li>
</ul>

CC BY-SA 3.0
2013-11-08T17:55:14.380Z
see also [how to get HS students interested in CS](http://cs.stackexchange.com/questions/12857/what-should-i-do-with-a-bunch-of-16-17-year-olds-to-get-them-interested-in-compu) cs.se
vzn
CC BY-SA 3.0
2013-11-09T23:03:24.190Z
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
CC BY-SA 3.0
2013-11-10T06:43:39.527Z
@rahulmehta95 - is there a link to the proposal I can read?
Shaull
CC BY-SA 3.0
2013-11-10T18:42:51.257Z
Here you go: http://cs.ucls.uchicago.edu/~rahulmehta/papers/BOF-Theory.pdf. Hope this helps!
rahulmehta95
CC BY-SA 3.0
2013-11-08T17:10:48.503Z
2013-11-08T17:10:48.503Z
vzn
<p>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.</p>

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

<p>"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?"</p>

<p>"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?"</p>

<p>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}$;</p>

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

<p>The reason I selected VC &amp; IND-SET is that it's not <em>too</em> 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$.</p>

CC BY-SA 3.0
2013-11-10T18:55:19.563Z
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
CC BY-SA 3.0
2013-11-11T02:16:51.063Z
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](http://en.wikipedia.org/wiki/Tseitin-Transformation)?
vzn
CC BY-SA 3.0
2013-11-10T18:51:01.263Z
2013-11-10T18:51:01.263Z
rahulmehta95
<p>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.</p>

<p>First, does anyone know of high schools where a TCS program has been taught successfully (or unsuccessfully)?</p>

<p>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:</p>

<ul>
<li>Asymptotic analysis</li>
<li>Basic data structures and algorithms (lists, arrays)</li>
<li>Graph algorithms, also as a demonstration of greedy algorithms v.s. dynamic programming.</li>
<li>Other algorithms (e.g. probabilistic)</li>
<li>Computability - the concept of a TM, reduction, decidability.</li>
<li>Complexity - NP, P, perhaps PSPACE and NL. Completeness.</li>
<li>Automata theory</li>
</ul>

<p>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).</p>

<p>To sum up, and to give precise questions:</p>

<ol>
<li>Does anyone know of a similar program anywhere?</li>
<li>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)</li>
<li>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.</li>
</ol>

CC BY-SA 3.0
2013-11-08T10:43:42.053Z
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](http://egtheory.wordpress.com/2013/09/24/learning-dfas/), 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
CC BY-SA 3.0
2013-11-08T11:07:22.393Z
@ArtemKaznatcheev - The list is not chronological, and automata (which just happen to be my research field) are definitely a central part. Probably even before defining TMs. I fear that Angluin's work is a bit too difficult to fit in such a syllabus, but it is definitely an idea to consider. Thanks! If you turn the comment to an answer, I'll vote up.
Shaull
CC BY-SA 3.0
2013-11-08T16:15:24.637Z
no havent heard of it done before! "selected" students? does that also mean advanced, presumably? try mining [popular science books on TCS](http://cstheory.stackexchange.com/questions/18968/what-are-the-popular-science-books-that-inspire-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](http://csunplugged.org/). good luck!
vzn
CC BY-SA 3.0
2013-11-08T19:00:55.053Z
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
CC BY-SA 3.0
2013-11-09T02:09:56.920Z
Machine learning doesn't need Chernoff bounds. It needs Matlab (or equivalent). Perhaps you're confusing it with PAC learning, which isn't as hot a topic?
Yuval Filmus
CC BY-SA 3.0
2013-11-09T15:40:14.660Z
@vzn - yes, these are advanced (dare I say - gifted) students.
Shaull
CC BY-SA 3.0
2013-11-09T15:41:28.583Z
@usul of course some of the time would have to be spent on mathematical skills, but a very clear intention is to try and get the math through the cs topics, rather than taking the university approach and laying the mathematical basis. This is because these students lack the "mathematical maturity" to handle heavy math.
Shaull
CC BY-SA 3.0
2013-11-09T15:51:05.843Z
another suggestion/idea— after some introduction & instruction to a broad array of modern topics ask the _kids_ what they would most like to learn about, allowing them to originate stuff found in their own experience, seen in media/news/movies, etc. as for complexity theory a neat/compelling way/angle to introduce P vs NP is via the [$1M claymath prize](http://en.wikipedia.org/wiki/Millennium_Prize_Problems).
vzn
CC BY-SA 3.0
2013-11-09T16:13:58.817Z
@Shaull I see ... there is probably a good balance to be struck. It would be different if it were just a single semester, but I was hoping that over three years you can possibly help *develop* some mathematical maturity. Perhaps it is possible to coordinate with the math instructors?
usul
CC BY-SA 3.0
2013-11-09T16:15:42.900Z
@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
CC BY-SA 3.0
2013-11-09T16:18:22.567Z
@usul - coordinating with math teachers would be great, of course. However, here we face the brick wall of the ministry of education, and the standardized national tests. These are very strict, and very physics oriented (as most high school math programs are). The math curriculum is stressed enough as it is (this I know from experience, as I am currently a math teacher), so there is very small chance of making this change, at least not in the near future. I do feel, however, that such a change will come eventually.
Shaull
CC BY-SA 3.0
2013-11-09T17:11:58.817Z
"somehow TCS is not yet part of the popular culture". disagree somewhat, think its actually quite prevalent/pervasive knowing where to look but there is indeed a lack of realization about how it *does* show up. asked a question about this awhile back on cs.se but it got closed by the mods. but that does lead to new idea; [cs in the movies as edu tool](http://cs.stackexchange.com/questions/16853/computer-science-in-the-movies-as-an-educational-angle)
vzn
<teaching>
Teaching high school TCS - existing programs
Shaull
# Teaching high school TCS - existing programs

(Asked by: username_0 on 2013-11-08)

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.

**Tags:** teaching

> **Comments:**
> **username_1**: 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](http://egtheory.wordpress.com/2013/09/24/learning-dfas/), although from my experience this is difficult to teach to undergrads in a first theory course, so more caution is warranted with HS.  
> **username_0**: @ArtemKaznatcheev - The list is not chronological, and automata (which just happen to be my research field) are definitely a central part. Probably even before defining TMs. I fear that Angluin's work is a bit too difficult to fit in such a syllabus, but it is definitely an idea to consider. Thanks! If you turn the comment to an answer, I'll vote up.  
> **username_2**: no havent heard of it done before! "selected" students? does that also mean advanced, presumably? try mining [popular science books on TCS](http://cstheory.stackexchange.com/questions/18968/what-are-the-popular-science-books-that-inspire-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](http://csunplugged.org/). good luck!  
> **username_3**: 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.  
> **username_4**: Machine learning doesn't need Chernoff bounds. It needs Matlab (or equivalent). Perhaps you're confusing it with PAC learning, which isn't as hot a topic?  
> **username_0**: @username_2 - yes, these are advanced (dare I say - gifted) students.  
> **username_0**: @username_3 of course some of the time would have to be spent on mathematical skills, but a very clear intention is to try and get the math through the cs topics, rather than taking the university approach and laying the mathematical basis. This is because these students lack the "mathematical maturity" to handle heavy math.  
> **username_2**: another suggestion/idea— after some introduction & instruction to a broad array of modern topics ask the _kids_ what they would most like to learn about, allowing them to originate stuff found in their own experience, seen in media/news/movies, etc. as for complexity theory a neat/compelling way/angle to introduce P vs NP is via the [$1M claymath prize](http://en.wikipedia.org/wiki/Millennium_Prize_Problems).  
> **username_3**: @username_0 I see ... there is probably a good balance to be struck. It would be different if it were just a single semester, but I was hoping that over three years you can possibly help *develop* some mathematical maturity. Perhaps it is possible to coordinate with the math instructors?  
> **username_0**: @username_2 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.  
> **username_0**: @username_3 - coordinating with math teachers would be great, of course. However, here we face the brick wall of the ministry of education, and the standardized national tests. These are very strict, and very physics oriented (as most high school math programs are). The math curriculum is stressed enough as it is (this I know from experience, as I am currently a math teacher), so there is very small chance of making this change, at least not in the near future. I do feel, however, that such a change will come eventually.  
> **username_2**: "somehow TCS is not yet part of the popular culture". disagree somewhat, think its actually quite prevalent/pervasive knowing where to look but there is indeed a lack of realization about how it *does* show up. asked a question about this awhile back on cs.se but it got closed by the mods. but that does lead to new idea; [cs in the movies as edu tool](http://cs.stackexchange.com/questions/16853/computer-science-in-the-movies-as-an-educational-angle)  

---

## 4 answers

### Answer by username_5 on 2013-11-08. Score: 8

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](http://csta.acm.org/Curriculum/sub/CurrFiles/K-12ModelCurr2ndEd.pdf) on its [Curriculum Resources](http://csta.acm.org/Curriculum/sub/CurrResources.html) 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](https://www.coursera.org/course/ml)
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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: in a way, Turing machines are _all about algorithms_. also [ruby](http://en.wikipedia.org/wiki/Ruby_(programming_language)) is also an excellent option comparable to [python](http://en.wikipedia.org/wiki/Python_(programming_language)). on same subj another excellent option to learn development is [javascript](http://en.wikipedia.org/wiki/Javascript) because of many reasons eg its proliferation in browsers, lots of public/sample code, wide features, high usage, etc.  
> **username_5**: @username_0, they have a site ([Young Scholars Club](http://www.ysc.ac.ir)) but it is in Persian and doesn't contain much about what is covered in the summer school any way.  
> **username_5**: @username_2, 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.  
> **username_2**: 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 =(  

---

### Answer by username_6 on 2013-11-09. Score: 5

Curiously, there is [someone](http://www.lsi.upc.edu/~gavalda/docencia/tml08-revised.pdf) 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](http://www.ece.drexel.edu/gailr/papers/essinger_11.pdf) 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.

> **Comments:**
> **username_0**: 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.  
> **username_6**: 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.  

---

### Answer by username_2 on 2013-11-08. Score: 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](http://online.wsj.com/news/articles/SB10001424127887324049504578543822451290856) WSJ June 2013
* [AP computer science](http://en.wikipedia.org/wiki/AP_Computer_Science), wikipedia
* [AP computer science home page](http://apcentral.collegeboard.com/apc/public/courses/teachers_corner/4483.html)
* [AP students/College Board computer science](https://apstudent.collegeboard.org/apcourse/ap-computer-science-a)
* [AP CS Principles](http://www.csprinciples.org/)
* [College board CS principles](http://www.collegeboard.com/html/computerscience/)

> **Comments:**
> **username_2**: see also [how to get HS students interested in CS](http://cs.stackexchange.com/questions/12857/what-should-i-do-with-a-bunch-of-16-17-year-olds-to-get-them-interested-in-compu) cs.se  
> **username_7**: 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.  
> **username_0**: @username_7 - is there a link to the proposal I can read?  
> **username_7**: Here you go: http://cs.ucls.uchicago.edu/~rahulmehta/papers/BOF-Theory.pdf. Hope this helps!  

---

### Answer by username_7 on 2013-11-10. Score: 2

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

> **Comments:**
> **username_0**: 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".  
> **username_2**: 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](http://en.wikipedia.org/wiki/Tseitin-Transformation)?  

---

