Book by FemaleScienceProfessor

I'm an occasional reader of the blog FemaleScienceProfessor. Often the blog is just about being a science professor, which is interesting, and I can relate to. And sometimes the blog is specifically about being a female science professor, which is also interesting, even if I relate to it less.

Well, FSP has re-worked past blog entries into an on-line book available at lulu.com. I haven't yet bought and downloaded it yet, but from the Table of Contents, it appears to be a particularly worthwhile book for graduate students thinking about a life in academia, and for new faculty. The bulk of the book seems gender-neutral, if that's a concern. I thought I'd give it a free plug.

Failure, and a Second Try

About two years ago, I went through a huge failure on a project. In the back of my mind, I always wanted to use this blog as a jumping off point for a second chance for this project. Now is the time. Perhaps some of you can help me fix this failure.

Back in early 2006, while I was on what's now known as the SIGACT Committee for the Advancement of Theoretical Computer Science, I was thinking about ways to promote theoretical computer science (TCS). One idea that struck me is that most people entering college from high school know nothing about TCS. If they've had exposure to computer science, it has been programming. Compared to the excitement of biology (we're figuring out the building blocks of life!) or physics (we're figuring out the building blocks of the universe!), computer science must seem to the average high school student to be, scientifcally speaking, a wasteland.

Now, we know this isn't true. Those of us in TCS wouldn't be in it unless we thought there were fantastic, mind-bending, potentially world-changing problems in the field. And I think history is on our side; computer science, and in particular TCS, has changed the world, fundamentally, and continues to do so. I don't think, though, we do a good job of promotion, showing the world, and in particular high school students who we might hope to attract to our field, the excitement of TCS. Somehow, our field still attracts talent, but it's an uphill battle. If we could change that, I thought, we could change the perception of our field, attracting top students earlier, and long-term creating a greater appreciation of TCS in computer science and across the sciences.

So in 2006, I dreamed up a project. I wanted a book that could be handed to high-school sophomores, to give them an idea of what TCS is all about. I wanted a book I could give to friends' kids -- heck, to my own kids, when they got to the right age (and wanted to really know what Dad did with his time). I wanted a book that would be interesting, engaging, and cover the wide swathe of work we do.

So, naturally, I knew I couldn't write this myself.

Instead, I wanted a group-book, with experts writing chapters in their areas of expertise. I reached out to about 40 or so people in the TCS community, asking them to write a chapter. I hoped first drafts could be done over summer 2006. And that by the end of the year, we might have a book ready for a publisher. About 1/2 the people agreed, and I sent occasional e-mails reminding and encouraging people.

And nothing happened. I think lots of people started, but never finished, their chapters. I heard a lot about how it was difficult to write chapters for the target audience, high school sophomores. It seemed for everyone that other projects, other papers, other things took priority. Disheartened, and busy myself, I let it go.

I still thought the project was a good idea. I still think so. So now, over the next couple of weeks, I'm going to revive the project here on the blog. I hope to change the nature of the project a bit, so my initial management failure won't necessarily repeat itself. It's something I've wanted to do since I started the blog, but I've kept putting it off.

I think it's time to try again. More to follow.

Books from my Shelf, Part 3

Today, let's look at some more practical books from the shelf.

Network Algorithmics, George Varghese: Even before he wrote this book, George Varghese had essentially written the book on how to get good performance on your network devices (e.g., routers) by smartly using algorithms combined with systems thinking. George is my role model in this area, even moreso now that I've worked with him on a few projects. If you want to see how network people are thinking about and using algorithms for packet classification, prefix-lookups, switching, scheduling, security, and so on, pick up this book.

Mining the Web, Soumen Chakrabarti: Sigh. Has it really been over ten years (no need to get more specific than that!) since Soumen and I were graduate students at Berkeley together? Soumen's one of those people who could have been a great theoretician, but was always lured by that "real world" thing, and instead became an expert on information retrieval and the web, which lets him still do theory now and again but with an eye toward problems of more immediate importance. A great book for everything you might want to know to start building your own search engine. Web crawling, information retrieval, clustering and classification, etc. And lots of algorithms and algorithmic insights.

