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.)
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.)
Machine Learning Made Easy:
(The basic math needed to understand machine learning)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.