Inspirational talk for final year high school pupils

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

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 5

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 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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

Answer 10

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 11

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

Answer 12

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 13

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?