Dr. Gabriel Robins Professor of Computer Science Department of Computer Science School of Engineering and Applied Science University of Virginia 85 Engineer's Way, P.O. Box 400740 Charlottesville, VA 22904-4740, USA
robins@cs.virginia.edu |

Theory of Computation (CS3102), Spring 2017:

These lectures are also available in a YouTube playlist format.

See the lecture slides (in Powerpoint and PDF formats) on the Theory of Computation (CS3102) course Web site.

- Lecture
1: syllabus, course overview, organization, readings, centrifuge
problem, beautiful proofs
- Lecture
2: historical perspectives, Archimedes, Eratosthenes, al-Hasan,
Fibonacci, decimal number system, Descartes, coordinates, Fermat,
Fermat's Last Theorem, Pascal, Newton, Euler, graph theory
- Lecture
3: Gauss, Hamilton, generalized numbers, Boole, De Morgan,
symbolic logic, Babbage, the analycical engine, Ada Lovelace, John
Venn, set theory, Lewis Carroll, Georg Cantor, infinities, transfinite
arithmetic, infinite hotels, dovetailing
- Lecture
4: dovetailing, cardinality of the rationals and the reals,
diagonalization, non-existence proofs, Cantor sets, Russell, Principia
Mathematica, Russell's paradox, Hardy, Ramanujan
- Lecture
5: Ramsey, Pigeon-hole principle, Ramsey theory, Hilbert,
Hilbert's problems, Goldbach's conjecture, Millennium Prize, Hilbert's
Tenth Problem, packings and tilings
- Lecture
6: aperiodic tilings, DARPA's problems, Godel, incompleteness,
Turing, apologies, countability of algorithms, uncountability of
functions, the halting problem,
- Lecture 7: the halting problem, halting and mathematical proof, undecidability, finitely-describable numbers, uncomputable numbers, misconceptions, Turing's seminal paper
- Lecture
9: regular expresions, FA minimization, characterizations,
generalized finite automata, identities, decidable FA problems, RE/TM
minimization, context-free grammars and lanugages, derivations,
palindromes
- Lecture
8: Shannon, entropy, Kleene, Chomsky, formal languages, Kleene
closure, finite automata, JFLAP, cross-product construction, closure
properties, powerset consruction, nondeterminism
- Lecture
10: context-free grammars and lanugages, pushdown automata,
closure properties of CFLs, decidable PDA / CFG problems, PDA
enhancements
- Lecture
11: pushdown automata, undecidable PDA / CFG problems, PDA
enhancements, proving non-regularity, pumping theorem
- Lecture
12: non-regular languages, pumping theorem reloaded, Turing
machines and variations, alphabet size, double-infinite tapes,
multiple heads and tapes, 2D tapes, nondeterminism
- Lecture
13: Turing machines, TM enhancements, multitapes,
nondeterministic TMs, combining multiple enhancements, decidability,
recognizability, enumeration, lexicographic orderings
- Lecture
14: recognition vs. enumeration reloaded, characterization
theorems
- Lecture
15: decidability, recognizability, closure properties,
reducibilities, reductions, undecidability of halting on empty input
- Lecture
16: reductions, undecidability of halting on empty input,
undecidability of language emptyness and regularity, language
properties, Rice's theorem, the extended Chomsky hierarchy
- Lecture
17: computational universality, minimal universal TM, computing
using legos / water pipes / billiards / gravity, Church-Turing thesis,
what we can and can't compute, board games, self-driving cars, chaos
- Lecture
18: computational universality, fractals, computer art,
Church-Turing thesis, resource-bounded computation, time and space
complexity classes, Turing machines, tape-dependence of time and
space, space-time relations and tradeoffs
- Lecture
19: reducibilities reloaded, complexity classes, P, NP, PSPACE,
time and space relationships, Savitch's theorem, Complexity Zoo,
extended Chomsky hierarchy reloaded, NP-hardness, NP-completeness,
polynomial-time reductions, problem transformations, Boolean
satiafiability (SAT), Cook-Levin theorem
- Lecture
20: NP-completeness, Cook-Levin theorem, historical notes,
guess-and-verify, robustness of P and NP, Millenium Prize, 3-SAT,
classic NP-complete problems, cliques, covers, coloring, partitioning,
knapsack, packing
- Lecture
21: Steiner trees, traveling salesperson, Karp's seminal paper,
decision vs. optimization, NP-completeness of graph cliques /
independent sets / graph colorability, restricted degree and planarity
considerations, approximation algorithms, minimum vertex cover
heuristic
- Lecture 22: robotics and automation, artificial intelligence, science fiction becoming reality, technological singularity, list of topics covered, "ask me anything" session

Theory of Computation (CS3102), Spring 2018:

See the lecture slides (in Powerpoint and PDF formats) on the Theory of Computation (CS3102) course Web site.

