Big Numbers

In my algorithms class, at some point, I teach RSA and primality testing. For the corresponding assignment, I usually have students do a "numerical exercise" which involves, naturally, computing with some big numbers. They also have a later programming assignment where they have to use numbers that may not fit into a standard-programming-language-sized integer. Since this is not a programming class, and I do not prescribe a language for them to use, I essentially tell them it's part of the homework to figure this out.

Surprisingly, it seems to give a number of people significant grief every year. I know that for C and Java it's a pain -- the natural thing to do is to download and install a BigNumber library, which should be easy, but often some trouble arises. (And most students, even though they've had the intro programming courses, do not seem to have learned how to do useful things like download and run useful libraries.) There are other programming languages which handle big numbers essentially transparently -- ah, the days of programming in Lisp -- which are fine for the numerical exercise, but may not be as nice for the larger programming assignment.

My only real point here is that, in those lists of skills I would expect CS majors to have, I'd have to put "being able to do computations with very large numbers" somewhere on the list. Yes, you're unlikely to need it for your standard checkbook program, but it seems to me this issue arises in plenty of places. (It has for me -- and my graduate students -- several times.) And it's not so important that they know how to do this specific task off the top of their head, but more that when they're given a task like this, they are able to find the information they need and complete it in a timely fashion. For better or worse, that's something some of them get out of my class.

Problematic Students

One thing they don't warn you about in graduate school -- unless some places have changed their "teaching preparation" classes to be somewhat more useful -- is that, every once in a while, you'll get a student who is, shall we politely say, "problematic". This is the student that takes up 80% of the time you spend interacting with students that semester, and in a negative way.

I've probably seen a few more of these students than the average, because I've allowed my course to be offered through the Harvard extension school. There have definitely been many cases there of students who just enter the class insufficiently prepared, and most of them quickly drop the class. But occasionally there's one who misunderstands and thinks it's our fault (mine and the TAs) that they're failing a class that they may not have had the necessary background for to begin with. (I've recently had to deal with such a student, which brought up this line of thinking.)

For sheer annoyance value, though, my most problematic student was a Harvard student. He or she (let's use "he" from hereon) got a warning from me partway through the semester because he failed to turn in an assignment. I told him he had done fine on the assignments he had turned in, but if he didn't turn in one or more future assignments, his grade would suffer, and he could even fail the class. He said he'd understood.

After the midterm, he did not turn in another problem set. Which would be fine, except that he then made a rather large issue out of failing the class. He insisted on knowing the exact formula I used to assign grades, going over every question on the midterm and final with me, and so on. In short, he refused to take responsibility for the outcome, which is the hallmark of a problematic student.

I'm curious if other teachers have had similar experiences, and what advice they might have in dealing with such students. (My advice -- catch these students early, and document by e-mail what they have been told regarding their performance! And try to spend more time with more positive students.)

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

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.

Security, and Class Projects

As I was reading Freedom to Tinker, catching up on the latest reports of flawed voting machines, I remembered my favorite class project of all time.

My first year teaching Algorithms at the End of the Wire, I included a subunit on cryptography/security. (This was before Salil Vadhan arrived, and before Michael Rabin started regularly teaching a crypto course.) One group, for their final class project, decided to explore the potential security flaws in the Crimson Cash system, the local system where students put money on their ID. They got a card reader and figured out how to intercept and spoof messages from the vending machines in the Maxwell-Dworkin lobby. It was a standard man-in-the-middle attack -- you intercept the message from the vending machine so your account doesn't get debited, and tell the vending machine the message went through. For their demo, they showed how they could get a free soda. They got to learn about security by breaking an actual system (which, by the way, in retrospect was something of a bad idea -- next time students try to break system security, I'll make sure they do it in a closed, lab-type setting).

It was great stuff. All CS majors should do some sort of a-little-bit-out-there, hands-on project like that. And then, maybe, we'd have better voting machines.

CS 124 and xkcd

A few of my students in CS 124 (Algorithms and Data Structures) pointed me to this xkcd cartoon -- amused, no doubt, that we had covered the O(2^n n^2) algorithms in class about a week ago. And who says that you don't learn anything important in my class!

