Introduction to Algorithms and Complexity

Lecture, four hours; discussion, two hours; outside study, six hours. Enforced requisites: course 32, Mathematics 61. Designed for junior/senior Computer Science majors. Introduction to design and analysis of algorithms. Design techniques: divide-and-conquer, greedy method, dynamic programming; selection of prototypical algorithms; choice of data structures and representations; complexity measures: time, space, upper, lower bounds, asymptotic complexity; NP-completeness. Letter grading.

Review Summary

Clarity
0.0 / 10
Organization
0.0 / 10
Time
5-10 hrs/week
Overall
0.0 / 10

Reviews

    Quarter Taken: Spring 2019 In-Person
    Grade: A+

    Contrary to older reviews, Ostrovsky seems to have gotten better in terms of teaching. After a confusing beginning to class where he spent 2+ weeks talking about NP-completeness (a topic barely covered in other 180 lectures) as well as unclear lectures, he settled down quite a bit after week 4-ish and delivered lectures that are worth going to. This quarter, he decided to write on the blackboard instead of using slides, which has its pros and cons. A big pro is that he would talk slightly slower, but unfortunately he does not have the best handwriting, nor is he the clearest. Reading the textbook is essential in most cases.

    Homework is definitely intended to challenge the students, but unfortunately most of them are basically un-doable without the solutions manual. That's not really a trait about his class though, as I hear this is the case with other professors too. (The textbook just has hard problems in general.) I'd still recommend doing them as much as possible on your own – and start early, as nothing beats the feeling of coming up with a solution yourself after thinking about it through over multiple days.

    Exams are exponentially easier than the homework. Even so, this year the average for the midterm was in the 60s, though have actually gotten gradually easier over the past years. Most past midterms with Ostrovsky had averages in the 40s.

    In general, not as horrible as other reviews make it out, but if you have the option of waiting one more quarter to get Sarrafzadeh, wait.

    Quarter Taken: Spring 2023 In-Person
    Grade: B+

    Professor Ostrovsky is a bad lecturer, but his class isn't too hard. He's really lenient on grading, and even if you do bad on the midterm, he will weigh it less if your final is significantly better. I literally got a D on the midterm and still ended up with a B+. You just have to study independently for this class, his lectures really won't help that much.

    Quarter Taken: Spring 2023 In-Person
    Grade: A

    I hated every moment of this class. The lectures were super disorganized and confusing. The homework was so difficult that we'd all just have to resort to copying the answers the TA told us (and the TAs would also need to look up some of the answers because the questions were just that hard). Relying on the textbook is pretty much required for this class if you want to be able to understand anything at all.

    Quarter Taken: Spring 2023 In-Person
    Grade: A

    Lectures were pretty bad and felt disorganized, TA was goated and did a good job explaining concepts. The textbook is pretty good to read.

    Quarter Taken: Spring 2023 In-Person
    Grade: A+

    Ostrovsky is obviously a very accomplished, intelligent, and incredible computer scientist. His contributions to the field are immense—very obvious when he mentions an algorithm and says he once skied with its inventor.

    However, he is an absolutely horrible lecturer.

    Just yesterday, he asked us to review him nicely on course evaluations and on Bruinwalk because he spent a lot of time revamping this course to be more accessible. I appreciate that, and don't doubt that he spent a lot of time making this course better for us. He truly is a nice guy, very approachable, and cracks hilarious jokes to lift our spirits.

    Unfortunately, I've got to say the truth—he isn't a good lecturer. He makes everything more confusing and spends too much time fussing about which marker works the best. He goes through at least 20 markers each lecture. Reading material online, on YouTube, and even the book taught me more about algorithms than him. Again, this is not a personal indictment on Ostrovsky—I love the guy, but teaching isn't for everyone.

    Tecot screams incompetency. I went to his first discussion and left halfway. I could not bear listening to him scribble on his iPad with utter nonsense.

    Instead, I started to (virtually, since I had a conflict) attend Levine's discussions. Absolute masterclass in discussions. Very approachable, nice, structured mini-lectures that filled in the gaps where Ostrovsky left to be desired. He should be the lecturer, not Ostrovsky in my opinion.

    Quarter Taken: Spring 2023 In-Person
    Grade: A+

    Professor Ostrovsky is a very nice guy, don't get me wrong, but as a professor, he isn't that great at teaching. It's hard to follow him when he explains certain algorithms and the proofs for them, as he often rambles on instead of providing a clear step by step guideline as to what he is talking about. As a result, I resorted to watching youtube videos and getting review materials from other university equivalents to help me out. Homeworks were just texbook problems, which were pretty hard and time consuming. However, they weren't graded that harshly as long as you gave it a good effort. In terms of exams, our quarter's TAs were very generous in terms of partial credit. As a result, practically > 50% of the class got A's. Overall, nice guy and generous grading scheme, but not so good at actually explaining the concepts clearly.

Course

Instructor
Rafail Ostrovsky
Previously taught
23S 19S 18W 17S 11S 10S 08S

Grading Information

  • No group projects

  • Attendance not required

  • 1 midterm

  • Finals week final

  • 100% recommend the textbook