# What are some good follow-up courses to CS 224 (Advanced Algorithms) at Harvard?

envy!

Answer by Jelani Nelson:

I would check out the courses at http://toc.seas.harvard.edu/cour… and http://toc.csail.mit.edu/Who%20i…. Both only show up to Fall 2014 though. For Spring 2015, here are some courses I'm aware of at Harvard which are related to the Theory of Computation (TOC) that a CS 224 alum might enjoy:

Salil Vadhan: CS 225 (Pseudorandomness)

Michael Mitzenmacher: CS 223 (Probabilistic analysis and algorithms)

Les Valiant: CS 229r (Special topics course: biology and complexity)

Yaron Singer: CS 284r (Topics on computation in network and crowds)

Vahid Tarokh: AM 106/206 (Applied algebra)

David Parkes: CS 186 (Econ & computation)

What are some good follow-up courses to CS 224 (Advanced Algorithms) at Harvard?

# For how many years did you study advanced topics in algorithms before you really became productive as a researcher?

addicted!

Answer by Jelani Nelson:

Here's an answer that is perhaps too long-winded…I'm sure it differs from person to person, but my experience was as follows. First off, I entered MIT freshman year not knowing much about computer science, and also not knowing what a mathematical proof was. I knew some C/C++ from teaching myself in my senior year of high school, and some HTML from teaching myself in 8th grade, but that was it. I also had no idea what research was.My first exposure to proofs was Freshman year, taking the theory track for single/multi-variable calculus and differential equations (18.014, 18.024, and 18.034 — see Jelani Nelson – CLASSES ). My first exposure to algorithms was in my sophomore Spring algorithms course (6.046). I liked the class, but at that point is was just one class of many and I didn't think much more about algorithms for at least another year. My next course in theoretical computer science was then a graduate cryptography course (6.875) in my junior Spring, which I really enjoyed. At that point, I thought I wanted to do cryptography.At the same time, I signed up for a TopCoder account near the end of junior year (in May). I also signed up for an account on the USACO training gateway, and on the websites of several other online judges. A couple friends of mine at MIT, namely Hubert Hwang (TopCoder: antimatter) and David Pritchard (TopCoder: daveagp), were really into TopCoder at that time and I got into it due to their influence. It is quite easy for me to get addicted to computer/video games, and I viewed solving problems on these websites as a game. Summer 2004 I probably spent over 8 hours a day solving algorithmic exercises on various websites. I would say this phase of my life was quite pivotal. After about 2 years on TopCoder, algorithmic thinking became second nature.

I also took a few graduate courses in algorithms my senior year: Advanced Algorithms (6.854), Randomized Algorithms (6.856), and Advanced Data Structures (6.897 at the time, now 6.851). They all had final projects, but I was quite busy taking 6 classes per semester so I didn't have much time to launch any serious research efforts. Luckily Erik Demaine as part of 6.897 had some "open problem solving sessions" which I attended. These were quite fun, and as part of one, a team of 7 of us solved some data structure problem on dynamic ham sandwich cuts which we published that summer in CCCG. It was not a major problem, but I believe one of the goals of these sessions was to introduce youngsters to research in theoretical computer science. It worked on me; I think it was both a good confidence booster, and simply a good way to get my feet wet. (It was also my first co-authored paper with Daniel Kane, who I ended up working with later on quite a few projects during graduate school.)My senior Fall I also applied to (two) graduate schools (saying I wanted to do cryptography). I had a 5.0 GPA at that point but zero theory research experience, and I got rejected from both. (I also can't really even remember why I applied, considering that at that point I didn't really understand what a PhD was …). After senior year I did a one-year Masters supervised by Bradley Kuszmaul and Charles Leiserson, focused on external memory and cache oblivious data structures. Since I was only taking two classes per semester, I had much more time to focus on research. At some point Bradley and I came up with an update/query tradeoff for external memory predecessor, but then Jeremy Fineman pointed out it had been done in a SODA several years prior. We worked on other stuff though, which led to a SPAA paper a year later on two cache-oblivious solutions that aimed to get much better update performance while still having good query. My main contribution was in deamortizing the "cache-oblivious lookahead array" (COLA) in that work. So, I think by this point, I had the ability to do some theory work.I didn't really find my current area though (streaming/sketching/dimensionality reduction/etc.) until my second year of PhD. My first year I tried to do some more cache-oblivious stuff but didn't really get anywhere. My second year, in the Fall, I took a course by Piotr Indyk on streaming and sketching. I did a final project with Krzysztof Onak and Nick Harvey on entropy estimation in data streams. We had some non-trivial progress by the end of the course, and we kept working on it intensely in the Spring. We managed to get a pretty good algorithm by the FOCS deadline, so we submitted and it got accepted. That was my first paper in the area that became the focus of my thesis.