David Eppstein was inspired to write a longer blog post on the algorithm, well worth reading (especially if you're in my class!).

Class Demographics

This year, my undergraduate algorithms and data structures class is about 25% women. This is significantly more than average (enough that I noticed). Based on previous experience (and initial impressions from the first few lectures), these women will be very strong candidates for graduate school should they choose to apply when they graduate (one or two years from now). (I could simply be suffering mental bias from the various studies I've read, but my recollection from prior years is that when there's a larger cohort of women in the class, they generally perform better overall. I leave others to postulate on causes and effects, or to argue whether my data point is unrepresentative.)

Class Reviews

I just received the class reviews for my Randomized Algorithms class. Historically, I have found my reviews are bimodal. Some students describe me as their favorite professor (and end up taking all my classes). Some students describe me in fairly unflattering terms. This year was pretty much the same.

The most signal from the noise was worth hearing, although pretty much stuff I already knew. First, students would like more of my time. I apologize for being busy, I suppose. Second, it would have much better to have had a TA. I agree (you think I enjoyed grading problem sets???). Sadly, my first choice TA was (rightly) busy working on his thesis, and there wasn't really another appropriate graduate (or undergraduate) student. But going without a TA is not something I'll try again.

A lot of the rest of the comments are lost in the jumble that comes from teaching to a class that serves a wide audience, not just theory folks. Some thought it was too fast, some too slow. Some liked that we pretty much followed my textbook, some thought I should let people read the textbook on their own and cover other stuff. Most found the problem sets a "challenge", which I think is just fine.

Class reviews never answer the question I really want answered. Five years out, was my class worthwhile? Has it had any impact on your research/job/worldview/life? Or even if you don't see an impact, do you remember it as a worthwhile learning experience? I don't care if you come out of the class thinking I'm some sort of sadistic homework machine (but really, I'm not...), if a few years down the road you find it was all worthwhile.

So ex-students -- not just MY ex-students, but all ex-students -- if you have a class you particularly liked several years back, a class that sticks in your mind or a class where the material has proven really useful to you later on, please send an e-mail to that professor and let them know. Anonymously is fine. That's the kind of feedback that means a lot to teachers. And you can even do it if you had a course you particularly disliked -- at least I wouldn't mind hearing from students who years down the line still think that I did a terrible job if they have constructive contributions to offer.

More on the Shopping Period

As I mentioned two posts ago, Harvard has an unusual tradition of a "shopping period" -- you don't preregister for a class, but you choose classes after the first week, after you've had a chance to go to a lecture or two and see how you like it.

As a student, I loved it. What better way to get an idea if you'll like a class than to go, hear the professor, check out the syllabus, see who else is thinking of taking the class, etc. It makes choosing classes much more flexible. Instead of switching out of classes you've already chosen without seeing, you choose later. Part of that benefit might just be psychological -- most schools allow you to change courses in the first few weeks fairly easily -- but there is a marked difference between changing your classes and choosing your classes, especially if a student has to fill out forms or get signatures to change a class. The openness of the first week is a real benefit to students. I can understand why something like shopping period just might not be feasible for some very large schools, but I think it's a shame more schools don't do it.

Several years ago, there was a movement by the administration to introduce preregistration and get rid of shopping period. I was on the Committee for Undergraduate Education and the Faculty Council, and when the idea was first brought up I spoke against it, only to find that the issue didn't seem up for discussion; it apparently had been "decided" higher up. (It's things like this that helped make the Presidency of Larry Summers so unpopular, as opposed to some of the supposed reasons popularized in the press.) I was surprised that so many faculty on these advisory committees seemed willing to go along with the idea. It was massively unpopular among Computer Science faculty; we like students being able to choose their courses.

