professor
Mihalis Yannakakis

May 2017

This was not the most interesting theoretical computer science course I have taken. Sure the material is very canonical: approximation algorithms for all of the standard problems, lower bounds, and reductions. However, it just did not hold my interest. The algorithms were all presented well, but they just were not that interesting. Perhaps part of the problem is I had seen most of the material before. But moreover, because each class we looked at new algorithms, it did not feel like the class was going anywhere, but rather starting over with a new problem each week. Overall, not a bad class. Teaches you all the approximation algorithms you would want to know. Most of the material you would need to get started in the field of algorithms.

May 2016

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.

May 2015

This was one of the best classes I have taken at Columbia. It is a topics course on approximation algorithms, mostly for NP-Complete optimization problems, and there is a brief discussion of online approximation algorithms at the end of the course. The emphasis is on the design and analysis of approximation algorithms, and some time is also spent on hardness of approximation results. This is a definitely great class to take if you enjoyed Analysis of Algorithms 1. Professor Yannakakis is an excellent instructor who has an unbelievable command of the material. He always has comes to class with a very well-structured lecture plan, and is able to give very thorough answers to students’ questions. He also posts great lecture notes online, which are very helpful, as is the recommended textbook “Approximation Algorithms” by Vazirani. For many of the lectures, he begins the lecture by introducing an optimization problem (or a family of closely related optimization problems) and then spends the lectures going through different approximation algorithms for the problem in increasing order of sophistication. The class met once a week for two hours, and while these lectures were a bit long, it allowed for the material to be covered with a good amount of depth. He is also very up to date with the material and able to put the results we cover in context, sometimes telling us about recent improvements from the past few months! While some of the reviewers have correctly point out that he is not the most exciting lecturer, he does a great job of engaging students in lectures. He is definitely one of the best professors I have had, and I believe he is by far the most underrated CS professor. The homework assignments were some of the most interesting and well-designed that I have seen. They are very relevant to the material that is covered in lecture and strike a great balance between rigor and accessibility. Every problem is interesting and somewhat substantial and there are no boring filler problems. I definitely had a great time working on these, though I suspect it would have been much less enjoyable had I left them till the last minute. We were given a good amount of time for each problem set and I recommend taking advantage of that. For the last month of the class we had a research paper instead of problem sets, which required to write a 10-15 page paper on a relevant topic of our interest. The assignment is pretty flexible and I thought it was a great experience, especially since none of my other CS classes had a similar assignment.

May 2015

If you're in the Foundations track, you should definitely take this class. The course covers approximation algorithms often touching upon some state of the art stuff in the field. It's quite an intellectually challenging with plenty of opportunity to really dive in depth into the subject matter if you choose. There were a surprising number of undergrads (at least 6 out of 35) for a 6000 level class so you'll have plenty of company. Yannakakis is not the most exciting lecturer but an expert in the field and as such can answer any question you throw at him. The class was 2 hours long so it was often hard to concentrate for the entire duration. If you get lost at any one point in time, you're pretty much screwed for the rest of the class since it all builds up. Each class generally consisted of us studying a specific problem and different techniques to design approximation algorithms. A lot of the material can be found in the textbook Approximation Algorithms by Vazirani. It would be useful to brush up on common problems like max-cut, flows, TSP, etc. to get the most out of the class. Homeworks were generally difficult and required some time and deep thinking. I worked with a friend and it took us maybe 10-15 hours on average + attending office hours where one of the TAs would pretty much go over the gist of the solution (which was very much appreciated). You have to write a 15 page research paper on any topic of your choice within the scope of the class. He gives you a month for it and I suggest you start early. I put together a pathetic excuse for a paper 3 days before it was due and was not happy with the results or my understanding of the problem I was studying. Overall, a solid class that's only offered once every 2 years. 100% recommend taking it.

May 2015

