Readme, Course Information, Course Description, Dates, Photos Fun, Your Marks (4111,5111) Forum, Class

Topics	Slides	Videos	Steps	Notes	Questions	Solutions	Tests
Quantifiers (Take up Exam Question.)
Turing Machines
Models of Computability
Complexity Classes
Diagitization & Uncomputability
Reductions For Uncomputability
No Proof System for Number Theory
NP-completeness		(sols)
Other Possibilities

About Course:
     This course is an extention of 2001. It 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.

Texts:

Course Description
About Turing: Article
Steve Cook: Computability and Recursive and Recursively Enumerable Sets
Russell Impagliazzo Notes
Jeff Edmonds' "How to Think about Algorithms"   Amazon   Cambridge House Press   Desk Copies   reviews
Michael Sipser, Introduction to the Theory of Computation, (second edition) PWS Publishing Company, 2006.
Lewis and Papadimitriou, Elements of the Theory of Computation (second edition) 1998.
Hopcroft, J.E. and Ullman, J.D., Introduction to Automata, Languages and Programming, Addison Wesley, 1979.
Gems of Theoretical Computer Science (Many thanks to U. Schoning and R. Pruim)
Other References

Introduction: (ppt)

Quantifiers: (Steps, ppt, Questions)
           (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.)

Existential and Universal quantifiers

Turing Machines: (ppt, Questions)
           (Historic and mathematical ways of modeling machines for computing.)

History & Overview
Church's Thesis
Goto vs Loop Models
Turing Machines
Loop Invariant Example
Adding Example (single tape)
Adding Example (multi tape)
Table Lookup Example
Single vs Multi Tape TMs
Java to TM
Constant vs Finite vs Infinite
Universal TM

Other Models of Computability: (ppt, Cook, Questions)
           (More Historic ways of modeling machines for computing.)

Primitive Recursive
TM to Primitive Recursive?
Primitive Recursive << TM
TM to Recursive
Register Machine
And/Or/Not Circuits
Computer Circuits
Circuits Depth
Arithmetic Circuits
Neural Nets
Poly-Time
Non-Deterministic Machines
Quantum Machine
Context Free Grammars
Java to Machine Code (Compiling/Parsing) (pdf, Java)
Context Sensitive Grammars
TM to Grammar
Decide vs Accept
Humans
Complexity Classes

Complexity Classes: (ppt, Questions)
           (We classify computational problems based on the amount of resources
           used to compute them.)

Computable using Halting as an oracle
Acceptable, Witness, Enumerable
Computable
Ackermann's Time
Double Exponential Time
E: Exponential Time
Exp Time
PSpace
PH: Poly-Time Hierarchy
NP & Co-NP
Poly-Time
NC: Poly-log depth Circuits
NC2
NL: Non-Det Log Space
L: Log-Space
AC0, Thres0, Arith0: Constant Depth
NC0: Constant Fan-out

Diagonization & Uncomputability: (ppt, Cook, Questions)
           (There are more real numbers than fractions and the same number of
           fractions as integers.)
           (Some computational problems are solved by NO algorithms.)

Uncountable Infinity & Diagonalization
Diagonal Uncomputable
Halting Problem
Time Hierarchy

Reductions For Uncomputability: (ppt, Cook, Questions) (3*1.5hrs)
           (Knowing that some computational problems are hard, we prove that
           others are.)

Reductions
Simple Reductions
Rice's Theorem
Reverse Reduction
Acceptable
The Post Correspondence Problem
Tiling (Impagliazzo)
CFG G Generates I
CFG G Generates Every String
CFG G Generates Some String
CFG L(G)=L(G')
Game of Life
Hilbert's Tenth Problem (Gems)

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

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

NP-completeness: (ppt, pdf, Questions)
           (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
Circuit vs Airplane
Circuit vs 3-Colouring
Non-Deterministic Poly-Time
Reductions
K-Clique vs K-Independent Set
12 Steps
Any P <= Sat
3-Col <= 3-Sat
Sat <= 3-Col
More Problems
12 Steps in More Depth
Making Change scan
Embedding points with distortion pdf

Kolmogorove Complexity
Time/Space Trade offs Pebbles (pdf)
Cryptography: RSA (Josh, ppt)
Distributed Systems: mud on forehead & common knowledge
# of prime numbers
Intro to Quantum: Shor's factoring
Rudich's course

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.