[Below is a guest post from Sanjeev Arora on his redesign of the traditional graduate algorithms course to be a better match for today’s students. –Boaz]
For the last two years I have tried new ideas in teaching algorithms at the graduate level. The course is directed at first year CS grads, but is also taken by grads from related disciplines, and many advanced undergrads. (Links to course homepage, and single file with all course materials.)
The course may be interesting to you if, like me, you are rethinking the traditional choice of topics. The following were my thoughts behind the redesign:
- The environment for algorithms design and use has greatly changed since the 1980s. Problems tend to be less cleanly stated (as opposed to “bipartite matching” or “maximum flow”) and often involve high-dimensional and/or noisy inputs. Continuous optimization is increasingly important.
- As the last theory course my students (grad or undergrad) might take for the rest of their lives, it should somewhat fill in holes in their undergraduate CS education: information/coding theory, economic utility and game theory, decision-making under uncertainty, cryptography (anything beyond the RSA cryptosystem), etc.
- Programming assignments need to be brought back! CS students like hands-on learning: an algorithm becomes real only once they see it run on real data. Also, computer scientists today —whether in industry or academia—rely on subroutine libraries and scripting languages. A few lines in Matlab and Scipy can be written in minutes and run on datasets of millions or billions of numbers. No JAVA or C++ needed! Algorithms education should weave in such powerful tools. It is beneficial even for theory students play with them.
Sample programming assignments: (a) (compression via SVD) given a 512 x 512 grayscale image, treat it as a matrix and take its rank k approximation via SVD, for k=15, 30,45,60. Use mat2gray in matlab to render this new matrix as a grayscale image and see what k suffices for realistic recovery. (b) You are given S&P stock price data for 10 years. run online gradient descent to manage a portfolio (Lecture 16), and report what returns you get with various parameter settings.
Students are allowed to do a final project in lieu of a final, and many choose to apply algorithms to some real world problem they are interested in. Sample projects are also listed on the course page.
I welcome your comments, suggestions, and links to other relevant course materials on the web!
Windows On Theory 
Sanjeev, the course looks fantastic. And it’s great that the materials are high-quality and accessible. I know people have been making similar efforts elsewhere (e.g., this course at Berkeley: https://www.cs.berkeley.edu/~satishr/cs270/sp13/). It would be helpful if people posted more examples in the comments (if they exist).
Having just a few example courses makes it vastly simpler to implement a related course for the first time. And it seems that the majority of junior faculty teaching grad algorithms are facing this dilemma.
Thanks, James!
By the way, this same course (COS521) used to be aimed at theory grads only until 2013. Those wishing to teach that version should look at http://www.cs.princeton.edu/courses/archive/spring13/cos521/
or
http://www.cs.princeton.edu/courses/archive/spr12/cos521/
The new version is a bit easy for our theory grads, though some have told me they learnt a fair bit anyway: different topics and emphasis, plus the simple programming assignments.
there seems to be a split in CS field where some think that it can be done seriously without programming, possibly the Djikstrian view, to whom the quote is attributed about “CS is not about computers just like astronomy is not about telescopes”. then there are others like Kuhn/ Sedgewick/ Zeilberger et al who are proponents of more applied science. this yin/ yang-like split will probably forever be with CS. must admit to being a huge fan of the applied side only because it seems like it might be at an underrepresented point in the pendulum swing. although Big Data & supercomputers are putting some major dent in that these days. thx so much for going out a limb somewhat and advocating the applied side! need to blog on this again sometime & defn cite this along with lots of other great stuff 😀
some more musings on experimental/ empirical CS
fyi here is another outstanding ref (but seemingly not well known) that seems to strongly mirror some of your own thinking about shifts in the field. apparently Hopcroft has also contributed. it seems to be a draft version of a book, not sure if it ever made it to publication, but it sure needs to.
CS theory for the information age / CMU, Kannan, Hopcroft et al
I must acknowledge that the Hopcroft-Kannan notes (which have been circulating for several years) were a wonderful inspiration for me too, especially for the “big data” parts of my course.
I second James that this indeed looks like a fantastic course. Satish’s course seems too intense for new graduate students.
I’ll include some info I wrote in response to a private query. There was no special set up for the programming assignments. The relevant infrastructure (matlab, python etc.) already exist in most CS depts and universities. I didn’t even code up the homeworks myself before assigning them. Students are resourceful and find whatever they need (or they ask each other, since collaboration is allowed).
In general, learning from the young is the easiest way for us old codgers to get into all this.
Sanjeev, I like your choice of topics but I was wondering if you thought about including a lecture on Interior Point Methods. The essence of IPM is quite different from everything else that you currently discuss, and it is at least as “canonical” as all the other concepts you have included. Historically the philosophy of IPM has also been somewhat underused in TCS (though of course this is rapidly changing), and I think it is important for the new generation to view this technique as something as classical as gradient descent or the ellipsoid method.
Hi Sebastien
That is a good suggestion. From now on I plan to rotate in a few new topics each year, so that I can have good lecture notes on them. Truly the total # of good topics is large.
That said, it seems that algorithms with “log 1/\epsilon” convergence are somewhat less relevant to general computer scientists; it is more the domain of experts. (You mentioned
“TCS” in your comment, but note that this course is geared to general CS students. )
Do you agree?
Hmm your comment on the log(1/epsilon) is interesting. Note however that it applies to the ellipsoid method too.
In any case I feel like the idea of taking a “shortcut” by going “inside” the convex hull of the possible solutions is such an inspiring idea that to me it stands on the same level as SVD or Nash equilibrium.
Reblogged this on machinelearners.
It depends. Are you trying to produce someone who can use current tools? Or in my area, I teach people to know the mathematics behind the game to have the freedom to design anything? Those are two very different things: 1. are you teaching a technician 2: are you teaching a scientist and a mathematician. One must simply decide the goal. What say you?
This is an aside: some have made note of Hopcroft. Pretty much anything Hopcroft has to say especially about practical computer science might be worth reading, just saying