Wednesday, December 04, 2013

Algorithmic Growth (Class Size)

Pre-term planning numbers are in for Harvard, and it looks like the undergrad Algorithms and Data Structures class has about 175 people planning to take the course.  That's a huge jump again over the last few years (where it's jumped from the 50s to well over 100).  I imagine the growth is spurred by our ever-increasing enrollment numbers in the intro classes, as well as the fact that it's being taken over by a younger, dynamic, new faculty member.  (Go Jelani Nelson.  I can't help but think some number of students were waiting for me to go on sabbatical...)

These numbers are usually within plus-minus 10% of the final, though there's higher variance when new instructors take over.  If 175 became the steady state class size, it would mean a bit over 10% of the students at Harvard would take Algorithms at some point.  I don't think I ever expected that when I started. 

If we can get the people resources, at some point we'll probably want to start breaking this up.  One direction is to make an "honors" class that would cover more/harder material more rapidly.  (We're thinking of making this an "honors theory" course, that would cover both complexity and algorithms -- 2 classes packed into 1.)  The Math department here has done this very successfully, separating out the future Putnam winners from other students early on.  A benefit is it leaves the remaining students happier as well, as the curve-breakers remove themselves from the regular class.  Another possibility is to do an algorithms style class designed for non-majors, that would bring in more people not currently taking algorithms as well as some of those in the current course.  There are "topics" classes like this -- the Easley/Kleinberg book Networks, Crowds, and Markets: Reasoning About a Highly Connected World is algorithmic and seems to allow an instructor to choose a desired mathematical level from a broad range -- but I don't really know of examples of something more like a standard algorithms/data structures courses designed for a broader audience than for CS majors.  I'd be interested in pointers to and anecdotes about experiences in such classes if they exist. 

6 comments:

Arjun Narayan said...

Michael Kearns' class on "Networked Life" seems to be somewhat down that alley of a softer introduction to algorithmic thinking... http://www.cis.upenn.edu/~mkearns/teaching/NetworkedLife/nwlife12.html

I'm not sure how relevant it is though to algorithms per se, than to quantitatively thinking about ideas that have been bouncing around in the social sciences for a while (Schelling models, Six Degrees of Separation, etc.). However, if you are thinking of something down that path, Michael's probably someone you would want to talk to, as he has taught it over nine iterations since 2004.

Anonymous said...

Algorithms and Data Structures attracts about one-third of all Princeton undergraduates. It covers the basics like sorting and searching, as well as graph processing, string processing, and a gentle introduction to intractability.

Meena said...

If the audience is non-cs folk, how about
Algorithms unplugged
http://www.springer.com/mathematics/book/978-3-642-15327-3
?

I don't think I've seen a course based out of this book, but I think it is feasible.

Michael Mitzenmacher said...

Anonymous #2 -- is that really 1/3 of all undergraduates, or 1/3 of all undergraduates in the college of engineering?

Meena -- I like the idea of an Algorithms Unplugged type course. I'd have to think about coherency -- what are the big lessons I want students to get out of the course, and can the topics be suitably laid out coherently to cover the themes -- to make sure it wasn't just a hodgepodge of things. And I'd have to find the appropriate breadth/depth tradeoff. Really nice idea for a starting point though.

Anonymous said...

@Michael
Yes, 1/3 of all Princeton undergrads will take the course at some point - 400+ a year and still increasing in popularity.

Luay Nakhleh said...

Dear Michael,

We've recently introduced a new freshman-level course, called Algorithmic Thinking, that is now required of all CS students at Rice University. About 140 students are already registered for Spring 2014 in the course. Again, this is a freshman-level class, but it emphasizes efficiency of algorithms (asymptotics), and introduces students to how to take a problem from a certain domain (e.g., biology), model it formally (what is the input? what is the output? etc.), think about an algorithm, analyze it, iterate (until a reasonable algorithm is devised and implemented). I cover various algorithm design techniques (divide-and-conquer, greedy, reductions, dynamic programming, iterative improvement,..). The applications include graph partitioning (community detection a al Girvan-Newman), biological sequence alignment, and phylogeny reconstruction. If you're interested, I can email you some sample homework assignments.