I've reviewed two previous classes with Yannakakis (December 17, 2013 and May 02, 2014 reviews) both of which I liked. Approximation Algorithms was more of the same -- he may not be super charismatic or exciting, but he's a thorough, and incredibly knowledgeable professor (the course covers quite a range of topics, but he's up to date on the latest in all of them; it's not unusual for him to say, "we'll be discussing this version of the algorithm, but 6 months ago researchers X and Y came up with a much better version..."). He posts great lecture notes, gives interesting homework and has TAs who grade fairly. The homework in particular deserves a shout-out, as it felt much more like puzzle-solving than the drudgery most CS classes force you through. The final research project was a lot of fun, as someone who hadn't done one before. Also, I found the CS Theory -> Computational Complexity -> Approximation Algorithms sequence with Yannakakis worked very nicely (the assumed background knowledge matches pretty closely to what he's taught in his previous courses), and I'm guessing if I'd taken Algorithms I with him, too, it would've been even better.

May 2014

Computational Complexity with Professor Yannakakis is an excellent class. This was my second class with him, the first being CS Theory in the fall, and with that said, I am confident that he is a good choice for any class he is teaching. I will definitely take another class with him if the opportunity comes up. While he might not be a dazzling speaker, he is always well-prepared with very structured lecture plans and does a great job presenting the material. The material is very well-motivated and he involves the class in his lectures by frequently asking questions. He is able to thoroughly answer any question that comes up from the class. There are few to no errors in the lectures, and detailed lecture notes are posted on Courseworks. The textbook is the bible for the subject and it is well-written, but he doesn’t strictly follow it, so it’s really not necessary for the course. The homework assignments were also very well-written and unambiguous, and ultimately at the heart of the course. I definitely learned a lot from working through them. While this class is the natural follow-up to CS theory, one difference is that there are fewer formulaic problems that simply require following an algorithm. Usually a bit of thought is required for most of the homework problems, but they’re manageable as long as you don’t leave them until the last minute. Hints are generously provided for more difficult problems. I agree with the previous review that the Turing Machine topic at the beginning of the course could’ve been shorted. Much of that material was familiar for CS Theory, and it was without doubt the least interesting part of this course.

May 2014

(I'm the author of the December 17, 2013 review of CS Theory with Yannakakis.) In general, my take on this semester is the same as my review of CS Theory with Yannakakis, though this time the lecture hall wasn't so sleep-inducing. Yannakakis is not exactly an exciting lecturer, but charisma aside, he does everything he should: he chooses a good textbook, assigns homework that reinforces and expands a bit on the material, has a TA who grades fairly, provides good lecture notes online, and so on and so forth. My only real complaint is that the class overlapped a lot for the first month with CS Theory, but given how many people were confused by really basic issues about Turing Machines, I guess that wasn't Yannakakis' fault. I'd definitely take a third class with him if the opportunity presented itself.

Dec 2013

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.

Dec 2013

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.

Dec 2013

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.

Dec 2010

I took the class CSOR 4231 with Prof Yanakakis. Unless you are really stupid, do NOT take this class under this Professor. Granted, he has great credentials and has won a Knuth prize or two for his research. But at the end of the day, teaching a course is not the same as doing research and not everyone can do both well. Instead of making the class interesting and explaining the background behind how algorithms should be designed and how they came to be, he just puts the algorithm on the board and makes a poor attempt at explaining it. Watch one lecture given by Stein on CVN and you will be inspired .. and sit for one lecture with this guy, and you will forget the little you knew before the class. His homeworks concentrate more on proving correctness than on designing algorithms and mapping problems to standard algorithms. It is a pity that a researcher of his caliber, does not have the ability or the inclination to make this class interesting. Believe me, you would be better off watching lectures on MIT OCW or stein's on CVN. You have been warned.

May 2006

I really enjoyed taking this class with him, and would highly recommend it despite the amount of work that I had to put in - I learned a lot and it was worth it. 1) he understands the material, and explains it clearly and elaborately. 2) It takes a little bit of time to adjust to his accent, but after that you'll find he's an engaging lecturer who always comes prepared and has no problem answering any questions that come up. 3)He's done a lot of theory work so be prepared to tackle that aspect of the algorithms and data structures as well as simply knowing them and how/when they work. 4) Besides being a prolific and accomplished researcher he can teach, and he's a nice guy, which in this case also means very fair grading.