Why we do algorithms wrong

So by we, I mean my school’s CS department. After only a few meetings with my advisor here, I see the difference between the teaching/advising styles and why one is far better than the other. In our department, the algorithms class pretty much proceeds in a manner than an algorithm is taught, maybe there is some discussion about the run time of it, and then the students usually have to implement it as an assignment. The textbook used is the Cormen textbook, which is pretty much like the webster’s dictionary of algorithms. So what are we missing?

First, we are missing the very important step of the proof of the algorithm. Yes I know that most students don’t care for proofs and find them difficult and useless, but too bad. The fact of the matter is that it is hard to prove the correctness of algorithms, but that is exactly what we need. The proofs are not necessarily important in the content of the proof in itself, but the process that one would go about reasoning the correctness of an algorithm. If you do enough proofs, you start to develop an intuition for the correctness of an algorithm long before you even finish it. We could all benefit by saving time on an approach that wont yield a correct answer.

But the most important thing that we are missing is the emphasis that the algorithms that are taught should help us develop an intuition on how to go about coming up with an algorithm. I know plenty of people who have gone through our algorithms course but still have little idea about how to start developing an algorithm for a Topcoder problem. This is because we teach our class more as a reference class for algorithms, not to teach the paradigm. A good manifest of this concept is the textbook used. Sure, the Cormen book is an excellent reference if you already have a great understanding of all the math and you are looking to read some material on an individual problem. But it doesn’t do that well actually teaching the concepts when compared to the Kleinberg algorithms book or the Papadimitrou/Vazirani book. Those books actually teach the concepts and walk through the development of these algorithms. The Kleinberg book also does a great job of showing how to arrive at correctness proofs (it even teaches about commonly used proof techniques such as exchange arguments). Plus the books are generally easier to read, which is a big plus when starting to teach more advanced concepts such as approximation and randomized algorithms.

I realize that our department isn’t hoping to raise the next generations of algorithmists or send people to do work in CS theory, but we should be trying for this approach. Even if it does go over the heads of most students, there is no harm to trying it this way since they can always go back to reading the book for all the answers they need. If our students are too lazy/incompetent to get all their answers from the book and still need a professor to hold their hand in the class, we have a bigger problem than we know.

Hopefully I end up with a really solid foundation for doing advanced work in algorithms after this summer. I am interested to see how our advanced algorithms seminar is going to turn out. I have some doubts, but I’ll keep those private (as if publishing a thought really constitutes it as a public thought).

REU 3.0

Well, here I am at my third and final shot at making an REU worthwhile. My first one was a great learning experience, but I really didn’t know enough at that point to really take advantage of the “research” opportunity. I think I was ready to do some serious stuff for the second one, but it turned out to be a terrible experience in almost all facets. This one is starting strong. We have 13 students so far (we have one more to come) and we seem to have a good social dynamic going on. Im excited to see where the summer leads us around LA.

My project this year is infinitely better than what it was last year. My chief complaint from last summer is that my advisor treated me like a small child with minimal knowledge of what programming was; my advisor this year says he’s going to treat me like a 5th year PhD student who has passed all exams and has read all the literature unless I tell him to slow down and explain something. From our early meetings, its pretty clear that I will be taking advantage of the “slow down and explain something” option quite frequently.

So I’m getting my start in CS theory research this summer. We are considering the problem of maximizing the spread of your influence on a graph. We have a model where at each time step, a node will choose one of its neighbors at random and change to whatever color that node is in the next time step. Before this process begins, you are given an amount of money M that you can spend on nodes to color them your color, assuming that each node has its own activation cost. We would like to find a set of nodes S, such that the total initial cost of those nodes < M that will maximize the expected number of nodes that will be your color after T timesteps. This problem is motivated by the case where a company is looking to pay some people to initially adopt their product in order to spread the adoption of their product throughout the network. Two natural examples of this would be publishers giving out free textbooks to professors in hopes that they will adopt the textbook for their class and other professors will do the same after seeing the original professor use that textbook or paying certain people to start using a social networking site (like Twitter) in hopes that others will join because of the influence of those people.

When we are done researching that simple version, we will explore what happens when there are two companies, A and B, with the same finite amount of resources and nodes will adopt technology A or B with probability proportional to how much money each company has spent on them. In this scenario, I have already looked at a simple probability function where A has already made all of its moves and found an optimal algorithm for B (of course, it is not a polynomial time algorithm, but its better than the “try everything” approach). In the future, we are going to look at equilibria in the game. That is, if A knows how B will react given a strategy for A, what can player A do to preempt B and choose a strategy that will be worse for B when B reacts to it.

There is a fair bit more technical detail to what is going on and I have much more to learn, but I am really enjoying what I have done so far. Hopefully, it will remain that way.