<p>A good source for education purposes in general is <a href="http://csunplugged.org/">CS unplugged</a>, which has lots of neat CS ideas translated into high-school and middle-school <a href="http://csunplugged.org/activities">activities</a>.</p>

CC BY-SA 2.5
2010-10-24T13:01:43.993Z
That is a very good link thanks. The most remarkable thing about it is that it is aimed at middle school children.  I doubt there is a single middle school in the UK that teaches anything like it, sadly.
Simd
CC BY-SA 2.5
2010-10-25T03:57:13.130Z
The Teacher's Edition book looks more suitable for primary-school and middle-school children, rather than for high-school students.
Alessandro Cosentino
CC BY-SA 2.5
2010-10-23T05:54:45.423Z
2010-10-23T05:54:45.423Z
Noam
<p>One of the most appealing aspects TCS is how it uses abstract mathematical ideas for day-to-day practical applications.  A presentation can focus on the abstract ideas that lie one step behind what they see daily on the Internet:  Shortest paths becomes exciting once they are put in the context of friends-of-friends on Facebook.  More graph algorithms can ride on Pagerank; Amazon recommendations raise the challenge of machine learning; and buying-stuff on the Internet is certainly a good lead for the public-key crypto.  </p>

CC BY-SA 2.5
2010-10-23T10:24:28.067Z
Also, any StarCraft player is aware of the importance of a good shortest path algorithm. And I guess that high school students are still playing videogames (do they ?).
Sylvain Peyronnet
CC BY-SA 2.5
2010-10-24T13:59:33.503Z
They're definitely playing video games.
Daniel Apon
CC BY-SA 2.5
2010-10-23T05:50:31.403Z
2010-10-23T05:50:31.403Z
Noam
<p>I've used two talks quite successfully with both high school students and entering freshmen. </p>

<ol>
<li><p>Origami. I lead off with the 5-point star problem (this works well in american contexts, because of the connection to the american flag) and let students try to figure out how to make a five-point star with folding + 1 cut. I talk about the "resource" (cutting) and how algorithm design is about working with limited resources. Then I talk about other origami questions and applications in the real world (heart valves, NASA telescopes, crumple zones in cars). </p></li>
<li><p>Sorting pancakes: there's a beautiful connection between sorting pancakes and genome rearrangement, and I actually made stacks of pancakes from foam for students to play with. Works great, and lets me talk about algorithms, gene sequencing, Bill Gates (!), and other fun things. </p></li>
</ol>

CC BY-SA 2.5
2010-10-23T07:10:03.907Z
2010-10-23T07:10:03.907Z
Suresh Venkat
<p>I think almost any topic in computer science can be used for giving an interesting talk, but some are better suited, the more important part is the presentation.</p>
<h3>Fun Side of Computer Science</h3>
<p>I have used various games from Combinatorial Games Theory, mainly from Richard Guy's &quot;Fair Games&quot; and Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy's &quot;Winning Ways for your Mathematical Plays&quot; (<a href="http://en.wikipedia.org/wiki/Winning_Ways_for_your_Mathematical_Plays" rel="nofollow noreferrer">wiki</a>).</p>
<p>They are <strong>fun</strong>, and you can play them in the class with them and let them find the right way to play it, give some hints so at the end <em>they</em> find the way to win the game. These games are probably more suitable for younger students.</p>
<p>There are other fun topics in Computer Science where you can pick a problem which is more suitable for your audience and use it to engage them.</p>
<h3>Philosophical Side of Computer Science</h3>
<p>There many topics in theoretical computer science which are related to philosophy and the <strong>big questions</strong>. From Gödel's incompleteness theorem to zero-knowledge proofs, security, privacy, algorithmic game theory, P vs NP, machine learning, ... I would not go into details, just demonstrate that the problems are interesting, they are more than just computer science, they are related to big questions. (Take a look at Scott Aaronson's <a href="http://www.scottaaronson.com/democritus/" rel="nofollow noreferrer">Quantum Computing Since Democritus</a> and <a href="http://stellar.mit.edu/S/course/6/sp08/6.080/materials.html" rel="nofollow noreferrer">Great Ideas In Theoretical Computer Science</a> lectures). Don't make them feel like the topic is dead (i.e. all questions are answered), make them feel that the area is alive, there has been progress but there are still big challenges ahead, and it is a journey to an undiscovered land.</p>
<h3>Technological Side of Computer Science</h3>
<p>Talk about the computer science behind technologies. There are so many topic that one can choose here, familiar <strong>technologies</strong> from video-games to Google search, machine translation, vision, ... technologies that everyone uses each day, or even unfamiliar ones. Talk about in progress and next generation technologies, about the impact they have had on our lives, and how they have improved it. Talk about research going on in big famous companies (like Google, Microsoft, Apple, IBM, ...) and products they develop. Talk about <strong>big problems</strong> of our time and what effect computer science has on them.</p>
<h3>Mathematical Side of Computer Science</h3>
<p>This is good for students who are already interested in mathematics, those interested in the <strong>pure</strong> and <strong>exact</strong> side, but without combining it with other theme mentioned above it won't be as effective to other students. I would go with a big question and at some point mention start talking about mathematical problems involved.</p>
<h3>Interdisciplinary Side of Computer Science</h3>
<p>Computer Science is probably one of the most <strong>interdisciplinary</strong> subjects, there are some connection with almost any other subject, humanistic (sociology, linguistics, economics, philosophy, ...), natural sciences (mathematics, physics, ...), biology, medical sciences, art, engineering (electronics, mechanics, ...), ... anything! <em>Whatever topic you are interested in, there is something in computer science that is related to it!</em> As Scott said, <a href="http://scottaaronson.com/blog/?p=442" rel="nofollow noreferrer">Every Other Major Sucks By Comparison</a> :).</p>
<h3>All of Them</h3>
<p>You can also try to mention all of the themes I have mentioned above. I haven't tried this, and I am not sure how effective it would be. You have to transfer the feeling and make the point, and it takes sometime. One other options is to mention all of them briefly at the start (or the end) and then go on with one of them, and tell them that they can contact you to get more informations about the other ones if they are interested.</p>
<h3>some comments</h3>
<p>Whatever you are going to talk about, you should <strong>be enthusiastic</strong> about it. It is going to be much more difficult to interest them in a topic which is not really interesting to yourself. Tell them about your own reasons for selecting computer science. And <strong>don't be boring</strong>.</p>

