Hello Hacker News and Reddit! Holy crap there are a lot of you…
There are two approaches to teaching a class entitled “Algorithms”. One is to teach a survey course where you are told about a bunch of algorithms and how they work. Tests in such a class could be passed with brute force memorization and little understanding, and would definitely be easier than the tests in the second type of course, “How to Design Algorithms”, where the questions are asking students to design and analyze something new every time. My tests this term were definitely in the second category, which made them much harder than they would have been with the other approach. But I think the second category is what should be taught! Computers are for remembering things, people are for creatively discovering new things. In order to teach people to design algorithms, we do have to show them how some famous algorithms are designed, but it’s a question of course focus. Do we emphasize how the algorithms work, or the design principles that led to their creation? As my father often told me*:
The person who knows “how” will always have a job, but the person who knows “why” will be their boss.
I teach the “why” stuff because the “how” stuff is fundamentally boring. It’s well-solved, and, when confronted with that situation in the field, simply sit down with the algorithms book and translate the pseudocode into real code. Or, more likely, get the real code that someone else wrote and use that! But only people armed with answers to the “why” questions will be able to handle new problems in new scenarios. This is why lots of CS job interviews ask tricky puzzle questions. It’s kind of insulting, but it’s also trying to assess whether or not you can solve new problems in new scenarios. They ask these questions, because being able to come up with new solutions to new problems is the key skill for a programmer who is being asked to do non-lame** work.
Computer Science (and Algorithms in particular) is the art of doing new computational things. Because if we did them before, then we should just use the old solution and move on. If a problem can be just be memorized and regurgitated, then solving it can be programmed (and not just the solution to the given problem, but also the meta algorithm of translating from problem to algorithmic solution). If finding the solution to a problem can be programmed, then training students to do so is largely a waste of their brain space, because the right solution would be “get a computer to solve it”. That’s why questions in a course about “How to design algorithms” will necessarily be tricky. Because we will need to almost always ask questions which need a (currently unprogrammable, but still real) algorithmic intuition that cannot be reduced to a series of steps.
We can’t ask: please write down an algorithm to sort a list of integers in O(n lg n) time using only a constant amount of extra space (hint: Heapsort), because solving those problems is just a cache lookup. Memorize the book and you’ve got your answer! It makes no sense to require computer science students to pretend that they have to remember everything when the whole point of much of computer science is to use these powerful machines to aid us in thought and memory. I suppose an alternative is allowing students to use the Internet when answering my test questions — that’s a more “real world” environment — but in that case I would be unable to tell the difference between a problem solver and a good searcher of previous solutions. And I want to gauge how people perform when they encounter new unsolved problems, not how well they google. I could ask problems that I can guarantee nobody has ever seen or solved before, but that still doesn’t solve the problem of students quickly getting an answer via nerdsniping a message board. Also, making students do new research to pass an in-class test is just dumb. Worst of all, coming up with algorithms questions hasn’t yet been automated, and I can’t see any reasonable algorithm for doing so. Therefore, for the time being, both the design and answer of questions on algorithms tests will necessarily require an algorithmic intuition as well as just knowledge of the subject. And that means that coming up with good questions is tricky, and that so is the process of solving them.
* This is true, he actually told me this many times.
** I use non-lame/lame to denote the difference between work where a much dumber person with knowledge of the same facts could/couldn’t do the job. I would hope that most people want a non-lame job, although in the current economy one can’t be too picky. And there are always some people who are motivated purely by money and no other concern, although these people often drop out of the CS major pretty quickly.
