EECS2001 EECS 2001: Introduction to the Theory of Computation
                                                      Jeff Edmonds

Schedule, Readme, Course Information, Course Description, Notes, Mental Health, Dates, Account, Photo, Fun, Your Marks, Forum, Tests

Topics Slides Video 20 V18 V17 Datta's Questions Sol 2017 Sol
Intro Jan 07
Math Preliminaries 09 13 14
Turing Machines and other models 16 21 23 28 30
DFA Machines Feb 06 13 24 25
DFA Classes fast
Context Free Grammars March 05 09
Countable and Uncountable Infinite 10
Undecidability oops
Reductions For Uncomputability 12
No Proof System for Number Theory zoom
NP-completeness I miss x
Machine Learning you


About Course:
     This course is useful for a student interested in the
     theoretical aspects of computer science.

Request:
     Jeff tends to talk too fast. Please help him go pole pole slowly.

Math Preliminaries: Review on your own intro slides

First Order Logic:
           (Before a student can understand or prove anything in mathematics, it
           is essential to first be able to res present it in first order
           logic. Hence, Jeff reviews it in each of his courses.)

Models of Computability:
           (Historic and mathematical ways of modeling machines for computing.)

Deterministic Finite Automata - Machine:
           (Useful for modeling simple machines eg coke machine.)

Deterministic Finite Automata and Regular Languages Classes:
           (We classify computational problems based on the amount of resources
           used to compute them.)

Context Free Grammars:
           (Useful for modeling and parsing languages.)

Countable and Uncountable Infinite:
           (There are more real numbers than fractions and the same number of
           fractions as integers.)

Halting Problem is Uncomputable:
           (Some computational problems are solved by NO algorithms.)

    One page proof Halting is Undecideable
    History of Computability
    The Halting Problem
    Understanding Quantifiers
    Some Uncomputable Problem
    Halting Problem is Uncomptable
    Review
    Questions

Reductions For Uncomputability:
           (Knowing that some computational problems are hard, we prove that
           others are.)

No Proof System for Number Theory:
           (Godel proved that there is no mechanical way of proving everything in
           mathematics.)

NP-completeness:
           (Reductions involve writing an algorithm for one problem from that for
           another. NP-Completeness give strong evidence that most search
           problems that industry cares about are believed to not have poly-time
           algorithms.)

    History
    Course vs Schedule
    More about Reductions
    Circuit vs Airplane
    Circuit vs 3-Colouring
    Conclusion
    Definition Review

Machine Learning Made Easy:
           (The basic math needed to understand machine learning)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.