Deletion Channel Pointer : Kanoria and Montanari

For those half a dozen of us in the world who care about the deletion channel (and perhaps I'm overcounting), I'm a bit late in pointing to the now available extended version of the Kanoria and Montanari paper from ISIT last year.  It follows a path laid out by my student Adam Kirsch by looking at an information theoretic characterization of the channel, but then uses a perturbation analysis to get the right degree distribution and very tight bounds as the deletion probability goes to 0.  There's still plenty we don't understand about the deletion channel, but this paper moves us forward nicely.

Practical Uses of Induction

See!  Who says this stuff isn't useful....

Annual Facing the Reviews

Teaching reviews for spring (Algorithms and Data Structures) came in today;  time to face the music once again.

Actually, this year, my numbers were up substantially;  still room to improve, of course, but unlike the last two years, they didn't make me cringe.  If it seems surprising that my teaching numbers would go up when I'm now busy being Area Dean, it seems clear that the credit actually goes to the class.  This was easily the best class of students I've had in several years -- a really strong bunch.  I think the delta in scores reflect their capabilities more than anything else.  

It's always interesting to see the contradictions embedded in the responses.  This year, I decided to take advantage of the opportunity to ask specific questions, and asked the class if they preferred the written assignments or programming assignments (and why), and which lecture they would want to see removed/not want to see removed.  It was almost 50-50 for the written/programming assignments, with a slight edge to written assignments.  And it seems like for every person who really liked the primality testing/RSA lectures, or the least common ancestor/suffix tree lectures, or the lecture on heuristics, there's another who would remove the exact same things.  This is entirely consistent with feedback I've gotten directly over the years.  You can't please everyone.  (Sorry, that should be "I can't please everyone."  I shouldn't speak for you.)   

A number of students commented on how valuable the material was.  The negative version of this is that the course is "CS broccoli" ("you really ought to take it, but you probably won't enjoy it much"), but the positive version is much more pleasant -- the class really shapes how you think about problems, and is IMPORTANT knowledge for CS majors.  I made a point this semester of really emphasizing the point that correctness is a design consideration that can be traded off with other performance metrics like time and space, and multiple students commented specifically on finding that idea exciting.

On the downside, I'm still intimidating to some students (on the other hand, several others took me up on my open invitation to go to lunch with them this semester), the exams are too hard, and they want more feedback.  And there are too many math majors coming in and messing up the curve. 

How is this last problem handled elsewhere?  It's almost tempting to have a CS theory course for CS majors and a harder course for math majors.  Is it fair to have an "honors track" within the class for the math types and modify the grading curve accordingly?   

If you're from the class and you've stumbled on this -- congratulations on making it through.  Even if your grade wasn't as high as you might have liked, please don't let it get you down.  As you move on how you do on problem sets and timed tests is less important;  it's what you can accomplish with the knowledge you've gained.  So accomplish something great, and come back and show off to me -- I'll be eager to see it!

NSF Bows to Blog Pressure (Tongue-in-Cheek)

As some of you may recall, I accused the NSF of being "misguided" in changing its graduate fellowship policy to effectively disallow teaching.  

So I was please to get home tonight and see that some students had forwarded me the following e-mail from the NSF:

Dear Colleague:

The purpose of this memorandum is to inform you of recent developments
in the NSF Graduate Research Fellowship Program (GRFP).   There was a
recent change in policy that NSF has decided to reconsider.  In
particular, the policy concerns what can be expected of Fellows during
the three years they receive NSF funding (on tenure).  NSF has decided
to reinstate the previous policy with respect to this issue while
further study is conducted to inform this and other GRFP policies.
The policy that will be in effect during the 2011-2012 Fellowship Year
is an updated version of the one described in the 2009 Guide (NSF
09-62), which is as follows:

Each Fellow is expected to devote full time to advanced scientific
study or work during tenure. However, because it is generally accepted
that teaching or similar activity constitutes a valuable part of the
education and training of many graduate students, a Fellow may
undertake a reasonable amount of such activities, without NSF
approval. It is expected that furtherance of the Fellow's educational
objectives and the gain of substantive teaching or other experience,
not service to the institution as such, will govern these activities.
Compensation for such activities is permitted based on the affiliated
institution’s policies and the general employment policies outlined in
this document.

You can refer to the 2011 Guide (NSF 11-031) at
http://www.nsf.gov/publications/pub_summ.jsp?ods_key=nsf11031 for
further information about teaching, research, and other work
activities during tenure years.

We apologize for confusion these changes may have caused, but look
forward to working with you to ensure the GRFP is as effective as
possible in helping to ensure the vitality of the U. S. scientific and
engineering workforce.

Sincerely,

The Graduate Research Fellowship Program Office
Division of Graduate Education
Directorate for Education & Human Resources
National Science Foundation

Now of course I wouldn't want to claim that this about-face was all due to my blog post.  I'll just let you draw your own conclusions.

More seriously, I'm glad they're pausing and getting some more input on the issue.  As I like to repeat often, the NSF is a wonderful institution, and it's nice to see them showing willingness to revisit this issue, given my opinion that their new policy was questionable in terms of its benefit to students.  I imagine many institutions encompassing large bureaucracies would never manage to reconsider a decision like this, so it is to their credit.

Serving Non-Majors in CS Classes

At the end of the year, I gave a short in-house presentation highlighting some aspects of the state of CS at Harvard.  In gathering data, one thing that struck me -- and I highlighted in our presentation -- is that most of the students taking our classes are not majoring (or, in Harvard-speak, concentrating) in computer science.

This shouldn't have been a big surprise -- if you look at the number of concentrators and then do the math this pretty much had to have been the case -- but it was a surprise to me how large and widespread the effect was.  Sure, our intro programming classes are filled with non-majors.  That's not hard to figure out, given we had about 500 people taking our first semester intro programming class this year.  We have LOTS more economics majors than CS majors in that class.  But even in my Algorithms and Data Structures, which I think of as core CS, only about 1/2 the class was CS majors.  (Lots of math, applied math, physics, as well as several from other majors.)  In some of our classes that are designed more to be outreach classes, like our courses on visualization and user interfaces, only about 1/3 of the class is CS majors, and others are from all over the campus.

This is, I think a great thing.  I'd like Harvard applied math, math, physics, engineering, government, statistics, sociology, economics, and English majors to leave Harvard with some strong foundations in CS.  The question is, how should we in CS at Harvard think about it?  One idea is that there's certainly room for us to attract more majors into CS at Harvard, and we're certainly working on that.  But another idea is that we should be looking for opportunities to teach classes that are both good for our majors and can appeal broadly to others as well.  Harvard offers something like minors (call "secondaries") which requires only a small number of classes;  another measure of success for us would be if we can significantly increase the number of CS secondaries.

Along these lines, David Parkes will be offering his version of an undergraduate Econ-CS course for the first time next year.  I expect it will be a very popular offering, for CS majors and others.   

 

Daily Updates

Getting slowly back into blogging, some happenings from the day.

I've gotten a couple of nice notes from students saying they learned a lot from my class this semester.  To any students reading the blog, I encourage you to send such notes.  It will make your prof feel maybe it's all worthwhile.

A colleague pointed me to a nice example of a real-world application of Bloom filters.  

I hosted a large dinner at my house a while back as part of recruiting our new faculty.  Now I'm being told that as Harvard is tax-exempt I was supposed to give the caterer a form with Harvard's tax-exempt status and I need to get them to refund the tax (or I won't get the tax reimbursed).  It's not a big deal, but I just love university financial offices and their fun rules.  (How I'm supposed to know this, I don't know.  When we take a candidate to dinner, we don't get to claim tax-exempt status, but apparently for a meal catered in your home... sigh.)  I'm sure it will get worked out.

Back to Blogging

I've given my final, and have grades ready to submit.  The semester is over! 

Over the summer I may do some blogging again, as I may have time for it.  I was noticing that on my calendar, I now have empty days ahead, something I haven't seen for a while.  I'm looking forward to those. 

To start off, I've just finishing registering for FCRC, and it seemed apropos to complain about how expensive it was.  I'll be there about 4 days, for 2 overlapping conferences (that last 5 days), and it costs nearly $1000 in registration fees. 

But then I looked at other conference prices.  Int'l Symposium on Information Theory 2011 is $725.  That does include several lunches, a banquet, etc., and it is a 5-day conference.  SIGCOMM 2011 is $625, again with banquet, 3-day conference.  Not sure about lunches. 

FCRC still looks expensive, but perhaps not ridiculously so.