CC BY-SA 2.5
2010-10-24T06:15:21.070Z
2010-10-24T06:21:43.637Z
2020-06-17T09:38:08.363Z
Kaveh
<p><a href="http://rads.stackoverflow.com/amzn/click/0716782715" rel="nofollow">The New Turing Omnibus</a> by A. K. Dewey has 66 so-called excursions in computer science.
It covers topics such as analysis of algorithms, AI, complexity theory, theory of computation, cryptography, computer graphics and so forth. Every topic is written in a rather condensed form, capturing some landmark result in computer science. This book could provide some inspiration.</p>

<p>Another possibility is to allow students to get their hands dirty via something like <a href="http://code.google.com/opensource/gci/2010-11/index.html" rel="nofollow">Google's Code-in</a> program. It's a bit like <a href="http://code.google.com/soc/" rel="nofollow">Google's Summer of Code</a>, but, you know, for kids. Perhaps showing some of the amazing coding projects students can be involved in is one possible way of piquing interest.</p>

CC BY-SA 2.5
2010-10-22T20:07:04.043Z
Of course, the book is from 1993 (I think) and thus a bit old school.
Dave Clarke
CC BY-SA 2.5
2010-10-22T20:33:34.833Z
Yes there is a problem with trying to excite them about the future if one is referring to a book written before they were born :)
Simd
CC BY-SA 2.5
2010-10-22T19:29:26.540Z
2010-10-22T20:54:50.697Z
2010-10-22T20:54:50.697Z
Dave Clarke
<p>Cryptography is always something that captures the mind of younger (and I personally hope older) individuals. I had friends who wanted to be nurses' assistants, hockey players, businessmen and politicians and friends (who despite their higher goals) took jobs as grocery baggers and cart pushers, construction workers and kennel assistants - all of whom invented and broke each others' (admittedly naive and simple) codes. In particular, the existence of public key cryptography is usually pretty easy to explain if one takes the route of RSA. One might also list some of the important results without proofs or constructions - Zero-Knowledge proofs and Homomorphic Encryption are bound to juice the geek factor for what it's worth.</p>

<p>Forward Error Correction and Error Detection codes are also very cool and if done right can be taught to a curious audience. To make them easier to digest, you could mention the "universality" of the index of coincidence - that all our spoken language and writing have small redundancies and exaggerations that help us to communicate in the noisy channel of a room containing shuffling bags, feet and humming air conditioners.</p>

