Kids and TCS

I'd like to follow up on a comment to my last post, on looking for a book describing the math behind Sudoku.

Anthony Widjaja To asked the following:

... I have noticed several postings in the blogsphere (including your blog, Suresh's, and Lance's) on how to popularize complexity theory to general audience. I am interested in something related: how to get kids interested in math and science (including computer science, physics, or even cosmology). These days many kids are spoiled by video games, etc. leaving very little room for curiosity about math and science. Since you have kids and are interested in a related issue, I'm sure you have some advice or pointers to useful discussion.

Well, I'm not sure if I have any useful advice about this, but let me mention a couple of things, which I think apply to math and science generally as well as to TCS in particular. First off, I feel that the question of how to get kids interested in TCS and how to get the general public interested in TCS are one and the same. That is to say, I think the only way to get the general public interested is to get kids interested, and then wait for them to grow up. I strongly suspect that the people who made up the audience for the various specials on Einstein this past year, or who buy up books like Brian Greene's The Elegant Universe, first became interested in the subject as kids or young adults. You may be able to get a few converts later in life, but not enough to make a significant difference.

Now having said that, I do think it's possible for TCS in particular to gain "market share" in the general public by stealing some interest away from those physics and cosmology fans. To do that, it needs to position itself a bit differently. I think that what attracts laypeople to physics and cosmology is that it seems to address some fundamental questions about what our place in the universe is. Practitioners in TCS need to occasionally step back from their narrow research interests and look at "big picture" questions of what is computation, what is information, what are the formal limitations of knowledge, why are some tasks inherently difficult -- and then write about these topics for a general audience. Sure, there are a few books like that on the market already, but it's purely a matter of numbers: For every Elegant Universe, I'm sure there are hoards of obscure physics books that nobody reads. Conversely, if you want to see another, say, Gödel, Escher, Bach, then you've got to start cranking out TCS books until you get a winner. This is not meant to suggest that the success or failure of a book is a matter of chance, but rather that it's not knowable in advance who's going to make a great author. So everyone should be encouraged to write at least one book for a general audience.

As for how to get kids interested in computing, my own kids are still a little young for me to have experimented on personal experience with. But I think a couple of points are clear. First, you have to start young enough, as soon as students are old enough to grasp concepts like what an algorithm is. This should happen by middle school or junior high. I think this is particularly important for getting girls interested in computing. Second, you need to hold students' attention by tying computing to other topics they're interested in. The undecidability of the halting problem is going to grab a certain type of student, but for others it is going to be too dry and abstract. Fortunately, computing has direct application to such a wide range of topics that there ought to be something for everyone. Case in point: I was checking the server stats for this blog, and the most popular search keyword so far this month is (you guessed it): sudoku.

There are educational standards that have been developed by various professional organizations. For example, the Computer Science Teachers Association was formed by the ACM to promote K-12 computer science education. They have a model curriculum that schools can use as a guide. The Mathematical Association of America promotes mathematics education at the college and grade-school levels and obviously will include topics relevant to computing. Unfortunately, model curricula probably aren't going to help too much with the question Anthony had in mind. Here is something aimed at young students that looks pretty neat, Computer Science Unplugged. I just bought a copy of this book and will let you know what my impression is once I have a chance to play around with it.

What I would really like to see are some web sites designed to teach computing to young students. Math and computer science are ideally suited subjects for on-line instruction, and you'd think there would be some real kick-ass web sites out there to do just that. However, the sites I've seen so far have been pretty lame. This is something that the ACM/CSTA, with its combination of an interest in pedagogy and technical expertise, ought to be taking the lead in.

Finally, on a personal level, the way to get kids interested in computing (or science or math) is by setting an example. If the children around you see that you find these subjects interesting, they will be more likely to explore them at some point. (And for this strategy to work, you have to begin when they're very young, before they start using you as an example of what not to do.)

Math and Sudoku

Welcome to 2006! I hope everyone had a cheery holiday season.

I posed the following query on comp.theory but haven't gotten any responses at all, so I thought I'd see if I can get any feedback here. (In the past when I've posted some really dumb questions on comp.theory, I've received lots of replies; there seems to be an inverse relationship between the volume of discussion and the meaningfullness of it. So maybe my current question is not so bad.)

My niece has become interested in sudoku, and this interest has spread to my own children. I was thinking that sudoku would make a nice jumping-off point to introduce topics in discrete math and complexity theory. Are there any books out there that deal with this? I haven't been able to find anything. Ideally, such a book would be geared toward a teen-aged audience and maybe cover topics like combinatorics, logic, and NP-completeness as they apply to sudoku. A quick Google search reveals lots of web sites that touch on this stuff, so maybe it's just too new an area to have made its way to print yet.

I'm reminded of some of the discussion following FOCS '05 about how to get complexity theory into the public awareness. It seems to me that tying it to a subject that's already popular with the general public would be one way to achieve this.

Any thoughts? I know David Eppstein has an interest in sudoku; I wonder if he's ever considered writing something like this. Or maybe I should think about writing this myself? I'm grossly unqualified, of course, but that might actually be an advantage--it could make it easier to understand the point of view of a general audience and anticipate the hard spots when explaining concepts.