Writing a Final Exam

For me, one of the hardest challenges of teaching is making up homework assignments and final exams. For homework assignments, there's some assistance from the textbooks (and I re-use problems a lot), but final exams are very challenging: coming up with problems that test a student's learning but under a 3 hour time limitation. Making a final exam usually takes me several hours.

For my final exam, usually about 1/2 is True-False, Multiple-Choice, Give-an-Example-or-Counterexample, or Execute-the-Algorithm-on-This-Small-Example type problem. These are very different from the homework assignments, which are usually proof/computation/programming-oriented, and hence have "bigger" problems. The other 1/2 is more like the homework assignments -- proof-type-problems -- but sufficiently easier (or with sufficient hints) that students can hopefully get through them quickly. Interestingly, although you might think the first kinds of problems are easier, on both halves, student averages are about 70%.

I've toyed with the idea of giving take-home finals (which I do sometimes in my graduate classes), but these days it's just too easy for students to cheat. I know I've had students anonymously mail questions around looking for people to answer them. And arguably it's useful to have the final exam test something different than the type of problem-solving that they do on the homework.

When I think of the time spent making a final, I know I'd be happier not to give one. And of course the students would be happier too. Not better off, I think, but happier. Perhaps there's a different solution....

A Bubblesearch (Semi-)Success Story

A colleague was backing up files to DVDs and wanted to know a good bin-packing heuristic. I pointed him to First-Fit-Decreasing and Best-Fit-Decreasing, nicely described the Wikipedia entry on bin-packing, but suggested as long as he was doing that he ought to try Bubblesearch as well. Recall Bubblesearch just tries random perturbations of the greedy ordering, to try to find a better solution; the full description is in this paper.

His reported results are that with FFD everything fit into 5 DVDs, which was the minimum necessary; but he did find that Bubblesearch improved the utilization of the first 4 DVDs from 94% to 99% (with about 10,000 random perturbations, and some small parameter tuning), which he thought was impressive.

Your mileage my vary, and I'm sure there are better specific heuristics for bin-packing. The point behind Bubblesearch is that it is a natural extension for a wide class of Greedy heuristics, and moreover is really easy to understand and to implement. My completely self-interested and biased opinion is that it (or something like it) should be taught in all undergraduate algorithms classes....

Stopover at Google Boston

I gave a talk over at Google Boston yesterday, which is now actually located in Cambridge, in the building above the Kendall Square Legal Seafood [5 Cambridge Center]. It's new digs -- they've pretty much just moved in -- and the place had the look of still being put all together, in terms of decorations and all. It did look like a typical Google building -- very open cubicles, lots of conference rooms of various sizes, a game room, a lounge, a colorful cafeteria, etc. I talked about the Hiring Problem; they were going to record my talk and put it on YouTube, but nobody checked the camera battery before the talk, and it and the backup weren't charged. So I get to avoid for another day the issue of having my talks on YouTube. (The good: anyone can see your talk; the bad: anyone can see your talk.)

Although there's not "research" there per se, they're trying to build up a connection to Harvard, having speakers from EECS and other disciplines (economics, law, etc.) come by and give talks. I'm hoping they'll eventually put some research people there; it would be a nice addition to the soon-to-open Microsoft Cambridge lab. [Note to Big Tech companies -- research labs or lablets in Cambridge/the Boston area should be a no-brainer. If you want access to good students early in their careers, there are lots of good students around here...]

Suresh Venkatasubramanian and the "Foundations" Book

Suresh Venkatasubramanian of the famed Geomblog has offered to co-manage this Future of CS: Foundations book project with me, so we hopefully will get more chapters soon. Our goal is to arm-twist a half dozen or so people over the summer, and then once people see it get started, maybe more will join. At least, now I have a good excuse to arm-twist Suresh!

