This course is offered through Coursera — you can add it to your Accredible profile to organize your learning, find others learning the same thing and to showcase evidence of your learning on your CV with Accredible's export features.
Course Date: 01 September 2014 to 13 October 2014 (6 weeks)
This course covers finite automata, context-free grammars, Turing machines, undecidable problems, and intractable problems (NP-completeness).
Jeff Ullman is the S. W. Ascherman Prof. of Engineering (emeritus) at Stanford University, where he taught in the Computer Science Dept. from 1979-2002. He worked at Bell Laboratories from 1966-1969, and taught at Princeton Univ. (from which he also received his PhD in 1966) between 1969 and 1979. He first taught Automata Theory in 1967 at Columbia University (from which he received his BS Degree in 1963), and has been teaching it periodically, ever since. He is the author or coauthor of widely read textbooks in Compilers, Databases, Algorithms, and Data Mining, as well as the book in Automata on which this course is based. He is a member of the National Academy of Engineering, winner of the ACM Karl V. Karlstrom Education award, the IEEE Von Neumann Medal, and the Knuth Prize.
I am pleased to be able to offer free over the Internet a course on Automata Theory, based on the material I have taught periodically at Stanford in the course CS154. Students have access to screencast lecture videos, are given quiz questions, assignments and exams, receive regular feedback on progress, and can participate in a discussion forum. Those who successfully complete the course will receive a statement of accomplishment. You will need a decent Internet connection for accessing course materials, but should be able to watch the videos on your smartphone.
The course covers four broad areas: (1) Finite automata and regular expressions, (2) Context-free grammars, (3) Turing machines and decidability, and (4) the theory of intractability, or NP-complete problems. Why Study Automata Theory?
This subject is not just for those planning to enter the field of complexity theory, although it is a good place to start if that is your goal. Rather, the course will emphasize those aspects of the theory that people really use in practice. Finite automata, regular expressions, and context-free grammars are ideas that have stood the test of time. They are essential tools for compilers. But more importantly, they are used in many systems that require input that is less general than a full programming language yet more complex than "push this button."
The concepts of undecidable problems and intractable problems serve a different purpose. Undecidable problems are those for which no computer solution can ever exist, while intractable problems are those for which there is strong evidence that, although they can be solved by a computer, they cannot be solved sufficiently fast that the solution is truly useful in practice. Understanding this theory, and in particular being able to prove that a problem you are facing belongs to one of these classes, allows you to justify taking another approach — simplifying the problem or writing code to approximate the solution, for example.
During the course, I'm going to prove a number of things. The purpose of these proofs is not to torture you or confuse you. Neither are the proofs there because I doubt you would believe me were I merely to state some well-known fact. Rather, understanding how these proofs, especially inductive proofs, work, lets you think more clearly about your own work. I do not advocate proofs that programs are correct, but whenever you attempt something a bit complex, it is good to have in mind the inductive proofs that would be needed to guarantee that what you are doing really works in all cases.
Will I get a statement of accomplishment after completing this class?
Yes. Students who successfully complete the class will receive a statement of accomplishment signed by the instructor.
What is the format of the class?
The class will consist of lecture videos, which are between 15 and 45 minutes in length. These contain integrated quiz questions. There will also be standalone homeworks that are not part of video lectures, optional programming assignments, and a (not optional) final exam.
How much work will I be expected to do in this class?
You need to work about 5-10 hours per week to complete the course. About 2 hours of video segments each week, containing inline ungraded quiz questions. A weekly, graded multiple choice homework.
Week 1: Finite Automata Week 2: Regular Expressions and Properties of Regular Languages Week 3: Context-Free Grammars and Languages Week 4: Properties of Context-Free Languages, plus introduction to Turing Machines Week 5: Turing Machines and Undecidability Week 6: Intractable Problems (NP-Completeness)
3-4 lecture videos each week. Many of these videos are longer than the typical MOOC video, so feel free to pause them and view them in several sessions of your own choice.
There will be 1-2 problem sets each week, which together count for 50% of the marks. You can repeat them until you get them all correct, and they are due two Mondays after release of the videos on which they are based.
There are also two optional programming challenges.
The course is built around the material in Automata Theory, Languages, and Computation 3rd edition (2007), by John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, Addison-Wesley. However, you do not have to buy a copy of this book. The course is self-contained, and all homeworks and exams are based solely on concepts taught in the video lectures.