Sahai bills his version of CS 181 as the unofficial "honors" offering, and he's right. It's very mathematical and proof-based. Each homework really does take about 20 hours (and that's probably a low estimate!). Definitely make sure you get a good study group that you can do the problems with, because you won't be able to do them all on your own.

That being said, Sahai is an excellent lecturer. He starts with the basic question of "What is a computer, and what are the problems it can solve?" and organically builds upon concepts from there. You'll come away with a great understanding of how regular languages, finite automata, context-free grammars, and Turing machines all fit together. He also gives out extra credit for asking questions, so be sure to come to class ready to pay attention.

The grade distribution is actually really generous – apart from giving out lots of extra credit in each lecture, you get extra credit for doing the homeworks in LaTeX and there extra credit problems on the midterm, final, and homeworks. I've heard that taking Math 115A helps a lot with the proof writing, but to be honest I found the TAs were pretty generous on grading for the HWs and tests. The final is also a week-long take-home final, due Friday of 10th week which is nice but also a little stressful. The class is curved, but extra credit applies after the curve so I think most of the class ended up with a B or above.

The textbook is great and the class covers it at a pretty slow pace so there's not that much reading you have to do. Definitely read ahead if you want to get some extra credit tokens at the next lecture.

All in all, this class will demand a lot of you, but if you really want to understand the theory of computation, I can't recommend this class enough.

Great class!