Theory of Computation

Theory of Computation

• Video Lectures at ArsDigita University
• Mirror at ArsDigita
• High Speed Mirror at Internet Archive
• Course website
  

A theoretical treatment of what can be computed and how fast it can be don. 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.