Inspirational talk for final year high school pupils

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.

-
I'm thinking this should be CW ? –  Suresh Venkat Oct 22 '10 at 19:43
Is this really TCS research level question?! –  Mohammad Al-Turkistany Oct 22 '10 at 21:32
@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 Oct 22 '10 at 22:32
@turkistany: Yes, yes, a thousand times yes. –  JɛﬀE Oct 23 '10 at 17:41
@JeffE, Ok, Ok,..., infinite number of times OK. I get now :) –  Mohammad Al-Turkistany Oct 23 '10 at 19:26

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.

-
Presenting ZK proofs is a very good choice. Another example which I think will be understandable to students is graph coloring. –  Kaveh Oct 23 '10 at 5:57
There's a cool ZK sudoku demo from Moni Naor's page. –  Suresh Venkat Oct 23 '10 at 7:07
That is very nice. Thank you. –  Raphael Oct 23 '10 at 17:15
While Goldreich has contributed a lot to this field, ZK proofs are originally due to Goldwasser, Micali, and Rackoff. PS: The color-blind-convincing protocol is actually due to Goldreich (see http://www.wisdom.weizmann.ac.il/~oded/poster03.html). –  Sadeq Dousti Dec 15 '10 at 20:16
@Sadeq: I am sure Ryan meant that ZKP for ball color with a color blind prover is due to Goldreich :) –  Sasho Nikolov Jun 15 '11 at 21:29

A good source for education purposes in general is CS unplugged, which has lots of neat CS ideas translated into high-school and middle-school activities.

-
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. –  Raphael Oct 24 '10 at 13:01
The Teacher's Edition book looks more suitable for primary-school and middle-school children, rather than for high-school students. –  Alessandro Cosentino Oct 25 '10 at 3:57

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.

-
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 Oct 23 '10 at 10:24
They're definitely playing video games. –  Daniel Apon Oct 24 '10 at 13:59

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

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 and Great Ideas In Theoretical Computer Science 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 :).

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.

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.

-
+1 for "make them feel that the area is alive". –  András Salamon Oct 24 '10 at 14:04

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.

-
Thanks very much. Those do look great fun. –  Raphael Nov 15 '10 at 13:51

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.

-

The New Turing Omnibus 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 program. It's a bit like Google's Summer of Code, 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.

-
Of course, the book is from 1993 (I think) and thus a bit old school. –  Dave Clarke Oct 22 '10 at 20:07
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 :) –  Raphael Oct 22 '10 at 20:33

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

-
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 Oct 23 '10 at 21:01

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

-
this is an excellent survey –  Suresh Venkat Oct 27 '10 at 19:54
Thanks for that. –  Raphael Oct 27 '10 at 20:07
This seems to part of a book that's a work-in-progress. Michael Mitzenmacher's blog post (mybiasedcoin.blogspot.com/2008/04/theorycs-book.html) has a link to that, which also has a very nice expository chapter (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 Oct 27 '10 at 21:44

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.

-

I think this is closely related to http://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")

-
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 :) –  Raphael Oct 24 '10 at 12:55
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 Oct 24 '10 at 14:59

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

-

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?

-
yup. this is a good example –  Suresh Venkat Jun 17 '11 at 17:52