Just recently I finished my 4th Coursera online class, titled Automata. Taught by Jeff Ullman, this course covered the basic theory of computation and automata theory and ran for 6 weeks. Ullman used his lecture notes from the equivalent course taught at Stanford, and 6 weeks felt like a very short period of time to fully internalize the concepts behind automata. Still, I think this is the most informative and rigorous online course I have taken to date.
The course consisted of video lectures, homework quizzes, and a single final exam. Their were also some extra credit problems and programming assignments, which were of lower priority for me. The per week video material was about 2 hrs straight through, and would usually take me around 10-15 hours taking notes and pausing to reflect on the material. Unlike other online courses, the video material was presented in larger chunks, usually 20 to 30 minutes long, and I have to say I like this format better. Ullman was very active on the discussion forums, leaving no question unanswered, and should be recognized for his outstanding dedication to helping students learn the material. If he teaches another course I will consider taking it for this reason alone.
The content covered included regular expressions, deterministic finite automata, non-deterministic finite automata, context free grammars, push-down automata, Turing Machines, and complexity classes P and NP. A major theme was properties and equivalences among and between these types of languages. Perhaps the most fascinating material was that of Turing Machines and computability, specifically how we prove the undecidability of the halting problem. Also, the complexity classes P and NP were well explained, and a few reductions of common problems like knapsack were given. If I spend more time learning about this topic, I will surely study Arora and Barak's Computational Complexity: A Modern Approach, which would not be possible without first learning the topics presented in Ullman's course.
Many proofs along the way where given, and I have developed a much better sense at the theoretical limits of computation along with sharpening my math and logic skills. Understanding whether a given problem is in P, is essential in knowing if an optimal algorithm can be written in polynomial time without making many assumptions about the nature of the problem instance. Any algorithmic development I undertake will have to take this into consideration. Further, I have learned the tools to understand many topics in computer science at a deeper level than possible before the course, and am looking forward to learning about topics built upon automata thoery, like approximation algorithms and the limits of parallel computation.