Overall, naturally, students didn't seem to like the idea. The administration's main argument seemed to be that it would allow more accurate predictions of class sizes in advance, so Teaching Assistants (and, in some classes, classrooms) could be assigned more readily and efficiently. (Here's an old Crimson opinion giving both sides of the issue.) This was around a time period where there were murmurs of graduate student unionization, and that might have been influencing the administration's mindset. Of course, nobody in the administration had an answer when I asked what prediction mechanisms they were using now, and if there was any evidence that preregistration would help predictions any. (I wasn't the only one asking this question. This was another reason the CS faculty in particular were against the idea; they saw no reason for it. It's in interesting problem to design an enrollment predictor; one semester, Stuart Shieber ended up running a projects class to find solutions for the problem.)

A funny thing happened, though. The change had to be approved by the faculty, and while I seemed to be a lonely voice with objections in these committee meetings, apparently a lot of faculty didn't actually like the idea. Instead of it being a quick and simple vote like the administration seemed to expect, the faculty meeting was a disaster. Eleven faculty spoke on the issue; ten spoke against it (including, I'm happy to say, me). Quietly, pre-registration was dropped as an issue, and shopping period continues.

Shopping Period Lecture

One of the great Harvard "traditions" that I enjoyed as a student is the "shopping period". Students don't pre-register for classes; they spend the first week "shopping" whatever classes they like, and then choose what ones they want to take. (I'll talk more about the "politics" of shopping -- the pros and cons -- next time.)

Because of this, rather than dive right into material the first class for my Algorithms and Data Structures class, besides going over the syllabus and requirements, I do something that at least I consider fun. We talk about how to get fair bits from a biased coin. The class starts with the classic brain-teaser: suppose you have a coin that may be biased. How can we flip that coin to decide something fairly, like who should pay for lunch?

[The simple solution to this question, unless I'm mistaken, is commonly attributed to von Neumann.]

Starting from there, I try and take the class through a series of questions, leading up to how to efficiently extract lots of random bits from a sequence of biased flips. The method I base the lecture on is due to Yuval Peres [(see "Iterating von Neumann's Procedure for Extracting Random Bits," Annals of Statistics, March 1992)], and I learned about it at some point in graduate school at Berkeley. I try to run this lecture in a very back-and-forth manner, asking questions of the students and trying to get them to answer. (I also do this a bunch during the semester, with varying degrees of success...) Here's a version of my notes, with the various questions.

For the students who decide not to take the course, I figure at the very least they've learned something interesting that they can take with them. Also, it's conceivably the only time students will hear the word "entropy" in a computer science class, so I think it's worthwhile for that alone. Somehow, this problem fascinates people. Way back when I had more energy, I wrote a Dr. Dobb's article on it to show it to a wider audience, and there's been lots of related research on the problem. In some sense, this problem is the pre-history of all the randomness extraction work that has come since.

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?

Preparing Students for Jobs

In a recent "discussion" on another blog, I repeatedly heard the refrain that we ivory-tower pie-in-the-sky university computer science professor types just aren't preparing students suitably for "real-world" employment. Personally, I think that's just BS. However, I realize I may have a fairly biased viewpoint. I teach at Harvard, and, if I may say so, our students are generally quite good and do well in the job market. Having spent some time in industry, and, if I may so so, being perhaps more interested than the average theorist about practical issues, I attempt to add "real-world" aspects to my classes, like programming assignments in my undergraduate theory course.

Now occasionally I catch students who admit to reading this blog. I mean all students, from whatever school, undergraduates and graduate students, not just students from my classes or Harvard students. I hope some of you are reading now. Because I'd like to ask you to enlighten me. (That means, for instance, I'll keep quiet on the comments.) Please tell me, in your experience, did your education prepare you for your life after in the real world. (For current students, you can comment on how you feel your education is preparing you.)

While I'd expect you to comment anonymously, I'd ask that you provide salient information where possible. (Harvard student or not, current undergraduate or long-time real-world person, CS or EE or other major, etc.) I'd also greatly enjoy hearing specific comments and criticism regarding my own classes, from any ex-students out there.

And in advance of some annoying anonymous commenter who might feel the need to say how out of touch I must be that I need to find out how students are doing by asking on my blog, please rest assured I have other sources of information (both personal and data-driven) on the subject, but this is, hopefully, an interesting opportunity for me and others to gain more insight.