TCP/IP Illustrated, Volumes 1 + 2, Stevens and Wright: At some point, I was looking at TCP for research purposes, and this was a great book for understanding the fine details. It may take a little looking, but the details are in there. Volume 1 also provides background on a lot of basics that I think are useful for networking research. Finally, I also think it would be useful for theorists to look over this book at some point is to get some insight into real-world systems-thinking.

Books from my Shelf, Part 2

Continuing a list of some interesting books...

Reversibility and Stochastic Networks, Frank Kelly: This was the book that got me interested in queueing theory style mathematics -- well, really it was a course I took from Frank Kelly, based on the book, and Frank then gave me a copy. The book is out of print, but nicely available online from the link. It's all about Markov chains, queues, queueing networks, and various applications. While I'm sure there are more "modern" treatments, I think the book holds up quite nicely.

Queueing Systems (Volume 1, Theory), Leonard Kleinrock: Another classic with all the basics of queueing theory, including all the fundamental results of all the basic types of queues. (While Volume 2, on Computer Applications, is also interesting, I think Volume 1 is much more useful.)

A First Course in Stochastic Processes, Karlin and Taylor: OK, another classic probability book. (Yes, there's still more of them to come.) Markov chains, renewal theory, Brownian motion, branching processes, etc. (While the Second Course, with more advanced material, is also interesting and useful, I think the first book is much more important.)

Introduction to Probability Theory and Its Applications (vols 1 and 2), Feller. Again with the classics. The classics are apparently classics for a reason, at least in my mind...

Books from my Shelf, Part 1

Commenters have told me they want some book recommendations, so here I go... since there's a number of books, I'll be breaking this post up.

But first, a caveat, I'm not a big collector of academic books. I was spoiled by Berkeley's libraries as a graduate student, and am spoiled by Harvard and MIT's libraries now. But here are some of the books on my shelf that I find useful (besides, of course, the obvious Mitzenmacher and Upfal, which everyone must have on their shelf). Some are useful for theory, some for practice, some for... well, hopefully the descriptions will give some idea. In no particular order, here are the first 5, with more to come...

Handbook of Algorithms and Data Structures, Gonnet and Baeza-Yates: Apparently out of print, but well worth getting used. This is the state of the art in hashing, search algorithms, sorting algorithms, priority queues, text search, etc. as of 1990. And one of the best sources if you need to look up, say, the formulas for the expectation and variance for the number of accesses required under linear probing hashing to insert the (n+1)st element into a table, or pretty much anything else in that vein. Chock-full of formulas and references, this is my go-to book for looking up the basics. Someone should write an updated version of this classic.

Elements of Information Theory, Cover and Thomas: This book is the classic standard introductory text for information theory. And it's just a darn fine book, well written and covering all the basics so you could, for example, skim it over and then go to information theory conferences and act as though you sort of belong.

Modern Coding Theory, Richardson and Urbanke: OK, it's not yet on my shelf, I still have to get a copy. This book is for everything you've wanted to know about low-density parity-check codes by two of the leading experts in the field. I'm not sure I'd recommend it generally to everyone, but I would to everyone interested in coding theory in general (and LDPC's in particular).

Information Theory, Inference, and Learning Algorithms, David MacKay: This book, which I've enjoyed since it came out, now lies somewhat interestingly between the above two information theory books. It's a bit more basic and broad, covering fundamentals of compression, coding, and Bayesian inference, while also covering topics like LDPC codes and neural networks. The book is a bit idiosyncratic, and naturally, since I enjoy David's work, I enjoy the book.

Complex Graphs and Networks, Chung and Lu: I like having this book around so I can pull up Chapter 2 for reference -- all about tail bounds, with an emphasis on variants of martingale bounds (Azuma's inequality) that cover more obscure situations that arise and are hard to find easily elsewhere.

Algorithms for Newbies: Static or Dynamic?

A talk I just went too (by Lynn Stein) raised the following question for me.

While I have some strange ideas about how an algorithms class should be taught (like students should do some programming in an algorithms class), in most ways my algorithms class is quite traditional. Roughly, my class looks quite similar in the path it takes to Algorithm Design by Kleinberg/Tardos (or the corresponding subsections of the standard Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein). And specifically, I teach primarily what we'd call "static" algorithms; there's an input, a desired output, and the algorithm is the recipe.

These days, many of us do research in and arguably most commercial products use "dynamic" algorithms; that is, they're processes that are always on, reacting to the environment around them. (Your cell phone, for example, might be considered a dynamic algorithm device; so would a robot vehicle. If you like, you can think of "dynamic algorithms" as roughly being closely tied to "distributed systems".) My course is not geared to teach or have student explore dynamic algorithms, although they get brief mention. Lynn seemed to be suggesting that dynamic algorithms and programs should be taught before static algorithms and programs. It is, after all, the paradigm students are most familiar with, and arguably more interesting to them.

This doesn't sit right with me. In my mind, it's partly a "walk before you can run" issue -- you could teach a lot of calculus without teaching trig, but it doesn't seem the right way to go. Although that's not really quite the right analogy; I can see that the issues in dynamic algorithms/distributed systems -- like communication, and responding to asynchronous incoming signals -- are often quite different than for static algorithms, so much so that in many case you don't have to know your standard static algorithms to write a dynamic one. I think it's more that I think that to do anything that I would consider technically interesting you need to know static algorithms first. That is, sure you can probably teach people to write an interactive Internet chat program pretty easily, and they'd learn a lot by doing it, but that's like the task 20 years ago of writing a checkbook program, just harder because of issues raised by the interactivity. To do really interesting things with dynamic algorithms, my bias is you need good static algorithms behind it. Like Google mail's search features, or Amazon's recommendation feature, or other stuff. (Or at least, in many cases, you should understand the static version of an algorithm before trying to understand the dynamic version of it.)

So now I'm wondering if I'm just old-fashioned. What do you all think?

New Book : Algorithmic Game Theory

I recently received my "desk copy" of the new book Algorithmic Game Theory, edited by Nisan, Roughgarden, Tardos, and Vazirani.

While I haven't read it cover-to-cover yet, I'm very impressed by the book. It's taken a large area with a fairly short history, and broken it up into reasonable-sized chunks each written by an expert, with most chunks covering a new and active research area. For example, Michael Kearns writes about Graphical Games, Christos Papadimitriou explains the complexity of finding Nash equilibria, Jon Kleinberg discusses cascading behavior in networks and the corresponding economic issues, Ramesh Johari and David Parkes and Joan Feigenbaum and so many others have chapters on their specialties, and so on. Overall I count 45 contributors! The result is a solid tome that really combines breadth and depth to create a resource that I assume works well for people working in the area and is certainly useful for an outsider trying to look in and see what's going on. There are also exercises in some chapters; it could certainly be used as a textbook.

I'd like to see other books of this form, built up by a coalition of experts to cover emerging areas. You do lose something with this approach -- for example, many concepts are defined multiple times in various chapters, and while the authors have made an effort pointing out relations among chapters, you don't really have the sense of coherence you get from most textbooks or books about research written by a single author. On the other hand, you do get a much broader coverage of topics than you'd probably see from a single-author textbook, and I assume that it was easier to spread the workload among authors. It's not clear to me any single author (or group of 3-4) could have put something like this together in any reasonable amount of time. Kudos to the editors (and authors).

What other topics could benefit from a treatment like this?

Book Reviews

For those of you who haven't succumbed to buying the
Mitzenmacher/Upfal textbook on Probability and Computing,
there are two very positive reviews that will appear in the next SIGACT newsletter. Here are the reviews, excerpted from the SIGACT book reviews page Bill Gasarch maintains.