CSCI-E 207 Formal Systems and Introduction to Computational Theory [REVIEW]

This course made me experience Stockholm Syndrome. It held me captive and consume every waking moment of my life. For that, it became everything to me.

It was difficult to find the time to watch or attend the lectures. When I took this course I was: simultaneously enrolled in three classes total, searching for full-time employment, and juggling a consulting gig. BAD IDEA!

The homework was so difficult that by the time you finish one... A brand new and much harder one is already posted online. Sure, lecture was important to understanding the material but it only covered 1% of what you'll have to learn in order to complete the Problem Sets. Well, it just felt that way!

Unfortunately, the lecturer could only cover so much in an hour and a half. Lecture provided an overview but section provided what you needed to know to get started on your homework.

Watch or attend section, or else. If you don't, you'll do poorly. I guarantee it! Brian was our Teaching Fellow and he was the best TF you could ever ask for. He never gave us the answers -- but I am certain he could teach chimps poetry. If you have a TF half as good as him you're in good shape. Often I felt section covered the material very clearly, much more than the book or lecture.


You'll have problem sets almost every week and they'll take about 20 hours or more to complete. This class seemed to be a "re-take" for others but this was the first time I covered this material. If you're taking this as a refresher, then sure, I guess it won't be that hard. But for me, it made me cry myself to sleep.

Besides the weekly homework, you'll have a midterm and a final. I studied diligently for them so I did pretty darn well. Both were difficult -- BUT not as difficult as I thought they would be.

You will also need to spend a week or two learning LaTeX and its markup language. LaTeX is intimidating at first and it does take some time to install. To get my MacBook set up correctly it took me over three hours. Most of the time was due to download a large gigabyte file. I believe there's some dmg you can download to set LaTeX all up for you. The markup language isn't too difficult but it does take a while to get used to as it's not intuitive (at first). On a MacBook, I found TexShop to my editor of choice.

I recommend anyone taking this class to download a tool named JFlap to help you with 2 or 3 of the Problem Sets. Trust me, JFlap is necessary and will help you test your answers. Drawing automaton or construct grammars is a piece a cake. Testing it is just as easy as your can run multiple input strings against your object (as shown above).

The assigned textbook is Introduction to the Theory of Computation (Sipser) and it's good but terse. I used the first edition because it was whole lot cheaper and I didn't have any problems. For the homework, you'll probably need more help if you can't figure things out on your own. A few books that helped me were:

How to Prove it (Vellemen): This book definitely helps for the first Problem Set and will help you write proofs for the rest of the semester. I came back to this book a few times to remind myself how to solve later problems in the course. It costs about $20.

Link to How to Prove it on Amazon

Introduction to Automata Theory, Languages, and Computation (Hopcroft, et al): I don't know why this book doesn't have a higher rating on Amazon. Out of all of the books I've used and looked at, this was by far the best for this class. I didn't find this until the end of the class and read it from cover to cover. If I had it early, many of the Problem Sets would have made so much more sense... SAD!

Link to Automata Theory on Amazon

Final Thoughts
The class was a roller coaster ride: I loved it, hated it, loved it, hated it, and so on. I ended up getting an A-minus but I know I earned it. If you want the same, work hard and treat this class like a full-time job. I'd take it again just to get that A.