Breadth Requirements

In our department we're looking at the class requirements for Ph.D. students, and in particular breadth requirements.

I'll state clearly that my opinion is that breadth requirements are a good thing. Breadth requirements for Ph.D. students are like vegetables for kids -- they don't always like them, but they're good for them. When I was at Berkeley the breadth requirements were reasonably onerous and I think they were very positive for me (even if, as contemporaries will suggest, it seemed like I slept through most of them). I especially think it's good for theoretical people to have a background in many areas of computer science outside theory, and classes are arguably the best way to get that background. And certainly I would argue that people in systems need some theory in their background.

I'd enjoy hearing arguments from the other side. You can argue that breadth requirements in general are a bad idea, or specifically that theory people shouldn't have to take classes in other CS areas (they should be allowed to just do all theory!), or that systems people shouldn't have to take a theory class. Any EE readers or readers from other areas should chime in with arguments based on their experiences as well!

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?

Harry Lewis's book, Excellence Without a Soul

Since my colleague Harry Lewis is kind enough to stop by and post comments from time to time, I would be remiss not to encourage everyone with an interest in the education of college students -- in the broad sense of whether universities are and how universities should be teaching students to become adults -- to pick up his book Excellence Without a Soul: How a Great University Forgot Education (also now available in paperback as well). I highly recommend the book, and plan to give it to my daughters to read when they're teenagers so they're better prepared for the college experience.

The book takes a stark look at the directions of modern college education, painting a picture of increasing directionlessness at the leading research universities, using Harvard and Harry's experience as Dean of Harvard college as a backdrop. Whether you agree with it or not -- and I have to admit I found a strong resonance with most of the issues in the book -- it is definite food for thought, well-reasoned and well-argued through and through.

There are two very small points of criticism I can make with the book. The first is that while the book sheds light on a number of challenging problems, it frustratingly offers little advice in the way of solutions. However, I think this was quite intentional. Indeed, one of the points in the book is that for many of these problems, what is needed isn't a "solution", but leadership, discussion, and the building of a consensus within the university.

The second nitpick is that one issue raised repeatedly in the book is the invasion of the consumer culture in education. Students pay a great deal for an education, particularly at private institutions, and they expect to get what they pay for; Harry argues forcefully that this trend is not good for the education of students. It would seem to me that this should be another compelling reason why Harvard shouldn't charge for tuition, as it might lessen the "I paid for this" attitude of many students (and parents), but perhaps Harry believes that even if there was no tuition, the consumer attitude would remain.

Broadening the Teaching of Theory

Offhand, I can think the following primary "types" of computer science classes:

1. Classes specialized for graduate students in a subfield (e.g., theory, or usually the next level down, e.g. cryptography, pseudorandomness).
2. Classes for graduate students in CS.
3. Classes specialized for undergraduate CS majors.
4. Classes for undergraduates primarily in other sciences.
5. Classes for general, non-science undergraduates.

I think most CS professors naturally gravitate to teaches types 1 and 3 -- classes in their area of specialization. I think, as a community, there is generally at least some effort by theorists to broaden the scope of some at least classes to types 2 and 4. Certainly I try to encourage non-CS majors into my undergraduate algorithms class -- what scientist shouldn't be learning to think algorithmically? -- and to get non-theory graduate students to take my randomized algorithms and algorithms at the end of the wire courses. I suspect, though, as a community, we could be doing more. While personally theory seems less isolated within CS today to me than it did say a decade ago, there still seems to be plenty of bridges left to be built.

Perhaps more challenging is classes of type 5 -- classes for non-scientists. The question of how to design a science distribution requirement course for non-scientists is not specific to computer science, but in CS it perhaps especially challenging. Programming is often taken to be off-limits, since how much worthwhile programming can be taught to people who have never seen a computer program before? And theory seems to require too much math. Plus there is the age-old question of how to make it all relevant to non-scientists.

Harry Lewis co-designed a course, Bits, which I think is a great example of what's possible, and is the course I wish I could have designed, if I wasn't so busy teaching my regular classes. I enjoy this first paragraph from the course description:

