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

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

Texts: (No text is required.)
       - Some online notes that I (Jeff Edmonds) wrote years ago when teaching this course.
       - Michael Sipser. Introduction to the Theory of Computation.
       - Harry R. Lewis and Christos H. Papadimitriou, "Elements of the Theory of Computation",,
       - J. E. Hopcroft and J. D. Ullman, "Introduction to Automata Theory",, Addison-Wesley.
       - Ding-Zhu Du and Ker-I Ko. Problem Solving in Automata, Languages, and Complexity. Wiley, 2001.
       - John C. Martin. Introduction to Languages and the Theory of Computation. McGraw-Hill, 2003.
       - Daniel Solow. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. Wiley, 2002.
       - A freely downloadable book on the foundations of Computer Science is here.
       - A freely downloadable book on Discrete Math is here.

(ppt) Power Point Slides
5 Video from this year (5 mins)
Video from past terms
See video above
Video covers more than needed.
Video Missing
Pooh

0 Intro: (ppt)

00 1:35 Administrative Details
01 30 Summary of Course

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.)
           Jeff's Logic Chapter, Logic Questions, & Solutions

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

01 1:03 History & Overview
01 Church's Thesis
01 Goto vs Loop Models
02 35 Table Look Up and TM
03 36 Turing Machines
04 1:48 Levels of Abstraction
05 1:03 Sum mod 100 Example
06 17 Compile Time vs Run Time
06 17 Steps for writing a TM from Java code
07 48 3:23 Shifting Example
07 80 30 Insertion Sort
08 16 Adding Example (single tape)
08 Adding Example (multi tape)
08 Table Lookup Example
09 4 Single vs Multi Tape TMs
09 5 Java to TM
09 5 Constant vs Finite vs Infinite
10 14 Universal TM
11 20 Other Models of Computation
12 4 Languages, Machines, and Classes

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

01 14 Read-Once and Bounded Memory
02 Constant Memory
03 6 Loop Invariants
04 4 Code with Simple Loop
05 10 Deterministic Finite Automata
06 Path Through Graph
07 19 Focus on States
08 10 DFA: Formal Definition
09 6 10 DFA "knowing" and distinguishable strings
10 25 (Extended) Regular Expressions
11 16 Parsing with Regular Expressions
12 Examples:
1 27 Simple examples
2 11 0*1* vs 0n1n
3 30 Mod Counting
4 4 Any Finite Language
5 5 Adding two Integers
6 7 Calculator
7 5 Syntax Processor

14 Nondeterministic Finite Automata:
1 24 Fairy God Mother Story
2 13 Contains 0101
3 73 Restaurant
4 24 Middle Third
15 Proofs:
1 15 L(M)=L
2 11 L(M)=L Method 2
3 44 Proof L(M)=L Eg 2
90 1:20 DFA Review

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

01 19 37 70 Closure Properties
02 10 Complexity Classes
03 11 8 NFA to DFA
04 19 19 Extended Regular to DFA (short/Eg)
05 1 23 20 NFA to Regular Expression (short/long)
06 7 Complex Conversion Example
07 39 74 50 1:08 The Bumping Lemma
90 36 Review

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

01 29 Context Free Grammars
          Chomsky Hierarchy
          Ambiguity
          Java Like Example
          Human Languages
02 22 Union, Concat, Spew, & Plop
03 13 Recursion
04 8 28 Parsing/Compiling (short/long)
05 36 Not Closed under Complement
06 11 24 Closure and Proof Big Enough (short/long)
07 3 NFA to Context Free Grammar
08 4 18 Push Down Automata (short/long)
09 5 14 Parsing using Dynamic Programming (short/long)
10 12 41 TM to Context Sensitive Grammars (short/long)

Computational problems, machines, and inputs
67    Computing ∃ Alg A, ∀ Inputs I, A(I)=P(I)
39 57 7      - Coding Phase vs Execution Phase ∃ Alg A, ∃ # k, ∀ Inputs I, ∃ time t, A(I)=P(I) & Lines(A,I)=k & Time(A,I)=t
27 58      - Compiling Java to TM ∀ Java Programs J, ∃ TM M, ∀ input I, J(I)=M(I)
  Computable vs Uncomputable ∃M∀I M(I)=P(I) vs ∃P∀M∃I M(I)≠P(I)
54   Time Complexity ∃M∃c∀I M(I)=P(I) and Time(M,I)≤ |I|^c
44   Classifying Functions f(n)∈O(g(n)) ≡ ∃c∃n₀∀n≥n₀ f(n) ≤ cg(n)
  Coding Phase vs Execution Phase Before input is chosen vs after
6   Table Look Up vs TM ∀k∃M_table∀x,y≤k M_table(x,y)=x×y   vs   ∃M∀x,y M(x,y)=x×y
26   Probabilistic Algorithms ∃M∀I Pr_R[M(I,R)≠P(I)] ≤ 2^-|R|
5   Universal TM ∃ TM M_U, ∀ TM M, ∀ input I, M_U(M,I) = M(I)
63   Hugely Expressive There is a first order logic sentence Compute(J,I,y)
that states computer program J on input I outputs y.

Complexity (Math 1090) (

12   Computing vs Accepting Halt(M,I,t) is computable   and   Halt(M,I) ≡ ∃t Halt(M,I,t) is not
1   Poly vs NP Sat(C,I) is in poly   and   Sat(C) ≡ ∃I Sat(C,I) is likely not
56 50   NP Clause-Sat(I) ≡ ∃S ∀C ∃x "Assignment S satisfies variable x in clause C"
  Reductions [∀I [Sat(I) iff P(InstanceMap(I))]] ⇒ [Sat≤P]
24   Uncomputable Problems ∃P ∀M ∃I M(I)≠P(I)
  Halting & MathTruth Knowing whether a TM M halts or a first order sentence α is valid
are both uncomputable.
7   Gödel's Incompleteness No formal proof system is capable of proving all valid
and no invalid formulas about the integer.
To guarantee a proof, α needs to also be true in every nonstandard model.

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

60 Shorter Description vs Finite Description vs Infinite Description
68 35 Description Length and Carnality
53 Countable
Countable via a List
Countable via Finite Descriptions
Uncountable
Hierarchy of Infinities
Some Uncomputable Problem

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

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

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

1 84 37 Simple Reductions
2 30 Is Regular
3 11 Not Halt
4 36 Rice's Theorem
5 20 Harder Examples Quick
6 40 30 Recognizable

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

33 Gödel's Incompleteness Theorem
Halting << Math Truth

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.)

00 84 NP-Reductions (Quick)
00 56 50 Card Reduction (Logic)
01 31 History & Overview
02 7 Course vs Schedule
03 14 More about Reductions
04 10 Circuit vs Airplane
05 24 Circuit vs 3-Colouring
06 31 Definition Review

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

Jeff's ML Chapter
84 Recognize Digits in Python(Google)
94 3blue1brown
- IEEE Talks,
1) 94 Introduction to Machine Learning (slides) (video)
2) 82 Algebra Review (slides)
3) 74 Generalizing from Training Data (slides)
4) Nov 23: Reinforcement Learning Game Tree / Markoff Chains (slides)
5) Nov 30: Dimension Reduction & Maximum Likelihood (slides)
6) Dec 07: Generative Adversarial Networks (slides)
7) Dec 14: Ethics (slides)
- 2021:
01 105 Labs 1 & 2
02 108 87 Lab Jeff

- Teaching in Cameroon in 2020
- Taught for EECS2001 in 2019
- A Good Book

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.