- Lecture
1: centrifuge problem, textbooks, course outline / syllabus,
grading scheme, cheating policy, required readings, scale of the
universe, good advice, do not procrastinate, TAs speak on cheating,
centrifuge problem revisited
- Lecture
2: centrifuge problem revisited, sum-of-integers, elegant proofs,
drawbacks of induction, proofs by picture, more problems with elegant
solutions, Georg Cantor, infinite hotels, one-to-one correspondences,
countability of rationals, dovetailing
- Lecture
3: summary of Cantor / infinities / countability, dovetailing,
uncountability of reals, diagonalization, non-existence proofs, Cantor
sets, Aristotle, the scientific method
- Lecture
4 (there is also an alternate
camera-angle version of this lecture): Kleene, Chomsky, formal
languages, definitions, alphabets, strings, languages, concatenation,
exponentiation, union, intersection, Kleene closure, Sigma-star,
complementation
- Lecture
5: review of definitions, finite automata, regular languages,
acceptance / rejection, transition functions, closure properties,
complementation, JFLAP, intersection, cross-product construction,
union, set differnece, XOR, "Next" movie
- Lecture
6 (there is also an alternate
camera-angle version of this lecture): review of finite automata,
non-determinism, powerset construction, "Next" movie, benefits of
non-determinism, regular expressions, type errors, converting regular
expressions into finite automata, automta minimization, converting
finite automata into regular expressions, generalized finita automata,
characterization equivalence between finite automata and regular
expressions
- Lecture
7 (there is also an alternate
camera-angle version of this lecture): Alan Turing, countability
of algorithms, uncountability of functions, what is a function,
algorithms / code vs. functions, non-computability, the halting
problem, short but difficult instances of halting problem, embedding
arbitrary mathematical conjectures as halting problem instances, the
"3x+1" problem, Turing's proof of the non-computability of halting
problem, algorithms vs. "magic"
- Lecture
8 (there is also an alternate
camera-angle version of this lecture): halting problem review,
inputing a program to itself, non-finitely-describable real numbers,
uncomputable reals, example of an uncomputable number, complete
descriptions, is "2" real?, if the halting problem was computable,
uncountability of the non-finitely-describable and the uncomputable
reals, subsets are not necessarily "simpler", infinite graphs, halting
problem misnomers, sometimes-incorrect algorithms, detecting only the
halting programs, "infinite runtimes", meaningless words, Turing's
seminal paper, computational universality, smartphones and compilers
- Lecture
9 (there is also an alternate
camera-angle version of this lecture): equivalence of regular
languages and regular expressions, regular expression identities,
decidable properties of finite automata, language emptiness, language
finiteness, finite automata equivalence, context-free grammars,
context-free languages, palindromes, well-balanced parenthasis,
ambiguity in English / languages / programming / art
- Lecture
10 (there is also an alternate
camera-angle version of this lecture): review of context-free
grammars (CFGs), context-free languages (CFLs), palindromes,
well-balanced parenthasis, ambiguity, pushdown automata (PDAs),
non-deterministic PDAs, recognition by PDAs of 0^n1^n and w$w^R,
equivalence of PDAs and CFGs, closure properties of CFLs, union
preserves context-freeness
- Lecture 11 (there is also an alternate camera-angle version of this lecture): closure properties of context-free languages (CFLs): union / Kleene star / intersection with regular sets, non-closure under intersection and complementation, non-closure under infinite number of operator applications, decidable and undecidable properties of CFLs / PDAs / CFGs, PDA enhancements: 2-way / 2-stacks / queue automata / 2-heads / non-determinism, non-regularity, pumping theorem, misnomers about pumping, "prime" strings, pumping for CFLs

Theory of Computation (CS6160), Spring 2018:

See the lecture slides (in Powerpoint and PDF formats) on the Theory of Computation (CS6160) course Web site.

