EECS2001 EECS 2001: Introduction to the Theory of Computation
                                                      Jeff's Syllabus

Passion: Thank you for working with me. I do love teaching.
I have been tightening up this material by replacing harder proofs with more casual chats .
This term, we will chat some more .
Please let me know if you think I should get future students to watch a different version than I have indicated.
The plan for the extra time is to do more Machine Learning this term.
.


Jeff, Readme, * Course Info *, Times, Dates, Course Description, Notes,
Mental Health, EClass, Zoom, Forum, Partner, Old Videos Zip, New Videos

Topics (VIDEOS BELOW) Slides Ques Sol 2017 Sol
Intro
Turing Machines and other models
DFA Machines
DFA Classes
Context Free Grammars
Countable and Uncountable Infinite
Undecidability
Reductions For Uncomputability
No Proof System for Number Theory
NP-completeness
Machine Learning


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.

0 Intro: (ppt)

1 Predicate Logic: (ppt) (Math1090 )
           (Before a student can understand or prove anything in mathematics, it
           is essential to first be able to represent it in first order logic.)
           Logic Questions & Solutions

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

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

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

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


Computing (Math 1090) (ppt):
Complexity (Math 1090) (
ppt): Classifying Computational Problems, NP, & Computable

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

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

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

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

7 NP-completeness: (ppt)
           (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.)

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

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.