Related Subjects

computation

View educational material

Readings

Exam 1 (html)
Exam 1 (PDF)
Exam 1: Solutions (html)
Exam 2 (PDF)
Exam 2B (PDF)
Handout: Recitation 1 (html)
Handout: Recitation 2 (html)
Handout: Recitation 3 (html)
Handout: Recitation 4 (html)
Handout: Recitation 5 (html)
Handout: Recitation 6 (html)
Handout: Recitation 7 (html)
Handout: Recitation 8 (html)
Handout: Recitation 9 (html)
Lecture Notes (MS Word)
Lecture Notes (PDF)
Problem Set 1 (html)
Problem Set 1 (html)
Problem Set 1 : Solutions (html)
Problem Set 2: Solutions (html)
Problem Set 3 (PDF)
Problem Set 3: Solutions (html)
Problem Set 4 (PDF)
Problem Set 4: Solutions (html)
Problem Set 5 (html)
Problem Set 5 (PDF)
Syllabus (PDF)
Useful Links (html)

Video Files

Lecture 1 (Real player)
Lecture 2 (Real player)
Lecture 3 (Real player)
Lecture 4 (Real player)
Lecture 5 (Real player)
Lecture 6 (Real player)
Lecture 7 (Real player)
Lecture 8 (Real player)
Lecture 9 (Real player)
Lecture 10 (Real player)
Lecture 11 (Real player)
Lecture 12 (Real player)
Lecture 13 (Real player)
Lecture 14 (Real player)
Lecture 15 (Real player)
Lecture 16 (Real player)
Lecture 17 (Real player)
Lecture 18 (Real player)
Lecture 19 (Real player)
Lecture 20 (Real player)
Lecture 21 (Real player)
Lecture 22 (Real player)

Other Files

All Files: HTTP

Resources

Bookmark

Course 08: Theory of Computation (ArsDigita University) (2001)

A theoretical treatment of what can be computed and how fast it can be done. Applications to compilers, string searching, and control circuit design will be discussed. The hierarchy of finite state machines, pushdown machines, context free grammars and Turing machines will be analyzed, along with their variations. The notions of decidability, complexity theory and a complete discussion of NP-Complete problems round out the course.

Text: Introduction to the Theory of Computation, Michael Sipser.

Reference: Introduction to Automata Theory, Languages and Computation by Hopcroft, Motwani and Ullman.

Requirements: Two exams, five problem sets.


This educational material is part of the collection: ArsDigita Computer Science University

About this Item

Date:

2001

Write a review
Downloaded 74,502 times Reviews
Average Rating:

Reviewer: Joy888 - - September 28, 2010
Subject: Im looking for Regular Expression lecture...
I can not find anything about regular expression... by the way i like the lectures.

Reviewer: nalrun - - September 23, 2010
Subject: Amazing
Thanks a lot to the Professor and University. Great job!

Reviewer: siva rolangi - - July 31, 2010
Subject: thanks to the professor
these lectures are awesome,thanks to professor SIMMONS & UNIVERSITY for providing such a great stuff

Reviewer: chamanbagga - - April 4, 2008
Subject: Amazing content
These lectures are very good, especially for somewhat tough subject like this... it makes the course pretty easy..

Reviewer: sarek - - March 6, 2008
Subject: The difference between passing and failing
I am currently enrolled a graduate version of this class based on the same book (the whole book in 16 weeks with doing 7 problems [much harder then the excercises]) at a on-line university and couldn't make heads or tails out of the book without these videos.

Reviewer: Ricardo Quiroz - - December 17, 2007
Subject: Awesome material
I´m downloading the videos and they helped me in my classroom. Even we follow another book to develop this topic at class, we found we´re imparting the same knowledge as we saw at the videos. Thanks to keep them online, I was unable to find something similar on the net.

Reviewer: 0404kumar3 - - October 6, 2007
Subject: Helps a lot
One of the best lectures I had ever seen

Reviewer: wackyStudent - - March 17, 2007
Subject: Help me get an A
Can't beat the price! Content is A+ and maybe better than some paid lectures