- Lecture 1
(part 1 of 2): centrifuge problem, textbooks, course organization
/ syllabus, grading scheme, cheating policy, course readings, scale of
the Universe, discrete math review slides, basic concepts and notation
glossary, good advice, centrifuge problem revisited, elegant proofs,
sum-of-integers, proofs by picture, drawbacks of induction, more
problems with elegant solutions, historical perspectives, Georg
Cantor, infinite hotels, one-to-one correspondences, dovetailing,
countability of rationals, dovetailing reloaded, uncountability of
reals
- Lecture 1
(part 2 of 2): uncountability of reals, diagonalization, societies
that don't have numbers, attempted end-runs around diagonalization,
non-uniqueness of decimal representation, non-existence proofs, Cantor
sets, Aristotle, the scientific method, Euclid, the axiomatic method,
Euclid's axioms, the parallel postulate, independence of the axioms,
non-Euclidean geometries, our non-Euclidean Universe, relativity
theory, spherical geometry, a non-Euclidean riddle
- Lecture 2
(part 1 of 2): Archimedes, Eratosthenes, the Antikythera, Ibn
al-Haytham, Fibonacci, positional number systems, golden ratio,
Descartes, coordinates, Fermat, Wiles's proof of Fermat's last
theorem, problems with elegant solutions, Pascal, early mechanical
calculator, Newton, Principia Mathematica, stamps, Euler, Bridges of
Konigsberg, graph theory, Euler's identity, Euler's formula,
applicaitons of graphs, Gauss, Hamilton, quaternions, octonions,
sedenions, generalized numbers, surreal numbers,
non-finitely-describable numbers, uncomputable numbers, countability
of programs / algorithms, dovetailing, uncountability of Boolean
functions, diagonalization
- Lecture 2
(part 2 of 2): uncountabiliby of the Boolean functions,
uncountabiliby of the reals, simple program that prints out all
programs, "size doesn't matter" w.r.t. difficulty of determining
halting, arbitrary deep theorems as short codes, proving the
uncomputability of the haltiong problem, "Pinocchio's paradox",
solving the halting problem with oracles / magic / deities, infinite
loops, non-finitely-describable reals, computable numbers are finitely
describable, halting problem misnomers
- Lecture 3
(part 1 of 2): formal languages, alphabets, strings, languages,
concatenation, exponentiation, reversal, union, intersection,
difference, Kleen closure, complementation, sigma-star is countable,
powerser of sigma-star is uncountable, finite automata, states,
transitions, initial and final states, fully-specified finite
automata, language acceptance, complementation preserves regularity,
JFLAP, closure under intersection, cross-product construction, more
closure properties (union, difference, and XOR), identity-based proofs
- Lecture 3
(part 2 of 2): non-determinism, powerset construction, two-way
finite automata, epsilon transitions, "Next" film, reasons to study
non-determinism, regular expressions, converting regular expressions
to finite automata, finite automata minimization, impossibility of
minimization in general, converting finite automata to regular
expressions, generalized finite automata, regular expression
identities, decidable finite automata properties, language emptiness,
language finiteness, laguage equivalence, regular expression
minimization, undecidability of Turing machines minimization
- Lecture 4
(part 1 of 2): regular expressions and finite automata review,
context-free grammars, derivations, context-free languages (CFLs),
palindromes, well-balanced parenthesis, context-freeness of regular
expressions, ambiguity in speech / programming / math / art, ambiguous
grammars, ingeretnly ambiguous languages, pushdown automata (PDAs),
non-determinism in PDAs, equivalence of context-free grammars and
PDAs, closure properties of CFLs, closure under union / Kleene star,
proving theorems several different ways, redundancy in engineering,
Intel Pentium FDIV bug, CFL closure under intersection and
complementation, De Morgan law -related closures and proofs
- Lecture 4
(part 2 of 2): decidable properties of context-free langauges and
grammars, CFL emptiness / finiteness, parsing, compilers, undecidable
properties of context-free langauges and grammars, PDA minimality /
equivalence, CFG minimality / ambiguity / equivalence, emptiness of
intersection, inherent ambiguity, PDA enhancements, 2-way PDAs,
2-stack PDAs, queue automata, 2-head PDAs, non-deterministic PDAs,
non-regular languages, pumping theorem, 0^n1^n, type errors revisited,
the set of English words is regular
- Lecture 5
(part 1 of 2): review of pushdown automata / non-determinism /
closure properties of CFLs / decidable properties of CFLs & CFGs / PDA
enhancements. pumping revisited, cube-free and square-free strings,
complementation revisited, "the truth - the whole truth - and nothing
but the truth", Library of
Babel
- Lecture 5
(part 2 of 2): Turing machine enhancements, decidability vs.
recognizability, recognition and enumeration, halting problem language
is recognizable but not decidable, decidability and
lexicographic-order enumerability, building an enumerator from a
recognizer, building a recognizer from an enumerator, dovetailing
enumeration, avoiding duplicates, parallel enumeration, Chomsky
hierarchy, why is it difficult to decide / recognize.
sums-of-three-cubes, Diaphantine equations, Hilbert's Tenth Problem,
closure properties of decidable and recognizable languages

A Brief History of Computing, Spring 2018:

- A Brief
History of Computing (Part 1 of 2) video, the Powerpoint
slides, and PDF

(there is also an alternate camera-angle version of this lecture): why study the history of computing, "standing on the shoulders of giants", Aristotle, the scientific method, Euclid, axiomatic systems, Euclid's axioms, non-Euclidean geometries, our non-Euclidean Universe, Eratosthenes, the Antikythera, Alhazen, Fibonacci, decimal number system, Descartes, coordinates, Fermat and his Last Theorem, Pascal, early hand-held calculator, Newton, Principia Mathematica, Euler, the ubiquity of graph theory, Gauss, Hamilton, quaternions, generalized numbers, Boole, De Morgan, Babbage, difference engine, analytical engine, Ada Lovelace - A Brief
History of Computing (Part 2 of 2) video, the Powerpoint
slides, and PDF

(there is also an alternate camera-angle version of this lecture): Ada Lovelace, John Venn, set theory, Lewis Carroll, Alice in Wonderland, semantics, Cantor, infinities hierarchy, transfinite arithmetic, infinite hotels, Russell, Principia Mathematica, Russell's paradox, Hilbert, Hilbert's list of open problems, Hilbert's Tenth Problem, Matiyasevich, sphere packing, aperiodic tilings, Godel, incompleteness theorem, Turing, defining computation, deciphering the Enigma, computational universality, Church-Turing thesis, artificial intelligence, Tesla Model S, neural nets, machine learning, von Neumann

Return to Gabriel Robins' home page