<p>Finally, I also would suggest doing a simple introduction to complexity theory - something along the lines of my answer to <a href="https://cstheory.stackexchange.com/questions/1471/dinner-table-description-of-theoretical-computer-science/1483#1483">A Dinner-table description of Theoretical Computer Science</a>.</p>

CC BY-SA 2.5
2010-10-22T19:55:38.017Z
2010-10-22T19:55:38.017Z
2017-04-13T12:32:28.080Z
Ross Snider
<p>In my opinion, to be sexy to high school students you need to be some kind of magician. That's why I think that randomized algorithms are very good as a student attractor. For instance property testing is really something intriguing, and also something that can be explained (not the technicalities, but the idea) to anyone. </p>

<p>PCP is also magic, but I guess that this is out of reach...</p>

CC BY-SA 2.5
2010-10-23T21:01:30.927Z
I had once given a talk about PCP to talented high school students, of course without proving it, but showing its applications to hardness of approximation and giving the general 'feel' of the theorem. I think they liked it, so it isn't that much out of reach (but they had listened to some talks about approximation algorithms before, without this I think they wouldn't grab the motivation of the theorem).
Karolina Sołtys
CC BY-SA 2.5
2010-10-22T21:28:14.563Z
2010-10-22T21:28:14.563Z
Sylvain Peyronnet
<p>Here is a very nice article on coding theory aimed at high school students by Michael Mitzenmacher:</p>

<p><a href="http://www.eecs.harvard.edu/~michaelm/FUTUREOFCS/codes-mitzenmacher.pdf" rel="nofollow">http://www.eecs.harvard.edu/~michaelm/FUTUREOFCS/codes-mitzenmacher.pdf</a></p>

CC BY-SA 2.5
2010-10-27T19:54:25.753Z
this is an excellent survey
Suresh Venkat
CC BY-SA 2.5
2010-10-27T21:44:59.027Z
This seems to part of a book that's a work-in-progress. Michael Mitzenmacher's blog post (http://mybiasedcoin.blogspot.com/2008/04/theorycs-book.html) has a link to that, which also has a very nice expository chapter (http://www.cs.princeton.edu/~chazelle/pubs/algorithm.html) on algorithms by Bernard Chazelle. That chapter isn't mathematics per se, but it is rich in mathematical ideas.
Cong Han
CC BY-SA 2.5
2010-10-27T19:19:39.390Z
2010-10-27T19:19:39.390Z
Jagadish
<p>My answer is not directly connected with TCS, but it can show that math can be beautiful and useful.   </p>

<p>You could make a speech about how to get reliable data about how many students were cheating on the exam. If you asked them directly then You wouldn't get reliable data. The idea of how to get reliable data is very simple. First You tell every student to think about some integer number, then You say:<br>
- If it was odd number write down whether You like green color or not. You can choose any other simple question, but You have to know, from some other survey, what percentage of people answer yes on this question.<br>
- If it was even number write down whether You were cheating or not.  </p>

<p>About 50% of students are going to answer on first question, and the other 50% are going to answer on second question. Now it is very easy to estimate how many students were cheating.
Example: If 40% of answers were yes, and You know that 30% of people like green color then You know that about 50% of students were cheating.</p>

CC BY-SA 2.5
2010-10-24T10:26:56.330Z
2010-10-27T19:32:51.237Z
2010-10-27T19:32:51.237Z
Tomek Tarczynski
<p>According to me, "computer science" is the "science of all sciences" :)</p>

<p>What is "science"?  We get data from nature, and we try to construct a model that explains the data.  Also, we assume implicitly that nature is not arbitrary.  The laws of nature must have a concise expression, the data must satisfy some symmetries, etc.</p>

<p>But this is exactly a learning problem!  The data is generated by some process that is promised to be of "low complexity", and our task is to reconstruct a description of the process.  </p>

<p>Our understanding of such problems is at such a primitive level that it's your duty to work on them! :)  Even our understanding of the seemingly simpler problem of whether the output of a black-box process is equivalent to some <em>fixed</em> function is far from complete.  For example, suppose that we are promised that the black-box is evaluating a function that can be computed by a small-depth arithmetic circuit (this is easy to explain to high-schoolers), and we want to find out whether the box is computing the zero function.  We don't know if this can be done in the lifetime of the universe for functions on reasonable sized domains!</p>

<p>Cue to start talking about arithmetic complexity theory, the chasm at depth 4, the role of randomness in computation, what's known if we reduce # of multiplication gates, etc. etc. ...</p>