I've had some people e-mail me with interest -- I'm very enthused, and I'm hoping you'll all follow through! (And if you haven't yet, please e-mail us with interest.) I think the key rules, again, to remember are that it should be written for smart high school sophomores, and that each chapter should include a "glimpse into the future", which I think of as a description of a specific, big, open problem that one hopes might be solved in about the next 10 years.

It also, I think, helps to think of right-sized "nuggets" for such chapters. (Although I'm open to more experimental approaches, a la Chazelle.) One person suggested they'd write a chapter on universal hashing, which I think is a great idea. Trying to cover all of hashing seems too big. But explaining the basics of hashing, and then the specific role of universal hashing and why it's interesting, seems just right.

STOC 2009 : "Impending Doom"

Another surprise announcement: I was asked to be the PC chair for STOC 2009, and I accepted.

I have to admit, I was surprised to be asked, as I am, after all, somewhat vocal in my opinions, which are not always popular. (I was going to label myself a crank, with examples, here, here, here, and here, before someone else did, but I prefer "vocal".) Once asked, I found it hard to decline, despite the warnings that the job is a lot of work (and arguably little reward). It is an honor to be asked, I do believe in service for the community, and, most importantly, I felt it might lead to interesting fodder for the blog. (Obviously nothing confidential will be discussed, but the challenges of the process -- an inside view -- might be interesting.) It was something I was hopefully going to do once in my life. And (as Cynthia Dwork nicely pointed out to me, when I asked her about the job), I'm only getting older, and will have less energy.

Some people might be worried, given my noted worldview, that I might set out to change things drastically. I was thinking it would make a great joke to take "competitive analysis" off the list of topics of the call for papers, only to find it wasn't actually there. Rest assured that things will probably change incrementally; I respect the traditions, and I view the main part of this job to be selecting and empowering a solid, talented PC to do their best job.

The one change I'd really like to implement, so much so that I have to let people object already, is to introduce the rating system that conferences like SIGCOMM use:

5: top 5%
4: top 10%, not top 5%
3: top 25%, not top 10%
2: top 50%, not top 25
1: bottom 50%

I like this approach much better than trying to guess what everyone thinks a 7 means, or differentiating between a 6.3 and a 6.6. (Though, depending on the projected acceptance ratio, I could see changing the numbers a bit -- to top 10%, 10-20%, 20-33%.) I think this approach makes it easier to concentrate attention on controversial papers that need attention.

Barbara Grosz now Dean of Radcliffe

Barbara Grosz was officially appointed dean of the Radcliffe Institute for Advanced Study. Barbara had previously been the dean of science for Radcliffe and took over as Interim Dean of the Institute when Drew Faust was made President of Harvard.

For those who don't know Barbara, she's known for her work in AI, and has been a professor at Harvard since 1986. I took her class and TA'ed for her as an undergraduate. I'm excited this has been made official, because I was getting tired of using the word "interim" whenever discussing Barbara's status.

Harvard computer science continues its tradition of being quite "outgoing". Harry Lewis was Dean of Harvard College, Mike Smith is currently Dean of the Faculty of Arts and Sciences, and now Barbara Grosz is Dean of Radcliffe. Per capita, we're well above average in Dean-ness. The joke around the department is once you get tenure you have to watch your back, or someone might make you Dean of something....

Book Management

Talking about a "group-book" is a lot of fun. Actually putting one together, maybe less fun.

I like to think this project will be self-promoting, if it just gets started. A few people write their chapters. I put them online, blog about them, maybe push others to blog about them, a few more people think that's a good idea and look people are actually doing it, a few more chapters come in, and so on. Soon we have 20 or so chapters, and we think an actual book. (Maybe soon after that it catches on so well we get 40 chapters, and we make an omnibus.) To me, though, the hard part is getting started.

We need some rules of management, and if I'm currently the editor assigned to your paper for say SICOMP, you might now that management is not always my strong suit. (In self-defense, I'll say it depends on the situation. Corralling referees is not my best skill. And probably not corralling authors, leading to the failure the first time around.) So here, I'm happy to take advice. Send advice! Indeed, I've had a prod or two from people who'd be interested in co-managing/editing this project, so it won't be just me-- which is great!

I'll eventually work it out with co-editor(s), but here's my rough thoughts -- totally open to change.

1. We'll send annoying e-mail to people who we might like to write chapters. (Those who were on the old list, you're not off the list.)
2. People who want to write chapters can pick (and send me) a topic, so we don't get many people writing on the same topic.
3. Authors can make their participation public, so their name and a working title goes on the Web site, or private, so they can back out.
4. There has to be some notion of deadlines -- if you say you're going to write a chapter, after time x, you have to back out (and someone else might take the topic), or show significant progress.
5. I'd hope that several people might take time over the summer to write chapters, and then maybe some others over the fall, and so on. So if you think you can spare cycles over the summer to put a draft together, let me know!

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?

The TheoryCS Book

I'm glad to see interest of various kinds in the Book on Computer Science (I really need to come up with a catchy name) I talked about last post. And yes, as many of you correctly interpreted, I'm looking for volunteers!

To flesh the idea out for you, here is (with some small updating) the original proposal I sent out for what I had in mind. For those who don't like clicking, here are what I wrote as the main rules:

1. The intended audience you should have in mind when writing a chapter is smart high school sophomores. I see this as the most important rule. The goal is a book (or, more concretely, a collection of chapters) the general populace can pick up and read, to learn about computer science and why it is interesting. We want to hear people say: I decided to try computer science because of this book.

   This rule has some corollaries. First, fewer equations, more pictures. Second, lots of examples. Third, simple language. I do not mean to suggest that we talk down to the audience, or assume that they are mathematically ignorant, but that we assume as little as possible, and try to reach the broadest audience.

2. Each chapter should explain something already known and understood, and why it is significant.
3. Each chapter should explain a specific, but big, open problem that one hopes might be solved in the next 10-20 years, but probably not before that.
4. Each chapter should be roughly 15 book pages. If we can have 20 chapters, that will be about 300 pages, which is plenty. That's a guideline; I expect some variance.
5. Each chapter should include at least 3 easily available references for more information.

I've had many people tell me they think this type of writing is hard -- that is, writing for a general, non-research audience -- and I understand that. This task won't be for everyone. But if, as a field, we can't articulate to a general audience what we do and why it's interesting -- and in particular, if we can't provide some idea of where we hope we'll be in specific subareas a decade or so from now -- well, then I think we're in big trouble in the big landscape of science. I'm sure we can do it. I also think we haven't really tried hard enough to do it in the past, which explains things like our current NSF budget.

If you're wondering what such a chapter might look like, I have my chapter from back in 2006 available. (It's on coding, naturally.) I'll talk more about this chapter, and how much work a chapter is, next post.