course
Computer Science Theory: Computability - Models - Computation

I took both discrete math and computer science theory with him. He's the best. An awesome professor. I'm going to graduate this year and after experiencing a ton of CS professors, the previous reviewer has to be kidding me. I hope Columbia continues to bring him back. He's WAY better than the regular professor who teaches Discrete *coughs* Ansaf *coughs*. I've taken a class with Ansaf and it's truly my worst Columbia experience. The previous reviewer seems to have an issue because Robert mainly teaches at a small college (he sounds elitist to me). LOL great researchers does not mean great teachers. Robert is actually one of the best professors I've had at Columbia. He posts lectures beforehand to accommodate those in different timezones (since at that time in 2020 recordings took 24 hours to be posted instead of right away like now in 2021), and also to allow students have a head start on the HW since the summer schedule is condensed. He's available during office hours and the TAs were great. He even accommodated students during the exams for those in different time zones. His grading was generous, AND his teaching was great. He definitely does NOT just read off the notes. The notes are literally him minimizing the students' work: instead of having students take notes during class, he provides enough notes that lets you just focus on the lecture, and then use the notes to study for the exams or a guide for the hw. He also fixed the typos of the notes and re-uploaded them :/ Like really the previous reviewer just comes off as an elitist and everything he said was wrong. His lectures were sufficient enough that I did not have to resort to the textbook or any other online resource, which says a lot, and I am by no means a math genius. Take him.

My favorite class in the cs core! Let me preface this by saying I did not do very well in this class but really enjoyed it and thought Xi was a fantastic professor. He broke down difficult class examples into smaller steps that made sense. The homework was very manageable and taught me a lot. Xi was so good that I'm trying to take another class with him.

