[COMS W3261] Computer Science Theory: Computability - Models - Computation

Aho was possibly the best CS professor I've had at Columbia... and I've had some pretty good other professors before.

The book (HMU, Automata Theory, Languages, and Computation) is a bit dense. Luckily, his class notes (posted on his website) are a very condensed, very readable summary. They don't cover everything, though, so you'll have to fill the rest in yourself.

Aho is a very clear and straightforward lecturer. No matter what question you ask, he's able to answer it without hardly having to stop to think - almost robotic (in a good way). Few mistakes, doesn't skip a beat. And a good sense of humor to boot.

The midterm and final were straightforward - the problems were difficult, but short (either you knew the answer and could justify it, or you couldn't). No need to memorize tons of proof details when studying, as long as you understood the process and the underlying concepts. Be warned, though, there was at least one trick(y) question on each exam, so you really need to know the material well!

I'm glad I took this class, as it gave me an appreciation for theoretical computer science (particularly lambda calculus) that I never had. It wasn't the most back-breaking CS class I've taken, but it's definitely one that you'll want to dedicate some time to, partly because the material is dense and abstract, and partly because Aho is just an all-around awesome dude.

Aho is a really really nice Professor. The problem is that he is too smart for his own good. Sometimes it's difficult to understand what he's trying to convey in class until you get to the problem sets and have to work through them. For the most part he tested exactly what he had taught and was very fair about it.

The real difficulty in this class is getting the material. Some people just understand it. Some don't. It's very much like Discrete Math where you are waiting for that ah-ha moment to arrive and suddenly connect the dots and for everything to make sense. Sadly that never came for me.

His stories are pretty funny and they make you realize how cool the CS dept is for having someone like Aho on staff. This is really a hit-or-miss class but I would say take it with Aho if you can.

In retrospect here's how I would have studied for this class if I could go back:
Review your notes after every lecture and then make new notes. Try and see the differences between the various terms (ie: deterministic and non-deterministic, Recursive vs RE). Make sure you understand the theory stuff. Read the book BEFORE the lecture so you have a basic idea of what you're about to do. Do every homework over again before the exams.

I looked forward to this class every day---it's probably one of the best courses I've ever taken. Aho is certainly not for everyone: he's a little dry and very odd, but he clearly cares deeply about the material, and does a good job explaining it.

He's a minor god in computer science---his portrait is on the wall at the Google offices downtown---and this class is worth taking for that reason if no other; he's also shameless about reminding you of his associations with major gods of computer science, in particular his friend Don (Knuth, that is). If, like me, you enjoyed Gross's digressions, you'll probably also enjoy accounts of evenings spent (no joke) playing violin concertos with the author of "The Art of Computer Programming."

You, like Aho, should care deeply about the material. This is a class about the fundamental questions of computer science---how problems can be described, how they relate to each other, how they are solved, and at the most basic level, what it means to compute. If all you want to do is write Java programs to fit a spec, you shouldn't have bothered with college: the whole point of studying computer science at an institution like this one is to learn how to answer questions like the ones Aho asks, and, you know, do something interesting with your life.

In summary, I had a blast; if you like oddball teachers and hard problems you will too.

Overall: A really great class.

Let's start with the bad: the lectures were not 100% terrific... so I tended to skip lecture sometimes and when I attended I sometimes didn't pay much attention. It's not that he isn't brilliant (he is... for heaven sake's he is the "a" is "awk"), it's just that he has trouble teaching to a class.

Now for the good: His office hours are golden. I cannot stress this enough. If you go into his office hours not understanding something, you'll come out of it completely and utterly understanding the subject; end of story. He is TERRIFIC 1 on 1. The homeworks are incredibly hard, so I recommend checking in during his office hours to double-check your work (or ask for pointers -- no puns intended) before submitting.

The other: As I said, his homeworks are incredibly hard (think Discrete math, but far, far more difficult). One of the last problems he gave us included a proof that HE had made in 1993 or some such proving that the way that perl handled regular expression recognition was NP-complete (when he first proposed this... no one believed him until he proved it). There was no way I could have solved this problem without going to office hours. But moreover, with the possible exception of the aforementioned problem, his assignments, while hard, are pretty fun. I don't mean you'll think they are entertaining, but they are well structured, so they are informative, and if you end up understanding the problem, it really helps you get a comprehensive understanding of the material (which is great). He also gives out practice exams that are incredibly useful. Grading is decently quick and fair.

This class is required for CS majors, so you have to take it, but if you have an option of taking it with or without Aho, take it with.

Potentially a very dry topic, but Prof. Malkin was able to make it interesting. Mostly because she seems to believe a great deal in class participation, and engaged students in every derivation.

Overall, I'd rate her highly.

Hell if I know. I never went.

The website says "CS Theory is the last course required of all CS undergrads", but it should probably be more like "CS theory is the last course of the day, don't bother." The topics mostly overlap with other courses (data structures) -- if you stay at home and read up on regexps and such, you'll be completely fine. The homeworks are basically perfect reflections of what you're accountable for, so if you can do them you're set.

I'm not really complaining about Tal, she's pretty OK. At the end of the day, it's just another CS course repeating the same damn curriculum.

Prof Malkin is very approachable and is definitely on your side - but she won't go find you, you have to send her e-mails and especially go to her office hours. Her lectures are thorough and cover the book material pretty strictly, but I think she'd be more helpful if she spent a little more time structuring the material, saying "You are here" in the grand scheme of Computation and it's Proofs. Indeed, I think a map could be drawn of the proofs and their relationship to one another - this would help a lot in understanding the dependencies of proofs upon each other.

Whatever you do READ AHEAD OF THE LECTURE. This stuff is nearly impossible to simply hear and absorb in clas, so having thought about the concepts beforehand will make all the difference in the world. Hell, you might even enjoy it.