# sort list via selection sort

struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode *insertionSortList(ListNode *head){ if (head == NULL || head->next == NULL) return head; ListNode *cur = head->next; head->next = NULL; // set up the termination condition while (cur){ ListNode *nxt = cur->next; ListNode * brk = head; if (cur->val < brk->val) { cur->next = brk; head = cur; } else { while (brk && brk->next && brk->next->val <= cur->val){ brk = brk->next; } cur->next = brk->next; // propagate the NULL, a smart move! brk->next = cur; } cur = nxt; } return head; } };

# What innovations in CS theory from the last 10 years have had an impact outside of academia?

Answer by Jelani Nelson:

I''ll add two more:

Algorithmic Game Theorystudies optimization problems in which there are strategic agents whose rationality you have to take into account. For example, you're Google and want to design an ad auction system that optimizes your profit, taking into account that advertisers will try their best when using your platform to game the system to maximize their utility. A founding paper in this area of "algorithmic mechanism design" is [1].Faster Numerical Linear Algebra via Randomizationhas been a recent development that's spread fast. Imagine you have a huge matrix, e.g. rows are users and columns are products, and an entry is that user's rating for that product. Most entries are empty, since most users don't rate most products; e.g. the Netflix matrix is only ~1% filled in [2]. Predicting unfilled entries is known as the "matrix completion" problem and is at the heart of some recommendation systems. Other problems people care about for large matrices include regression and principal component analysis (PCA). Earlier research showed how to use non-uniform sampling to get some speedup, but Sarlos showed [3] how to use fast random projections (a concept mentioned in another answer by Ghalib) to obtain speedup, which I think really changed the game. Since then, Clarkson and Woodruff showed [4] how to solve these problems even faster using ideas related to Sarlos (in time dominated by the number of nonzeroes in the matrix, which as mentioned before is often much smaller than the size of the matrix), and IBM has been putting together a linear algebra library based on these ideas [5].[1] Noam Nisan, Amir Ronen: Algorithmic Mechanism Design. Games and Economic Behavior 35(1-2): 166-196 (2001)

[2] Yunhong Zhou, Dennis M. Wilkinson, Robert Schreiber, and Rong Pan. Large-scale parallel collaborative filtering for the Netflix prize. In Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM), pages 337–348, 2008.

[3] Tamás Sarlós: Improved Approximation Algorithms for Large Matrices via Random Projections. FOCS 2006: 143-152

[4] Kenneth L. Clarkson, David P. Woodruff: Low rank approximation and regression in input sparsity time. STOC 2013: 81-90

[5] Sketching Linear Algebra Kernel

What innovations in CS theory from the last 10 years have had an impact outside of academia?

# Online Algorithms: Paging @ MIT

# How did you realize that you wanted to become a professor?

Answer by David Karger:

For me it was always in mind as an option, since my grandparents called me "professor" from age 10 or so. But I never assumed it would happen, nor considered it my only option. I recognized early that I enjoyed puzzling over creative technology problems. I didn't do any real research as an undergraduate but I enjoyed my problem sets and even more my independent projects. When I thought about the jobs that would let me work creatively in technology, most of them seemed to involve a graduate degree (at that time—some in today's startup culture argue it's no longer important). So I went there thinking it might be fun to be a professor, but that there were lots of other fun alternatives in computer science that I could pursue with a PhD. When it came time to apply for jobs, I

stillwasn't sure I'd be a professor, because I had no idea whether I'd get hired. I did decide that I was only interested in working at top research universities, and if I didn't get a job there I'd look for work in industry. Fortunately I lucked out. At this point I'm certain that it is indeed exactly the right job for me.But that leads to the advice bit of this post: do not plan your life around the idea of becoming a professor. There are very few jobs at the top universities, and you need a lot of luck (unless you are absurdly talented) to achieve the kind of research results that get you noticed and hired there. You need a backup plan, or more accurately a "likely plan". Chart a course towards a kind job that you'll like and that you're pretty confident you can get. Hopefully, it will keep open the possibility of academia if things break your way. But if your plan is academia or bust, you're taking a really big risk with your future happiness.