CC BY-SA 2.5
2010-11-09T00:27:28.033Z
2010-11-09T00:48:49.630Z
2010-11-09T00:48:49.630Z
arnab
<p>I think this is closely related to <a href="https://cstheory.stackexchange.com/questions/1471/dinner-table-description-of-theoretical-computer-science">Dinner-table description of theoretical computer science?</a></p>

<p>As I posted there I feel that algorithmics relate the best to every-day problems and can therefore motivate TCS very well. ("How long one google search would take if they would search in the same way you look up telephone numbers")</p>

CC BY-SA 2.5
2010-10-24T12:55:05.677Z
Hello Raphael!  The main difference I feel is that these are all mathematically inclined students making an active choice about what to do with their future. The problem we have had in recruitment, which may be peculiar to the UK, is that high school teaches them that CS is neither for great intellectuals nor for people who want to change the world.  I have 20 minutes to redress this misconception :)
Simd
CC BY-SA 2.5
2010-10-24T14:59:47.073Z
That is right (also in Germany) and there might be some differences in attitude but the amount of CS specific knowledge present might be about the same as for the dinner table folks. I would agree that you have wrap the package differently for the other audience but I would choose the same content.
Raphael
CC BY-SA 2.5
2010-10-24T12:51:38.353Z
2010-10-24T12:51:38.353Z
2017-04-13T12:32:28.080Z
Raphael
<p>In the Algorithms in the Field workshop a month ago in DIMACS, Graham Cormode was arguing in favor of teaching sketching techniques from streaming algorithms to undergraduates. Moses Charikar said that they do teach them in Princeton, I think @Suresh Venkat also mentioned he teaches things like the Misra-Gries algorithm for heavy hitters. I think some basic streaming results would be great for high school students too: they rely on basic but important math tricks, the problem formulations are like puzzles, and the solutions feel like magic, and magic is a great way to inspire high school students. You can make sure to emphasize the dramatic difference between the scale of the problem and the amount of resources you can use. A silly example: suppose that you can ask every person entering or leaving JFK airport their zipcode. Can you keep track how many different zipcodes have been represented in JFK during month, only using a notepad?</p>

CC BY-SA 3.0
2011-06-17T17:52:31.443Z
yup. this is a good example
Suresh Venkat
CC BY-SA 3.0
2011-06-15T21:44:19.207Z
2011-06-15T21:44:19.207Z
Sasho Nikolov
<p>There is a neat way to introduce zero-knowledge proofs to students, which I think is originally due to Oded Goldreich (please correct me if I'm wrong). </p>

<p>You have a red ball and a green ball, which poor colorblind Charlie believes are the same color. You want to convince Charlie that you can tell the difference between the red ball and green ball, and you want to do this in a way that Charlie <em>does not</em> learn which is red and which is green. (You want to prove something is true, in such a way that no one else can turn around and claim a proof of that something as their own.) How can you do this? Or is it impossible? </p>

<p>One protocol is the following. Charlie puts a ball in each hand, then chooses to either switch the two balls behind him, or not. Then he presents the two balls again. If you can always detect whether he switched the two balls or not, then Charlie is increasingly convinced that you <em>can</em> tell the difference between them. If Charlie does this shuffle at random and you really can't tell the difference between the colors, then you will only guess correctly with probability $1/2$. After $k$ trials, Charlie should be convinced that you can tell the difference with probability at least $1-1/2^k$.</p>

<p>Now while Charlie becomes increasingly convinced that you can tell the difference, he frustratingly never learns which ball is red and which one is green.</p>

CC BY-SA 2.5
2010-12-15T20:16:20.277Z
While Goldreich has contributed a lot to this field, ZK proofs are originally due to [Goldwasser, Micali, and Rackoff](http://portal.acm.org/citation.cfm?id=22178). PS: The color-blind-convincing protocol is actually due to Goldreich (see [http://www.wisdom.weizmann.ac.il/~oded/poster03.html](http://www.wisdom.weizmann.ac.il/~oded/poster03.html)).
Sadeq Dousti
CC BY-SA 3.0
2011-06-15T21:29:25.123Z
@Sadeq: I am sure Ryan meant that ZKP for ball color with a color blind prover is due to Goldreich :)
Sasho Nikolov
CC BY-SA 2.5
2010-10-23T05:57:04.467Z
Presenting ZK proofs is a very good choice. Another example which I think will be understandable to students is graph coloring.
Kaveh
CC BY-SA 2.5
2010-10-23T07:07:28.273Z
There's a cool ZK sudoku demo from Moni Naor's page.
Suresh Venkat
CC BY-SA 2.5
2010-10-23T05:37:14.440Z
2010-10-23T05:37:14.440Z
Ryan Williams
<p>I am often asked by my department to give talks to final year high school pupils about the more mathematical elements of computer science. I do my best to pick topics from TCS which might inspire their interest (which mostly involves something to do with the Halting problem) but would love hear other people's ideas/successes/failures.  </p>

<p>The remit is that these are pupils who are considering applying for a CS undergraduate degree at a decent university but may be more attracted by maths or another one of the sciences.  I find that the usual topics of shortest path algorithms or faster sorting methods don't really work any more to pique their interest.  </p>

CC BY-SA 3.0
2011-06-15T16:39:15.943Z
Shortest path algorithms were covered in A-level maths (the Discrete Maths 1 module) back at the end of the 90s, probably still are. It would be worth checking out what they've covered in maths classes (e.g. do they do that module? Just those doing Further Maths? Just those who can be bothered to self-study it) because you may be able to use it as a tie-in to the difference between CS at university and the computing A-level.
Peter Taylor
CC BY-SA 2.5
2010-10-22T19:43:43.673Z
I'm thinking this should be CW ?
Suresh Venkat
CC BY-SA 2.5
2010-10-22T21:32:29.573Z
Is this really TCS research level question?!
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-22T22:32:40.300Z
@turkistany: Yes.  Selling the importance of research is an essential part of doing that research.  It is also a part where many theoreticians are weak.  To paraphrase Feynman, we don't really understand TCS unless we can explain in to bright high school students.
Aaron Sterling
CC BY-SA 2.5
2010-10-23T17:41:12.637Z
@turkistany: Yes, yes, a thousand times yes.
Jeffε
CC BY-SA 2.5
2010-10-23T19:26:06.677Z
@JeffE, Ok, Ok,..., infinite number of times OK. I get now :)
Mohammad Al-Turkistany
<soft-question><teaching>
Inspirational talk for final year high school pupils
Simd
# Inspirational talk for final year high school pupils

