Thursday, April 24, 2008

Writing a Chapter, and Answering Some Questions

Yesterday, I posted the chapter I had drafted on codes for the hoped for book on CS aimed at high school sophomores. (You'll also note I now have a link to Bernard Chazelle's marvelous essay, The Algorithm: Idiom of Modern Science. Bernard agreed to "donate" this essay to this book projects two years ago, and has again given permission for its use.) I just wanted to clarify, the chapter did not take long to write. There was some background time in thinking about what I wanted to present, and time for looking a few things up. The actual writing, though, took something like 3 half-days during the summer, and that includes pictures. While your mileage may vary, I don't think this project should be a time sink for anyone. I'd like to think that if you made it a priority, it could be done fairly quickly.

The chapter was designed to cover what I think are important features:
  1. A simple introduction, based on (hopefully) easy-to-follow examples.
  2. An explanation of why this is important in "the real world".
  3. Important past results, that are known and understood. (Here, Reed-Solomon codes and LDPC codes.)
  4. A goal for the future. (In this case, network codes, and figuring out how they might actually be used in networks.)
  5. Links/pointers to relevant references.
I don't think the chapter is perfect. (Feel free to send me suggestions.) But I do think this chapter is good. And that is a key point that answers many of the questions I receive about this project, about why I choose to do things one way or another. Right now, there really isn't a book/resource like what I think I have in mind. I'd rather have something that's good up in a year, rather than aim for something perfect that will take forever. "The perfect is the enemy of the good" applies here in my mind.

Other questions:

1) Why not do it in a wiki?

Answer: I've explained some in comments-- I don't think a wiki is appropriate for a "creative writing" exercise. Also, I'd like some actual commitment from authors, and I'd like them to get credit for their work. (If this all works out, you can put this on your next NSF grant application as your broad educational service.)

2) Why focus on "theory"?

Answer: It's that perfect/good thing. I'd like something coherent, that I'm qualified to manage, that can be done in a reasonable time frame. That means some focus, and I'm choosing to focus on theory. (And theory, in my mind, needs the PR.)

If this works out, we can expand to other volumes. Heck, I'll manage/edit volume 2, communications and networking. Then I'll hand it off to someone else.

3) Who do you want to volunteer?

Answer: I'll be honest -- I have a very strong preference for Ph.D.'s (over graduate students), and I'd generally prefer "name" professors/research scientists -- we need at least some of those, so we can start developing some of that cult of personality in our field, and so the book will carry some weight with publishers and other outsiders. But I'd be open to any and all good ideas.

4) Timeline?

Answer: Well, I'll talk about "management" more next post. But I'd hope that a dozen or so people could be convinced to take some time over the summer -- maybe a week or so -- and write up a chapter draft. But since last time that sort of schedule seemed too optimistic, I'd be thrilled to get chapters by the end of the year....
Next post: ideas on management?


Anonymous said...

I'm curious about the range of subjects you'd like to see included. How broad of a net are you using to define "theory"? I'm assuming that it would include machine learning and AI ... what about things like programming language semantics, or database theory? If you posted a list of proposed topics it would undoubtedly generate some interesting discussion here.

Anonymous said...

Programming language semantics are closer to theory than a lot of AI. The problem, of course, is that the entire field is ungodly boring!

But certainly:
Learning Theory
Game Theory
Complexity Theory
Approximation Algorithms

all have the potential to lend themselves to sexy chapters and captivating problems.

Anonymous said...

I wonder if this is the right way to think about the problem you are trying to solve. Do it this way and you will wind up with the framework for the theory quals (of schools that, unlike Harvard, actually have theory quals). You're not actually trying to crate a foundation on which a superstructure can be built, nor to visit all the squares of a neatly stitched quilt. You are trying to get students to say OK, I get the problem, dunno how to solve it ... Wow! that's really neat! I wonder what else there is like that?

So maybe you'd be better off thinking of PROBLEMS first, problems anyone can understand and have "elementary" solutions but have the characteristic that solving them exposes interesting principles. You may have to pause to develop some substructure on the way to the solution, or you may solve the problem and then explain the generalized structure later. Some areas, such as PL semantics, might get omitted entirely because there are no problems you can state to a 15 year old that are likely to seem natural.

Anonymous said...

Something I keep wondering when I see your posts on this subject: have you seen Dewney's The (New) Turing Omnibus? How would your project differ from that book?

D. Eppstein (for some reason locked out of OpenID today)

Anonymous said...

Here's a problem - let's say you have codes to launch a nuclear missile. You'd like to divide the codes between two people, so that neither one can launch the missile alone. (Think the opening scene from WarGames.)

How do you do it?

Answer: draw a line that crosses the Y-axis at the coordinate equal to the launch codes. Give each person one point on the line.

Can then bring up issues of how best to represent "points" and "lines" on a computer. This leads to secret sharing over finite fields, which ties into the Reed-Solomon codes you described in the sample chapter.

Michael Mitzenmacher said...

Harry --

I agree with your sentiment. The point of what I'm aiming for is not to cover every area of CS (or even of theory). It's to spark that curiosity.

I guess I just think there are problems in most areas of CS (and in particular TCS) that are interesting. I'm not interested in starting with problems. I'm interested in starting with people -- people who think they have something interesting to write about and who are interested in writing -- and I assume that the exciting problems will come from there.

So I don't want to make a laundry list of "topics to covered". (Though, from my own personal bias, of course I think there are topics that are really exciting and should be covered.)

Michael Mitzenmacher said...

anonymous -- I just looked at what I could of the Turning omnibus online. It looks cool. But it looks much more mathematical/deep than I'm expecting. From my quick peek, it looks like it's at the level of college sophomores (in particular, college sophomores who have probably had some CS already!). I'd like to aim for high school sophomores.

Anonymous said...

I think there are completely untapped markets you haven't mentioned. By aiming at high school sophomores you are writing at a level that is accessible by anyone vaguely interested in the subject. This includes leagues of business people, older engineers, and those generally interested in problem solving. Lastly, as a graduate student, I would probably grab a copy for my parents to better explain my interests in the form of interesting/meaningful problems. By increasing the general awareness of problems computer scientists are interested in, you still will likely achieve your goal of attracting younger people to the field. Personally I believe explaining the subject via analogy to everyday problems (e.g. TSP) you can make it accessible to many. If you would like a small audience of potential high school students I would be glad to help where possible.

Anonymous said...

High school sophomores can be highly perceptive if you give them a problem that is meaningful. I had to work on some trigonometry homework problems with my niece (HS Junior) a couple of weeks back.

I wrote something similar to this on Isabel's blog the other day. The idea is that you start with an interesting problem, construct the meaningful abstractions, reason about them, then come back to answer about your concrete problem.

In this case, if you want to encourage kids to investigate and understand theory, it might be useful to construct a problem, derive the abstractions, then map those abstractions to [same|[near|not] similar] problems. This demonstrates the two important things, bijective abstract-concrete reasoning, and the importance of looking for the abstract [refactoring your comprehension base].