#53 overallEvergreen
Automata
Coursera
8 recommenders · 10 threads · recommended in 6 years, 2012–2020 · score 9.5
An automata theory course covering finite automata, regular expressions, and related formal language theory, taught by Jeffrey Ullman of Stanford. It was offered on Coursera and later moved to edX.
Commenters call it excellent and hard but rewarding, praising Ullman's relaxed teaching style and active participation in forums.
Algorithms & Data Structuresintermediatefreevideo lectures#automata theory#finite automata#regular expressions#formal languages#ullman
Recommendations by year
20062026
Not in the general case. But in this case, yes it can.
First, I suggest you read the fucking link I summarised in the first place: https://swtch.com/~rsc/regexp/regexp1.html
Second, this fucking course is really good: https://www.coursera.org/course/automata (I have taken it myself.) If you have a dozen hours to spare, it is highly recommended.
Third, you may want to take a look at this… fucking… analogy:
0 / \ | | \ / 1 / \ | | \ / 2 . . . N-2 / \ | | \ / N-1 / \ | | \ / N
The number of paths from top to bottom is 2^N. If you want to try them all, that will indeed take exponential time, parallelism or not. But when you process an NFA, you don't care which path you have taken. So you can forget about which path you have "actually" taken.
The thing is, when you branch from K, both branches land at the same spot: K+1. So you merge those branches. Then you split again. So when you're going through this graph, the maximum number of actual threads you will ever run in parallel is 2.
That's nowhere near the expected 2^N.
Here lies the beauty of proper NFA processing. By merging the parallel threads at each opportunity, you keep their numbers down to the number of states in the NFA —at most. As a result, the worst running time of a good NFA algorithm is O(N*S), where N is the length of the input, and S the number of states in the NFA. And the worst running space is O(S).
Of course, if you're fail to merge the threads (like backtracking), then your worst case goes back to exponential. On the other hand, it can give you extra powers such as back references.
I'm self taught :)
Algorithms in a Nutshell does a great job of introducing data structures and algorithms. It's also very short. Data structures and particularly basic graph algorithms (DFS, BFS, DSP) are very powerful and can solve a lot of common problems.
After that, study Math. Algebra, Set Theory, Automata and Calculus were real eye openers. Schaum's Outline of Discrete Mathematics is a good start in discrete math.
Automata: if you can, try and get hold of the Coursera course on the subject. It's excellent. It is hard work, but it got it through my thick skull :)
Then, compilers! They're awesome. They changed the way I think about development, and also in one feel swoop destroyed a lot of respect I had for the industry. I read "Engineering a Compiler" and followed the excellent Coursera course.
Did learning that make me a better developer? In some ways, yes. I'm capable of solving problems that I thought were impossible a few years ago. On the other hand, it is now clear to me that our industry is building castles on sand too often, and that makes me sad.
I feel like Algernon.
The Coursera Automata course is awesome. Ullman's active participation in the current second offering is part of it. But what really makes the course for me is that Ullman's presentations are relaxed. He knows the material, he knows where various aspects of the material rank in terms of importance to the learner, he has a feel for where students will get hung up, and he has no need to prove anything.
Ultimately, this gives the class the feel of a graduate seminar. It is designed so that student's can readily succeed in learning the material rather than structured around the idea of weeding out weaker students. It assumes that anyone who wants to learn the material can with enough effort, and that that learning is really all that matters.
If you're interested in learning Automata from Prof. Jeff Ullman of Stanford you may join the current session on Coursera. What's best about this course is that Prof. Ullman is always present in discussion forums, and helps everyone learn and enjoy great discussions. Join here https://www.coursera.org/course/automata
Edit: I'm currently learning there, and enjoy it a lot. Especially in video 6, you may listen to the stories of Junglee startup, Started in the mid-90’s by three of his students, Ashish Gupta, Anand Rajaraman, and Venky Harinarayan. Goal was to integrate information from Web pages. Bought by Amazon when Yahoo! hired them to build a comparison shopper for books. They made extensive use of regular expressions to scrap..."
Oh, thanks for the update! It looks like the new version is at
https://www.edx.org/course/automata-theory
Definitely recommended if you like somewhat dry and mathematical stuff with deep relevance to many areas of computer science. :-)
I took his 2 algorithm courses on Coursera's original platform. They were stellar. In particular making practical problems that have a calculable answer that you implement yourself in whatever language you choose and check as part of the course. As opposed to having some online interpreter for some specific language.
That was then hosted on Stanford's own Lagunita platform (based on the edX platform I think.)
Stanford then split those 2 courses into 4 on Coursera's new platform - the same material I believe but packaged differently.
Stanford then closed its Lagunita platform and those original 2 courses are now offered on edX.
A similar story with Alex Aiken's excellent Compiler course and Jeffrey Ullman's Automata course too. I'm not even sure if they are still available on Coursera or not.
[1] https://www.edx.org/course/algorithms-design-and-analysis
[2] https://www.edx.org/course/algorithms-design-and-analysis-pa...
[3] https://www.edx.org/course/compilers
[4] https://www.edx.org/course/automata-theory
Also, you can learn fundamental, intermediate and even advanced topics on CS without a formal degree via MOOCs, like the ones offered by Coursera - some of them taught by professors from universities that you may not even have the money/time/grades to get in for a formal degree.
I was thinking about attending to a CS undergrad course some time ago, but since I'm full-time employed at a very big ("unicorn") startup - an opportunity too good to be wasted -, I opted to take some classes on advanced topics such as Discrete Optimization and Automata theory on Coursera . It has been the best use of my spare time ever.
The Scala course fits a common template for Coursera - by which I mean that a meaningful fraction of Coursera courses have similar features, but not all Coursera courses.
That template: A course taught by the person who 'wrote the book', in this Odersky teaching Scala. Others on Coursera: Ullman/Automata, Wetherall/Networking, and Sedgewick/Algorithms. The great thing about these courses is that the instructors know what is important and what isn't and therefore the courses don't get bogged down stuffing every detail into the lectures or reflecting every detail in the homework assignments. The big ideas are the big ideas.
There are also courses taught by mid-career professors - e.g. not fully tenured. These tend to be pretty good, but there is an undercurrent that the course assignments must defend their employer's brand by being hard just to be hard. These also tend to be quality courses, though there seems to be more variation.
The last group are those taught by newer academics and these vary more widely in quality. They tend to take a less general approach as there can be the feeling that 'making a name for oneself' in a publish or perish world is part of the motivation. If the instructor's interest closely aligns with the course and the student's interests, then it can be really good. If not, then there's the 'unenroll' button.
I'd recommend downloading some lectures. I struggled with Linear Algebra before downloading Strang's MIT lectures, and I didn't understand the Dragon Book before following Coursera's Automata Theory course.
I'm looking at the same problem at the moment. PGM sounds really interesting, but I think that the time investment just isn't going to be workable for me unless I drop several of my other classes. My current plan is to watch the PGM videos and try to keep up with the programming assignments as long as I can, but if it comes down to a choice of one or the other, PGM will be the one to go.
As far as "dumbing down", I've found that the Coursera classes that I've taken (Compilers, Automata Theory, Algorithms 1, SaaS and Machine Learning) have varied in difficulty quite widely. Compilers and Automata were both challenging and enjoyable, Algorithms 1 was about what I'd expect from a freshman/sophomore algorithms class and SaaS and Machine Learning were easy enough that they should be approachable to anyone with basic programming experience.
I don't feel that the difficulty in the classes that I've taken had any particular correlation with teaching effectiveness. I found Andrew Ng's ML class to be simple, but still interesting and informative - you come out of it with enough of a basic understanding to implement simple ML techniques as well as a place to start if you wish to learn more. I think that while a theory-centric class would be a nice thing to have, he's done an amazing job of making a class that can appeal to a wide range of potential students and introduce them to a field that's usually very difficult to approach.
Coursera's Automata course is really good, but it's hard work. It's a six week course, and you'll spend around 10hrs per week if you do everything (and I'd recommend doing everything).
Udacity's introduction to statistics, so far, has been really easy.
From what I've seen so far, Udacity are aiming to be more inclusive "community college" level and Coursera are aiming for a true university level education.
What do you want to learn? Programming or CS? CS is more than just programming, and CS theory is more than just Algorithms & Data Structures.
If you want to learn about Algorithms and Data Structures and you have a strong math background, then CLRS is the book to get: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme...
An undergraduate CS curriculum will mostly cover the parts I-VI of the book (that's around 768 pages) plus a few chapters from the "Selected Topics Chapter" (we covered Linear Programming and String Matching). Mind you, this book is very theoretical, and all algorithms are given in pseudocode, so if you don't know any programming language, you might have to go with a an algorithms textbook that is more practical. In my DS course we had to implement a Red-Black tree and a binomial heap in Java, and in my Algorithms course we only wrote pseudocode.
Maybe Sedgewick's (Knuth was his PhD advisor!) "Algorithms (4th ed)" will be a better choice for a beginner, as it shows you algorithm implementations in Java: http://www.amazon.com/Algorithms-4th-Edition-Robert-Sedgewic... (If you decide to go this route, you might as well take his two Algorithms courses on Coursera, they will really help).
There are also a bunch of Python-based introductions to computer science which have a broader focus than just teaching specific data structures and algorithms. Some of them emphasize proper program design, debugging and problem solving. I haven't read any of them, so I can't vouch for them, but here are a few of the more popular ones:
* http://www.amazon.com/Introduction-Computation-Programming-U...
This book was written to go along with John's edX course: https://www.edx.org/course/mitx/mitx-6-00-1x-introduction-co...
* http://www.amazon.com/Python-Programming-Introduction-Comput...
Oh and btw, there's also the Theory of Computation, which is a major part of CS theory. Here are a few MOOCs and recommended books on the subject:
MOOCS:
* https://www.coursera.org/course/automata
* https://www.udacity.com/course/cs313
Books:
* http://www.amazon.com/Introduction-Theory-Computation-Michae...
Sipser's book is probably the best introduction to the theory of computation, and I believe its last chapter deals with Complexity theory as well.
* http://www.amazon.com/The-Nature-Computation-Cristopher-Moor...
I loved this book very much. It has a very informal and conversational style (don't let it fool you, the problem sets can be HARD).
* http://www.amazon.com/Computational-Complexity-A-Modern-Appr...
Once you are familiar with some computation models, its time to study computational complexity and this is one of the best books on the subjects. It is used both for graduate and undergraduate courses.
Check out the Coursera courses:
https://www.coursera.org/course/automata https://www.coursera.org/course/compilers