This is a course about information for students who are not technically or mathematically oriented. It aims to explain the dramatic increase in the amount of information that is being communicated and stored, and the consequences for society of that increase in capacity.We are on the cusp of a revolution, potentially as consequential as the invention of printing or the replacement of animals by steam engines as the vehicles of transportation.The course aims to equip those who will determining policies, whether as legislators, corporate leaders, or ordinary citizens in their multiple roles, with an awareness of the choices that lie only a short time ahead of us.

I am also strongly biased in that Harry followed my advice, with much of the technical meat in the beginning of the course covering basic information theory, specifically compression and coding. (Note: I emphasize that Harry followed my advice, not that he took my advice. As far as I know, he always planned to structure the course this way, and it's just happenstance that his take on what was worthwhile matched mine. I'm pleased nonetheless.)

The course is an interesting mix of science, technology, and policy. The lectures are now apparently freely available online now that the course is over for those who want to see it. Someday, perhaps I'll get to design a course like this. I'd be curious to hear from others what other examples there are for CS-based courses with non-trivial technical content meant for non-science majors. (Jon Kleinberg's course new course comes to mind, but it really seems to be type 4, built for scientists, including mathematically oriented economists and sociologists.)

Set Your Own Price for Music

Tangentially related to my previous post on why Harvard should be free (but you pay later through donations), via the Machinist I've learned that Radiohead (some "music group" -- I'm old and out of touch...) is putting their new album online and letting people choose what to pay to download the album here. (More information for actual music fans is available from the Machinist in a follow-up.) This sounds like an interesting experiment, and I'm very curious to see how it works out for them.

Somehow it made me think, will the pick and play model of iTunes ever make it to universities? Imagine selecting your own collection of courses for your undergraduate or graduate degree, without being limited to your actual physical university; you could take say Kleinberg's Structure of Information Networks, Roughgarden's Introduction to Algorithmic Game Theory, Demaine's Geometric Folding Algorithms, and so on... of course, an appropriate payment mechanism would have to be designed, but the possibilities are exciting and frightening at the same time...

What Do Professors Do?

A number of times I've had undergraduates ask me, essentially, "What else do you do?", which sometimes is an honest interest in what else my job entails and sometimes appears to be a concern that when I'm not teaching them, I'm just sitting around my office thinking up new ways to torture them via problem sets or soaking up tuition money.