(Asked by: username_0 on 2010-10-22)

I am often asked by my department to give talks to final year high school pupils about the more mathematical elements of computer science. I do my best to pick topics from TCS which might inspire their interest (which mostly involves something to do with the Halting problem) but would love hear other people's ideas/successes/failures.

The remit is that these are pupils who are considering applying for a CS undergraduate degree at a decent university but may be more attracted by maths or another one of the sciences. I find that the usual topics of shortest path algorithms or faster sorting methods don't really work any more to pique their interest.

**Tags:** soft-question, teaching

> **Comments:**
> **username_2**: I'm thinking this should be CW ?  
> **username_3**: Is this really TCS research level question?!  
> **username_4**: @turkistany: Yes.  Selling the importance of research is an essential part of doing that research.  It is also a part where many theoreticians are weak.  To paraphrase Feynman, we don't really understand TCS unless we can explain in to bright high school students.  
> **username_5**: @turkistany: Yes, yes, a thousand times yes.  
> **username_3**: @JeffE, Ok, Ok,..., infinite number of times OK. I get now :)  
> **username_1**: Shortest path algorithms were covered in A-level maths (the Discrete Maths 1 module) back at the end of the 90s, probably still are. It would be worth checking out what they've covered in maths classes (e.g. do they do that module? Just those doing Further Maths? Just those who can be bothered to self-study it) because you may be able to use it as a tie-in to the difference between CS at university and the computing A-level.  

---

## 13 answers

### Answer by username_20 on 2010-10-23. Score: 41 | Accepted answer