Xi Chen is a gem in the CS department. He not only makes occasionally-dense proofs comprehensible, but he motivates them such that you actually want to follow along and hear what he has to say. CS Theory was this dreaded class, but it ended up being one of my favorites this semester. Maybe it helped that his general attitude was very understanding, e.g. "I know this doesn't make a lot of sense but it hopefully will in 5 minutes," said in a way that was in fact understanding and not condescending/outright false. He is understanding just as a person also (accepted HW submitted past late deadline, but don't push your luck). The material is not the easiest of course, but, as with many logic/theory things, if you read the book, pay attention in class, and treat the whole thing as sort of a game, things should be OK.

Tal is wicked smart, evident from day 1, and is super knowledgable about the subject. Unfortunately, I think this somewhat hinders her from succinctly explaining the concepts to half the class just because we're too dumb to understand it (at first at least). Another issue that I found out in the second half of the term is that I was getting too caught up in the fine details of what was being taught in the lecture and wasn't really getting a full picture. But taking a step back from the material to see the larger picture, especially during the Turing Machine section, helped immensely. Even though I struggled with just about everything in the course, I would recommend taking it with Tal because she is super intelligent and is really helpful and approachable in office hours. I only went to her office hours towards the end of the class because I thought she would be somewhat intimidating but this was not the case at all. Some, myself included, found her intimidating in class because she would sometimes answer student's questions with "I'm not sure where your getting confused" which can be awkward for the student asking the question but Tal doesn't mean it with an ill intention. So, if you can get over this bit you should be fine or go to her OH and ask in a smaller setting. I'm not sure how this course will be structured when we go back to campus but the format was three unit tests worth 30%, 30%, 10% of your final grade. I got somewhat below average on all of them - nothing by more than 5% less than average - but did fine on the homework (except for one where I got 50! lol) and the quizzes and ended up with a B+ so the curve is really generous. For context, the averages for the tests in fall 2020 were around 70% each time and I genuinely thought I had failed the second test which was worth 30% yike. With all that being said, I do think that the homework grading can be inconsistent and sometimes (rare for me at least though) just doesn't make sense. Grading is not always inconsistent, but it certainly feels shitty when something unfortunate like that happens to you. But, as long as you go to office hours when confused you should be able to get some helpful pointers about where to start - some TAs are more helpful than others so best to figure that out in the beginning of the term. This class was one of those courses where I disliked it during the course but reflecting on it, it wasn't so bad. That is a strong argument for not taking the course though... TLDR: The curve will save you even if you feel like you are failing.

I used to aim for A/A- for all of my classes, but I think I'm failing this course.

It’s the inconsistent grading and severe penalties to the point that it'd be better to not even try on exams/homework sometimes. I would get 0 points for a proof on one part of a problem but then get credit for the same proof on the next part of the same problem graded by another TA. The professor did not make the class enjoyable for us but it was mostly the TAs that made the class difficult. Unless you have to take this for computer science, do yourself a favor and do not suffer through this. Could not be more thankful for pass/fail.

Professor Malkin is absolutely incredible. She teaches concepts clearly in class and responds to Piazza posts quickly and with in-depth, thorough answers. Literally, I've never taken a class in which the Professor responds on Piazza even more often than the TAs do (and at odd hours of the night, too!). She is a fantastic lecturer and makes the course material super super interesting-- and I say that as someone who has never been interested in the theoretical underpinnings of CS. I would highly recommend taking this class with her.

I highly disagree with the recent reviewer of Fall 2020. This class is required for CS majors only take if you have to or you like the material. The quizzes take at least 30 minutes-1 hour even if you've gone to all lectures. She assigned homework due 1 day before an exam and it was over the break (with no office hours then). She seems out of touch with the students. She judges people's questions in class. Last lecture she spent the entire class (except the last 15 minutes) going over the previous quiz... She manages time poorly. At least now she knows how to work Zoom (the first few weeks/into midterms she had problems with Zoom where class would not start until 20-30 minutes later). She often omits proofs. Oh and she combined her 8:40am and 10:10am sections, so she only teaches 2x per week, and if you have a conflict with the other class time (because you signed up for a specific time of this class) you're forced to watch the recordings and not attend live.

The worst professor I have ever had. Tal doesn't actually teach and her class is not formatted for virtual learning. Why does she omit every proof and tells us to "think at home" when we are all very clearly already at home? The world may never know. I've learned nothing in this class. And frankly, I'm confused as to how she has a silver nugget because that is the biggest joke of 2020.

I highly recommend taking this course with Professor Malkin! Prof Malkin is extremely intelligent and this is clear in the way she presents her lectures. She is clear, concise and really makes the subject matter easy to understand. She covers all bases and encourages you to think in non traditional ways. She is also approachable and always answers questions.

The reviewer below clearly has not taken any advanced math class at Columbia. Omri's explanations of theoretical concepts is very good, and if you have any experience with proof based math courses, you will probably really enjoy his exposition. The reviewer is correct that lectures are the exact same as the textbook, but that doesnt mean that they are not worth going to; reading and understanding the textbook by yourself can take an extremely long time whereas Omri will streamline and highlight important parts of the proofs in class.

The class is basically taught and graded entirely by the TAs who do not know how to grade. Grading was always late (2 of the 5 homework assignments were graded after the final exam) and feedback was terse. Omri doesn't seem to care about his students because he's too busy doing other things. Many times he wouldn't be in his office during his office hours. Take this class with other professors who will actually take their job seriously.

Definitely not the best at explaining concepts, which is kind of critical considering that this course is very abstract and theoretical. It can also get very hard to take notes on his lecture because he often would not write down a complex idea he is talking about and/or scribble very few words about it. He does regurgitate the textbook almost verbatim, so you can totally get away with not attending class.

This is a strong class. Pretty straightforward, not such easy concepts but very clearly explained in the textbook. Chen is a really good and straightforward lecturer. I find that once in lecture and reading a concept once/twice in the textbook made my understanding strong. TA's super helpful too.

Aho is apparently retiring, so perhaps this review won't be useful anymore. However, he also tried to retire 2 years ago and is still here, so I'm not really sure what he is doing? In general, I enjoyed the class. I thought the homeworks in particular were very well thought out – 5 problems, only 5 homeworks per semester and he drops the lowest grade. They neatly covered the concepts and they weren't easy, but they weren't too hard. With some help from office hours, I learned a lot from completing the homeworks, and got good grades on all of them. Aho's office hours are quite good, but the TAs helped a lot as well. That being said, unfortunately I did feel like I learned a lot more from the homeworks than I did from the class. Aho is not a very engaging lecturer – he talks very slowly in a monotone voice. He also fails to go over very many examples for a lot of the theorems, because they are common sense to him (he is a very Smart Man). I do, however, believe that you can learn to learn from Aho – at the beginning of the semester I felt lost at every lecture, but towards the middle and end I realized that if I attended class and wrote down everything he said, then went over it later for ~30 minutes with the online lecture notes, I could definitely understand the material. Note: apparently Aho is also the only one who teaches lambda calculus (other than Verma, who is new). Although the subject itself is easy, it is also useless plus it means the rest of the semester is rushed so that he can fit in lambda calculus. Overall, I would say it is a good course taught by a good professor. However, it seems that the other sections have been taught by amazing professors (Yannakakis, Verma, etc.), so make sure you look at your options but don't feel bad if you get stuck with this one.

A well-executed class. Tal Malkin is very clear, puts a lot of effort into teaching, and knows that mathematical maturity among her audience varies wildly. Thus, she gives intuition as well as rigor, followed by many examples. She likes to get people to participate in lecture by answering or asking questions. This can be either illuminating or frustrating, depending on said people in class. For the most part, lectures followed Sipser quite closely, although she merely sketched many of the more involved proofs, e.g. for PCP. The material was interesting enough, and she tries to give some motivation or application. However, the complexity portion of the class was much too rushed: we skipped many proofs and handwaved everything else. Recitation notes were regularly posted, and these were quite long and poorly LaTeXed but very thorough, so I can't complain. Most everybody who takes this class has to, so I recommend taking her iteration of it.

Professor Yannakakis is a very capable lecturer. Although he has a soft voice and a slight accent, his explanations are very clear and so are his answers to questions. It's not a super exciting class, but at least you won't be confused. His problem sets are also reasonable and do not contain anything he hasn't taught. His exams are trickier, since they require not just walking through algorithms but also understanding concepts on a deeper level. Definitely read over the lecture notes very carefully. Finally, he actually answers questions on Piazza! Take Yannakakis if you get him.

Fantastic professor. He was extremely clear throughout every lecture, and took time after every lecture to answer every question you have, even if that means reviewing what he went over in class. If you're taking CS courses in the summer, definitely consider this one to knock out your requirements. The problem sets didn't take too long, and as for the midterm and final, he gives out a study guide that will indicate pretty much what *exactly* will be on them. The workload is very, very light, and the exams are very fair if you use the study guides he provides. Honestly, you can spend very little time preparing outside of class for the exams if you pay attention in class and sometimes stay after class to ask questions because he's that clear (some will say slow-paced, but the concepts are very well-elucidated). He largely covers the textbook, but I never found myself really needing to turn to it.

Prof. Malkin is the best. Not only does she understand and explain the material very thoroughly, she also makes a genuine effort to learn her students' names and engage the class. She has this one-liner which she uses when nobody raises their hand: "You either do not understand and should ask a question, or you understand and can give me the answer." - Prof Malkin's honesty/authenticity shows through in one-liners like this one. Lecturing style - probably one of the best lecturers in the department. She does this thing where she gives a hand-waving, intuitive explanation of something, and then shows it formally. She is extremely approachable and very open about how grading is done in the class. Prof. Malkin and her TAs put in an try very hard to make the course fair, always retroactively applying a policy change to all students if one student brings it up, and I think that this attitude starts at the top with Prof. Malkin setting the example.

Very underwhelming class. I chose to take CS Theory with Aho due to his fame...in hindsight, this was a bad decision for me. I'm sure there are other people who feel differently, but this was my experience: Lectures- Aho seems to think that the material is a lot easier than it actually is, often failing to adequately explain simpler concepts in favor of complex proofs, etc. that never appeared on homeworks or exams. This is probably due to the fact that he pretty much invented a lot of it; however, for most of us, this was our first experience with theoretical computer science. Aho also just plainly isn't an engaging lecturer. Listening to him lecture is a lot like listening to your great-uncle drone on about the Great Buckwheat Shortage of '68 (if your great-uncle is a great storyteller, then ignore this). Occasionally, Aho will talk about having dinner with Stephen Wolfram or working with Kernighan and Ritchie at Bell Labs, which is always cool but doesn't necessarily make the class worth taking. Homeworks- hard, but doable. There were five problems per problem set. They were problems that you had to do out and solve, which turned out to be useless because: Exams- both the midterm and final were 10 true/false questions (with brief explanation). I just don't understand how ten true/false questions can adequately assess your knowledge of CS Theory. For the midterm, I studied all the algorithms and the workings of automata, but I did poorly on the exam (far below average). Many of the T/F questions were tricky (average was a 45, std. dev. of 22). For the final, I didn't bother to learn how to solve any problems or do any proofs, because I knew they weren't going to be on the exam. Didn't really know much about Turing Machines. Bad mindset, I know, but I just studied the general concepts and did much better than the class average (which was a 75). In conclusion- my recommendation? Take this class with someone else. I was not impressed...I'm not trying to be disrespectful towards Aho, but he is a professor that should be known for his accomplishments, not his teaching ability. Apparently he got a Great Teacher Award from Columbia at some point, but I feel like that has a lot to do with his legacy. I dunno, someone might come along and say something different, but I found the class dull and uninspirational.

Well organized notes, very straightforward exams - very similar to the practice questions she provides. Probably one of the nicest professors on Columbia's campus. Office hours incredibly helpful.

Computer science theory with Professor Yannakakis is a pretty good class; definitely one of the better classes I’ve taken in the computer science department. There was nothing exceptional about it, but the fact that there was nothing strikingly wrong with it puts it well ahead of most other CS classes I’ve taken. The professor wrote excellent lecture notes which he posted online, and followed them closely during lectures. He also handled questions from the class very well, and it was clear that no question ever came close to phasing him. His progression through the material was both organized and logical. If I had any criticism, it would be that we went rather slowly through details of proofs and constructions that didn’t seem very fundamental to the course, and we could’ve gone through a bit more material if some of this was streamlined. The assignments for the course were very reasonable in scope and they did a good job enforcing the important points for each topic. It seemed that he actually chose the problems based on what he covered in lecture and thought was important. They were assigned and due every 2 weeks, and each consisted of four problems of varying difficulty. Solutions to these were posted after they were handed in, and graded problem sets were returned a week after completion. The exam were also pretty fair. Some problems were more difficult than others, but nothing too ridiculous. Both exams were during the 75 minute class period, so the scope of the problems was not very large. The median on the midterm was 73 and the median on the final was 63.

This was an OK class. CS Theory with Yannakakis is neither good nor bad. The subject itself is very interesting. It's just the presentation of the material by Yannakakis and the textbook (HMU) that is lacking. Yannakakis is no doubt a brilliant man, but he's a mediocre teacher. He puts up slides of lecture notes on Courseworks and teaches directly off of them in class. This led to maybe 30 out of 87 students actually attending the class. The textbook often has convoluted proofs and too few examples. It's the defacto textbook for automate theory, but I think it could be improved. Sipser is another book which has slightly better explanations. Yannakakis teaches concepts in a reasonable manner given the dense material. Most people didn't attend class and just studied from the slides and textbook. His explanations are not much better than the textbook and you can learn everything from his slides. My advice is to make sure you are up to speed with what's being covered in class. The material can be dense and hard to follow, so try not to get lost because it will lead to a disaster when exams come around. Problem sets (40% of grade) generally have 1 or 2 easy questions and the rest are hard. It is advisable to check your work with classmates since homework counts for 40% of your grade and you shouldn't lose too many points on it. Don't worry too much if you don't completely understand some complicated proofs (eg- NFA to Regex, PDA to CFG conversions). If you know the method that it proves, you'll be fine for exams. He never asked to prove something in an exam. Questions were along the lines of design a DFA, CFG, Turing machine, algorithm, do a reduction, etc. Some of them can be tricky. The midterm (30%) and final (30%) consisted of 6 and 5 questions respectively and were both in class. They were manageable, but kind of hard since we got so little practice solving problems. The course is mostly theory with few examples and 4 problems per homework don't really prepare you for the tests. Make sure to study all the lecture slides and problem sets for exams. Read the textbook whenever you get confused by the lecture slides. Grading is fair. TAs grade both problem sets and exams. Final letter grades were also very reasonable. I wouldn't avoid Yannakakis, but neither would I recommend taking this class if someone better (like Aho or Malkin) were teaching it the next semester.

CS Theory as taught by Yannakakis is a good class -- it achieves everything you basically expect a class to, though it isn't outstanding in any particular regard. For almost the entire semester Yannakakis follows the textbook ("Introduction to Automata Theory, Languages, and Computation"), and it pays to read the text ahead of time. The book is light on theory and heavy on examples, and you could probably get away with not going to class for the first 10 weeks or so until Turing Machine reductions start to be explained, because the book's explanations until then are always thorough enough. Lecture clarifies and sometimes expands a bit on the book, but not in any fundamental way, e.g. there might be a slower and a faster way to implement a given algorithm, and the book gives the slower one while Yannakakis will show the faster one in class. Once you get into Turing Machines, going to lecture is pretty important. The book sucks on reductions. As a lecturer Yannakakis isn't exciting (it didn't help that this semester's room was poorly lit and had amphitheater style seating -- quite conducive to dozing off) but he is usually quite effective at going through examples clearly. He's been doing this for long enough to know which points people get confused about, and he makes sure to hammer those home. The only times I was truly lost in class were on a handful of particularly weird proofs that he demonstrated purely to make a point; they never came up on homework or exams. Yannakakis is (as those of you who've Googled him will know), a pretty big name in the field with a prize or two to his name. There aren't many opportunities in CS Theory for him to show off his brilliance, but he is clearly in total command of the material in a way that not all professors always are. He virtually never makes mistakes on the blackboard (he's usually working from his lecture slides, which are excellent and available on CourseWorks), and will occasionally respond to a seemingly narrow question by tying it to much broader questions and answering those, too.

I completely disagree with the two reviews below. I had no experience with CS theory before taking this class, but I had a great time and learned SO much, and want to take more theory classes because of this. Yes, on the first day, and for most of the first two weeks, Choi taught straight from the book, and told us that we could learn from the book just as well as in class. But--and the book is great, don't get me wrong--this proved completely untrue. Over the course of the semester Choi grew a lot as a teacher (it was his first semester teaching!) and gave us his own examples, clear explanations, and answered questions happily. He also seemed to realize that telling students to leave was NOT a good idea, and encouraged us to send him emails and raise our hands in class. The material itself is often hard to grasp, but that's not his fault, and he usually found multiple ways of communicating complicated ideas. I thought his tests were fine. The final was hard, but was curved, and the midterms were very similar to the homeworks. They were totally doable. tldr; Take this class with Choi! He's a really good guy, just a little rough around the edges, who is really willing to help you out and learn from his mistakes.

Professor Choi, isn't a good teacher. He often looked just as confused in lectures looking back at us, as we (or at least I) certainly did looking at him. The material itself is very dense, extremely theoretical, and requires some familiarity with proofs based mathematics. Basically, no amount of coding skills will help you in this class, as it is essentially an advanced math class. The homeworks and midterms are challenging, often requiring insights that are all the more difficult to achieve because Choi's "explanations" often you more confused than before the lecture. Be prepared to spend hours staring at a problem trying simply to decipher the meaning of the question. It is absolutely maddening, and yet, there's no better feeling than figuring out one of those tricky questions. The midterms have many true/false with justification questions with no partial credit, which Choi posts on his exams as T/F/J. I wish I had gone for the pure Justify, without ever definitely answering true or false - I would have done better, as the questions seemed to deliberately be exploiting flaws in common intuition and expectations. All in all, this class was a slow, torturous slog through material that had the potential to be interesting, though I don't know if I would go so far as to compare it to the horrors faced by the unfortunate pineapple in the review below. Choi is an uninspired, robotic lecturer who always feels most comfortable reading from the book. There is no reason for anyone to be surprised at this, though, the man basically said as much when he himself advised us to skip lecture on the first day. However, to his credit, he did start to be more responsive to the class's questions and more active in giving us study materials after the entire class performed dismally on a final that he apparently expected to be easy. I think he became more comfortable lecturing as the semester went on, and while I don't think anyone would ever use words like "interesting" to describe those last weeks, they were at least tolerable. He gave a generous curve at end, and so, I think Professor Choi deserves at least a B for effort.

I've had probably some of the worst professors at Columbia including (according to CULPA) "soul sucking professors" and "don't-take-this-class-unless-you're-an-econ-major professors," but I have never had a "I-want-to-kill-myself" kind of professor until I met Seung Geol Choi. On the first day of class, I came in to the lecture room ready and excited to learn about computer science theory. By the end of that hour and a half, I had already begun to dread my upcoming semester. I even wondered if I should have dropped the class that day, but I didn't and now I really wish that I had dropped it and waited for Professor Aho. To describe my experience in Choi's class would be analogous to describing how a pineapple would feel being slowly twisted into my anus. Choi discouraged us from coming to class under any circumstances on the first day of class. I thought he was joking, so I went to the next two lectures. Considering how awful they were (he paraphrased from the textbook in a very incomprehensible manner), I really should have followed his advice in not going to class. The problem sets were painful. I heard he was mean to his TAs. The midterms were pretty bad, but not as catastrophic as the final exam (which was worth 40% of my grade). I did pretty well in all of my midterms and homeworks, and managed to almost fail the class because of the final exam. I sat through the three hours of the final exam wondering when the pain would end and whether I should just kill myself on the spot because it would be better than finishing the exam. Don't take this class under any circumstances. Please. Save yourself.

Without a doubt one of the worst instructors I have ever had the misfortune of encountering here at Columbia University. Unhelpful and inflexible in terms of grading, which was itself extremely harsh. Exams covered a great deal of material that was never taught/explained in lecture, and were extremely esoteric/pedantic in nature, requiring extreme depth of knowledge in these areas. Instructor read straight from textbook, except in a way that was more incomprehensible than the textbook itself (due to his limited English-speaking/comprehension ability), rendering lectures utterly without merit. Choi actively discouraged students from attending lectures or approaching him with questions. 11/10 would not take again; wait for Aho to teach the course,

I am currently taking Comp Sci Theory with Choi, and I would definitely recommend him. At first the class was boring, because he taught straight out of the book. By the first midterm, I only came half the time, because it wasn't interesting. Before the midterm, he did an informal survey evaluation to see what the class thought. I was in his office hours before the midterm (like most professors, his office hours are useful if you have specific questions). As we were packing up to leave, he said that the evaluations had been really bad, and he had to figure out how to change the class. At this point, you might be wondering why on earth you would take this class. Here's the thing: he really listened to the evaluations! I came back to the first class after the midterm, and he had totally changed the way he taught. Instead of going through every proof step-by-step straight out of the book, he focused on the main concepts of the proof. He engaged in a dialogue with the class, asking how we would approach a certain question, and breaking it into manageable chunks. For example, he might start by asking what approach we should take (proof by contradiction, diagonal method, etc). It's amazing what a change there's been in the class. As far as I'm concerned, if you want a completely formal, rigorous proof of every theorem, you can read the book. (I should mention that the book he uses is very good-- thorough, readable, with useful diagrams.) What Choi's been teaching us is far more valuable-- how to think about a proof, how to go about setting it up. In other words, his class is great for building your logical intuition. It's also a fun class, and he makes it seem much more intimate and interactive than you would expect for a hundred-person class (as you would expect, about sixty people show up on any given day). There are twenty or so people who regularly ask questions, and he's learned all their names. It's a comfortable, yet productive atmosphere.

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.

The course is interesting, and Prof Feldman really enjoys the material espcially cnsidering that his advisor at MIT was the man who wrote the book you use. He is not the most exciting of lecturers, but he does cover the material in a effecient and clean manor. Prof Feldman is always ready to help, and seems to enjoy students coming to office hours to talk about P vs NP or the Red Sox, its your choice. He is a solid proffesor and I would recommend him if you are going to take computability.

The subject is hard, but Zeph is very passionate about it and works hard for his lectures. He must spend a lot of time preparing for his lectures, his homeworks, and exams, therefore, it is expectected that you will also do your part and work hard to meet his expectations. the homeworks are VERY time consuming!! and you might not be able to solve all of them yourself, some problems could be easy once in a while, but others could require you to be a genious to come up with a unique efficient solution. It is recommended that you form study groups to do the hws and study for exams, it will make the experience less painful. If you master the hws, and the readings of the book and think you are ready for the test, you'll be presented with new problems not seen before that will test how much you internalized the knowledge of the subject . be expected to do a lot of studying on your own, of course that if you are a math person, who loves math and cs theory, you'll be find, but if not, then a lot of work from your part will be needed. I enjoyed the class, is one of those classes that when you finish, you take a lot whole information of the subject with you.

First let me say: this is a DIFFICULT class. In fact, this is the most difficult non-programming class in all undergraduate computer science classes. Second, Prof. Grunschlag tries hard to explain the material as best as he can, but sometimes gets carried away in long proofs that won't ever be tested. Third, The homework problem sets are very very time consuming and usually you cannot solve all of them by yourself. Group discussions on the homeworks are strongly encouraged. Fourth, the tests are slightly easier than the homework problems, but not a lot. The tests do not usually involve lengthy proofs like the homework does, but there are a lot of tricks in the tests that you need to be careful with. All in all, a difficult class, but with a VERY BIG curve. So even if you feel you are doing poorly, you are probably OK.

Great Professor. Really enjoys the material, and enjoys teaching it. He'll even bring some humor into the class. Also, the subject material is really interesting (turing machines, P vs NP, etc). Also, if you are CS, you have to take the class anyway, and he is pretty much the one that teaches it.

Great professor, really seems to like every bit of the class. So, even if you hate the class in the beginning, his enthusiasm might transmit to you as well.

Zeph is a great guy, and he is really interested in you learning, and if he sees you putting in effort into the class he will help you and give you incentive along the way. He is always giving extra credit and stuff. The problem is that this class is hard, and takes a sh**load of time. don't slack off in the begining because those few points you missed on in the begining will come back to haunt you in the end.

Prof. Malkin is one of the is the best professors I have had in the CS department. She's brilliant, but can explain topics clearly and doesn't make you feel like a moron. Go to class because the homework and test questions are based on her lectures. She's very friendly and approachable. However, don't even try to BS her. She will not give out last minute extensions (unless you have an emergency) and collects homework at the beginning of class or it's considered late. Take the time and do the problem sets yourself. This is one of those classes where you cannot cram the night before the test and expect to do well. You have to really understand the concepts.

Great professor who really, really knows her stuff. Lectures well and does not use slides (as Grunschlag does) so going to class is important. Friendly and helpful during office hours. Funny and very likable! Subject material itself is very interesting and creative, but can also confuse and/or frustrate (especially people who are not very mathematical) because it is all proofs and the problems are extremely interrelated and similar. Reading ahead a bit before lecture would definitely help tremendously.

He's a very nice guy and he really wants to help you, but there's a good chance that by the time you go to him for help it'll be too late. The first half of the semester was extremely easy, which is why the second half hits so hard. Before you know it you'll be weeks behind, and at that point falling asleep in class to his not-so-stimulating lectures sounds like a good idea. The best advice is AS SOON as you don't understand ONE THING, no matter how small, get help with it, or you'll be lost for good. He tries so hard to make the students learn so that if you aren't, you'll feel guilty.

An immovable boulder in the CS major track, CS students usually put this one off as long as possible. While any class in Computability would be rough, Zeph means well and makes a good-faith effort in this huge and unfriendly subject. His lectures are actually decent and clear (the official word is that he has "gotten alot better" since starting a few years ago), but the class is still best-handled by drinking your new "Computability" brain cells to death the minute the final is over, and not stopping until they're good and dead. Seriously, though, the organization and clarity of the course overall are better than they might be. With Zeph, the book is good and you know more or less what is going to be on the tests ahead of time. Students don't look at an the midterm and go "what the fuck, how can he be asking about THAT random thing!?" as they do in so many other classes. A hard, hard class, but with that said it's about the best it could be.