At a high level, I know what else I do: research, write papers, give talks, go to conferences, manage and work with graduate students, advise undergraduates, seek funding, sit on department and university and theory-community committees, review papers and grant proposals, act as editor for a few journals, serve on program committees, write letters of recommendation, deal with standard administrative paperwork, and... well, I'm sure there are a few other things as well that I've forgotten. Let's count blogging as part of my job, too. And I consult on the side. Come to think of it, it's a wonder I have time to teach. (That probably explains the students' question. They're wondering if I have 40 working hours a week, why isn't this class better?) Of course, I'm know I'm not unusual; all this seems like standard faculty stuff.

What I've been realizing lately I don't have a good handle on is how much time I spend on these various activities. It has seemed to me that in the last few years -- since getting tenure -- a lot more of my time is going to administrative duties than to research-style activities. If true, that fact along with my poor time-management skills seems like a recipe for disaster. So this semester, I'm going to try a little experiment, and try to track my time in a spreadsheet somewhere, to start getting a better handle on what's going on. And figure out what activities to cut.

Of course, I'm curious -- what are others experiencing? How much time do you think you spend on various activities, and is there a pre-post tenure change? What's the biggest impediment to research time?

The Argument for a Tuition-Free Harvard Education

After being subjected to the uncompelling arguments of those who think my videotaped lectures should be freely available, I thought I'd present my own wacky idea, backed up by an actual argument: that Harvard should stop charging tuition for undergraduates.

Strangely, this idea (which hit me back in '99, when I came back to Harvard, and which at least one Dean told me was unrealistic) does not seem so wacky today. Harvard has devoted significant new resources to financial aid over the last decade, so college is essentially free for families earning less than $60,000, as outlined here and here.

While some would view this in the mystical light of commitment to the educational mission, social good, etc., I'll be a bit more cynical and actually try to back up why this has been a good idea with an economic argument. More financial aid is just good business. Harvard's cost was limiting its access to the talent pool of graduating seniors; moreover, the resulting debt was at least a potential and probably real barrier to the future success of many graduates. Since Harvard's greatest asset (after its remarkably talented, and modest, faculty, and maybe also its endowment) is its reputation, losing top students because of cost or limiting their success through debt simply cannot be Harvard's optimal strategy. Increasing financial aid just makes good sense, especially given Harvard's resources -- it can take the short-term cost for the long-term good. (The fact that all this coincides with altruism is certainly fortunate, as naturally pretty much all the faculty really do have a mystical commitment to the educational mission, social good, etc.)

This argument, however, doesn't justify making Harvard free for all accepted, as I have proposed. In fact, one might think the other way -- that the rich should be soaked for as much as they can to help pay for the not-rich. My cynical but rational argument for a free Harvard undergraduate education for all is that, if tuition was free, but Harvard then encouraged people to donate what they thought their education was worth -- say, perhaps, a small percentage of their annual income for life -- in the long run, they'd more than make up the tuition loss with increased funding of the endowment (thanks to the power law that is the wealth distribution). This is not a tax, but it is based on the idea that your college education is related to your future earnings, and giving back a percentage of those earnings is an arguably fair way to pay for that education.

Harvard might not even have to wait for the long-term to get the benefit. Indeed, imagine Harvard's next fund-raising campaign beginning with the announcement that after the campaign, as long as their goals were met, Harvard would be free for all undergraduates! What PR! What kind of donations would that bring in immediately!

Longer term, I would suspect the benefit would be even more. The pay-what-you-think-is-fair approach has been tried in some restaurants (see the SAME cafe, or the One World Cafe), and many museums have no fee but "suggested donations" at least part of the time, so this approach is not entirely unprecedented. In Harvard's case, I think the mix of guilt, altruism, and competition would push wealthy alumni (and wealthy parents of students) to give much more. (So you see, I am soaking the rich -- I just think you should wait to soak people until after they are rich, and inspire them to give generously, rather than bill them for a tuition payment.)

There are all sorts of possible side-benefits. It could work out that by moving from a system of tuition to voluntary donations, there would be an immediate jump because the donations, as opposed to tuition, could be made with pre-tax instead of post-tax money. (Note: I am not a tax attorney...) Students not laden with debt may prove more entrepreneurial (which besides helping the economy might lead to bigger donations down the line), or perhaps might take on more public-service oriented employment.

I can see why this might not have been tried elsewhere -- there's a lot of up-front cost while waiting for future payoff. Even for Harvard, perhaps the risk of too many free-riders is too large, although I doubt it. Harvard could also label the plan an experiment, suggesting that after some time tuition would have to be re-instituted if donations didn't keep pace with projections, to limit the risk. Perhaps the biggest negative is if Harvard tried this unilaterally, it would be seen as an unfriendly neighbor to all the other colleges. Still, I can't help but wish this idea would be given a try. Perhaps it could change the way we talk about funding education in this country, moving increased resources to our education system. I'd like to see Harvard lead the way in this regard.

Advertising: Anyone Can Take My Randomized Algorithm Class

Next semester, I'm teaching my class on randomized algorithms and probabilistic analysis, based on the Mitzenmacher/Upfal book. Harvard, like many universities, has an "Extension School", and I offer my courses through the distance education program. Basically, my lectures get taped and put online, I put the assignments online, and you or anyone who pays the Extension fee can take the course. While I'm sure my teaching performance on video is reminiscent of say an early Mel Gibson or perhaps a Moe Howard, I personally still don't think distance education is as good as "being there" by any means (at least, not yet...). But it offers an opportunity that people may not otherwise have.

The course is taught at the level of an introductory graduate class, meant for non-theorists as well as theorists. These days, who doesn't need to know randomized algorithms and probabilistic analysis? If you know someone, for example in industry, who might like to take such a course, here's the link to the bare-bones syllabus.