There is a neat way to introduce zero-knowledge proofs to students, which I think is originally due to Oded Goldreich (please correct me if I'm wrong).

You have a red ball and a green ball, which poor colorblind Charlie believes are the same color. You want to convince Charlie that you can tell the difference between the red ball and green ball, and you want to do this in a way that Charlie *does not* learn which is red and which is green. (You want to prove something is true, in such a way that no one else can turn around and claim a proof of that something as their own.) How can you do this? Or is it impossible?

One protocol is the following. Charlie puts a ball in each hand, then chooses to either switch the two balls behind him, or not. Then he presents the two balls again. If you can always detect whether he switched the two balls or not, then Charlie is increasingly convinced that you *can* tell the difference between them. If Charlie does this shuffle at random and you really can't tell the difference between the colors, then you will only guess correctly with probability $1/2$. After $k$ trials, Charlie should be convinced that you can tell the difference with probability at least $1-1/2^k$.

Now while Charlie becomes increasingly convinced that you can tell the difference, he frustratingly never learns which ball is red and which one is green.

> **Comments:**
> **username_10**: Presenting ZK proofs is a very good choice. Another example which I think will be understandable to students is graph coloring.  
> **username_2**: There's a cool ZK sudoku demo from Moni Naor's page.  
> **username_21**: While Goldreich has contributed a lot to this field, ZK proofs are originally due to [Goldwasser, Micali, and Rackoff](http://portal.acm.org/citation.cfm?id=22178). PS: The color-blind-convincing protocol is actually due to Goldreich (see [http://www.wisdom.weizmann.ac.il/~oded/poster03.html](http://www.wisdom.weizmann.ac.il/~oded/poster03.html)).  
> **username_19**: @Sadeq: I am sure Ryan meant that ZKP for ball color with a color blind prover is due to Goldreich :)  

---

### Answer by username_6 on 2010-10-23. Score: 23

A good source for education purposes in general is [CS unplugged](http://csunplugged.org/), which has lots of neat CS ideas translated into high-school and middle-school [activities](http://csunplugged.org/activities).

> **Comments:**
> **username_0**: That is a very good link thanks. The most remarkable thing about it is that it is aimed at middle school children.  I doubt there is a single middle school in the UK that teaches anything like it, sadly.  
> **username_7**: The Teacher's Edition book looks more suitable for primary-school and middle-school children, rather than for high-school students.  

---

### Answer by username_6 on 2010-10-23. Score: 16

One of the most appealing aspects TCS is how it uses abstract mathematical ideas for day-to-day practical applications. A presentation can focus on the abstract ideas that lie one step behind what they see daily on the Internet: Shortest paths becomes exciting once they are put in the context of friends-of-friends on Facebook. More graph algorithms can ride on Pagerank; Amazon recommendations raise the challenge of machine learning; and buying-stuff on the Internet is certainly a good lead for the public-key crypto.

> **Comments:**
> **username_8**: Also, any StarCraft player is aware of the importance of a good shortest path algorithm. And I guess that high school students are still playing videogames (do they ?).  
> **username_9**: They're definitely playing video games.  

---

### Answer by username_10 on 2010-10-24. Score: 15

I think almost any topic in computer science can be used for giving an interesting talk, but some are better suited, the more important part is the presentation.

### Fun Side of Computer Science

I have used various games from Combinatorial Games Theory, mainly from Richard Guy's "Fair Games" and Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy's "Winning Ways for your Mathematical Plays" ([wiki](http://en.wikipedia.org/wiki/Winning_Ways_for_your_Mathematical_Plays)).

They are **fun**, and you can play them in the class with them and let them find the right way to play it, give some hints so at the end *they* find the way to win the game. These games are probably more suitable for younger students.

There are other fun topics in Computer Science where you can pick a problem which is more suitable for your audience and use it to engage them.

### Philosophical Side of Computer Science

There many topics in theoretical computer science which are related to philosophy and the **big questions**. From Gödel's incompleteness theorem to zero-knowledge proofs, security, privacy, algorithmic game theory, P vs NP, machine learning, ... I would not go into details, just demonstrate that the problems are interesting, they are more than just computer science, they are related to big questions. (Take a look at Scott Aaronson's [Quantum Computing Since Democritus](http://www.scottaaronson.com/democritus/) and [Great Ideas In Theoretical Computer Science](http://stellar.mit.edu/S/course/6/sp08/6.080/materials.html) lectures). Don't make them feel like the topic is dead (i.e. all questions are answered), make them feel that the area is alive, there has been progress but there are still big challenges ahead, and it is a journey to an undiscovered land.

### Technological Side of Computer Science

Talk about the computer science behind technologies. There are so many topic that one can choose here, familiar **technologies** from video-games to Google search, machine translation, vision, ... technologies that everyone uses each day, or even unfamiliar ones. Talk about in progress and next generation technologies, about the impact they have had on our lives, and how they have improved it. Talk about research going on in big famous companies (like Google, Microsoft, Apple, IBM, ...) and products they develop. Talk about **big problems** of our time and what effect computer science has on them.

### Mathematical Side of Computer Science

This is good for students who are already interested in mathematics, those interested in the **pure** and **exact** side, but without combining it with other theme mentioned above it won't be as effective to other students. I would go with a big question and at some point mention start talking about mathematical problems involved.

### Interdisciplinary Side of Computer Science

Computer Science is probably one of the most **interdisciplinary** subjects, there are some connection with almost any other subject, humanistic (sociology, linguistics, economics, philosophy, ...), natural sciences (mathematics, physics, ...), biology, medical sciences, art, engineering (electronics, mechanics, ...), ... anything! *Whatever topic you are interested in, there is something in computer science that is related to it!* As Scott said, [Every Other Major Sucks By Comparison](http://scottaaronson.com/blog/?p=442) :).

### All of Them

You can also try to mention all of the themes I have mentioned above. I haven't tried this, and I am not sure how effective it would be. You have to transfer the feeling and make the point, and it takes sometime. One other options is to mention all of them briefly at the start (or the end) and then go on with one of them, and tell them that they can contact you to get more informations about the other ones if they are interested.

### some comments

Whatever you are going to talk about, you should **be enthusiastic** about it. It is going to be much more difficult to interest them in a topic which is not really interesting to yourself. Tell them about your own reasons for selecting computer science. And **don't be boring**.


---

### Answer by username_2 on 2010-10-23. Score: 14

I've used two talks quite successfully with both high school students and entering freshmen.

1. Origami. I lead off with the 5-point star problem (this works well in american contexts, because of the connection to the american flag) and let students try to figure out how to make a five-point star with folding + 1 cut. I talk about the "resource" (cutting) and how algorithm design is about working with limited resources. Then I talk about other origami questions and applications in the real world (heart valves, NASA telescopes, crumple zones in cars).
2. Sorting pancakes: there's a beautiful connection between sorting pancakes and genome rearrangement, and I actually made stacks of pancakes from foam for students to play with. Works great, and lets me talk about algorithms, gene sequencing, Bill Gates (!), and other fun things.


---

### Answer by username_11 on 2010-10-22. Score: 10

[The New Turing Omnibus](http://rads.stackoverflow.com/amzn/click/0716782715) by A. K. Dewey has 66 so-called excursions in computer science.
It covers topics such as analysis of algorithms, AI, complexity theory, theory of computation, cryptography, computer graphics and so forth. Every topic is written in a rather condensed form, capturing some landmark result in computer science. This book could provide some inspiration.

Another possibility is to allow students to get their hands dirty via something like [Google's Code-in](http://code.google.com/opensource/gci/2010-11/index.html) program. It's a bit like [Google's Summer of Code](http://code.google.com/soc/), but, you know, for kids. Perhaps showing some of the amazing coding projects students can be involved in is one possible way of piquing interest.

> **Comments:**
> **username_11**: Of course, the book is from 1993 (I think) and thus a bit old school.  
> **username_0**: Yes there is a problem with trying to excite them about the future if one is referring to a book written before they were born :)  

---

### Answer by username_12 on 2010-10-22. Score: 10

Cryptography is always something that captures the mind of younger (and I personally hope older) individuals. I had friends who wanted to be nurses' assistants, hockey players, businessmen and politicians and friends (who despite their higher goals) took jobs as grocery baggers and cart pushers, construction workers and kennel assistants - all of whom invented and broke each others' (admittedly naive and simple) codes. In particular, the existence of public key cryptography is usually pretty easy to explain if one takes the route of RSA. One might also list some of the important results without proofs or constructions - Zero-Knowledge proofs and Homomorphic Encryption are bound to juice the geek factor for what it's worth.

Forward Error Correction and Error Detection codes are also very cool and if done right can be taught to a curious audience. To make them easier to digest, you could mention the "universality" of the index of coincidence - that all our spoken language and writing have small redundancies and exaggerations that help us to communicate in the noisy channel of a room containing shuffling bags, feet and humming air conditioners.

Finally, I also would suggest doing a simple introduction to complexity theory - something along the lines of my answer to [A Dinner-table description of Theoretical Computer Science](https://cstheory.stackexchange.com/questions/1471/dinner-table-description-of-theoretical-computer-science/1483#1483).


---

### Answer by username_8 on 2010-10-22. Score: 6

In my opinion, to be sexy to high school students you need to be some kind of magician. That's why I think that randomized algorithms are very good as a student attractor. For instance property testing is really something intriguing, and also something that can be explained (not the technicalities, but the idea) to anyone.

PCP is also magic, but I guess that this is out of reach...

> **Comments:**
> **username_13**: I had once given a talk about PCP to talented high school students, of course without proving it, but showing its applications to hardness of approximation and giving the general 'feel' of the theorem. I think they liked it, so it isn't that much out of reach (but they had listened to some talks about approximation algorithms before, without this I think they wouldn't grab the motivation of the theorem).  

---

### Answer by username_14 on 2010-10-27. Score: 4

Here is a very nice article on coding theory aimed at high school students by Michael Mitzenmacher:

<http://www.eecs.harvard.edu/~michaelm/FUTUREOFCS/codes-mitzenmacher.pdf>

> **Comments:**
> **username_2**: this is an excellent survey  
> **username_15**: This seems to part of a book that's a work-in-progress. Michael Mitzenmacher's blog post (http://mybiasedcoin.blogspot.com/2008/04/theorycs-book.html) has a link to that, which also has a very nice expository chapter (http://www.cs.princeton.edu/~chazelle/pubs/algorithm.html) on algorithms by Bernard Chazelle. That chapter isn't mathematics per se, but it is rich in mathematical ideas.  

---

### Answer by username_16 on 2010-10-24. Score: 4

My answer is not directly connected with TCS, but it can show that math can be beautiful and useful.

You could make a speech about how to get reliable data about how many students were cheating on the exam. If you asked them directly then You wouldn't get reliable data. The idea of how to get reliable data is very simple. First You tell every student to think about some integer number, then You say:  
- If it was odd number write down whether You like green color or not. You can choose any other simple question, but You have to know, from some other survey, what percentage of people answer yes on this question.  
- If it was even number write down whether You were cheating or not.

About 50% of students are going to answer on first question, and the other 50% are going to answer on second question. Now it is very easy to estimate how many students were cheating.
Example: If 40% of answers were yes, and You know that 30% of people like green color then You know that about 50% of students were cheating.


---

### Answer by username_17 on 2010-11-09. Score: 2

According to me, "computer science" is the "science of all sciences" :)

What is "science"? We get data from nature, and we try to construct a model that explains the data. Also, we assume implicitly that nature is not arbitrary. The laws of nature must have a concise expression, the data must satisfy some symmetries, etc.

But this is exactly a learning problem! The data is generated by some process that is promised to be of "low complexity", and our task is to reconstruct a description of the process.

Our understanding of such problems is at such a primitive level that it's your duty to work on them! :) Even our understanding of the seemingly simpler problem of whether the output of a black-box process is equivalent to some *fixed* function is far from complete. For example, suppose that we are promised that the black-box is evaluating a function that can be computed by a small-depth arithmetic circuit (this is easy to explain to high-schoolers), and we want to find out whether the box is computing the zero function. We don't know if this can be done in the lifetime of the universe for functions on reasonable sized domains!

Cue to start talking about arithmetic complexity theory, the chasm at depth 4, the role of randomness in computation, what's known if we reduce # of multiplication gates, etc. etc. ...


---

### Answer by username_18 on 2010-10-24. Score: 2

I think this is closely related to [Dinner-table description of theoretical computer science?](https://cstheory.stackexchange.com/questions/1471/dinner-table-description-of-theoretical-computer-science)

As I posted there I feel that algorithmics relate the best to every-day problems and can therefore motivate TCS very well. ("How long one google search would take if they would search in the same way you look up telephone numbers")

> **Comments:**
> **username_0**: Hello username_18!  The main difference I feel is that these are all mathematically inclined students making an active choice about what to do with their future. The problem we have had in recruitment, which may be peculiar to the UK, is that high school teaches them that CS is neither for great intellectuals nor for people who want to change the world.  I have 20 minutes to redress this misconception :)  
> **username_18**: That is right (also in Germany) and there might be some differences in attitude but the amount of CS specific knowledge present might be about the same as for the dinner table folks. I would agree that you have wrap the package differently for the other audience but I would choose the same content.  

---

### Answer by username_19 on 2011-06-15. Score: 2

In the Algorithms in the Field workshop a month ago in DIMACS, Graham Cormode was arguing in favor of teaching sketching techniques from streaming algorithms to undergraduates. Moses Charikar said that they do teach them in Princeton, I think @username_2 also mentioned he teaches things like the Misra-Gries algorithm for heavy hitters. I think some basic streaming results would be great for high school students too: they rely on basic but important math tricks, the problem formulations are like puzzles, and the solutions feel like magic, and magic is a great way to inspire high school students. You can make sure to emphasize the dramatic difference between the scale of the problem and the amount of resources you can use. A silly example: suppose that you can ask every person entering or leaving JFK airport their zipcode. Can you keep track how many different zipcodes have been represented in JFK during month, only using a notepad?

> **Comments:**
> **username_2**: yup. this is a good example  

---

