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
www.cs.virginia.edu/robins
Phone: (434) 982-2207
Office: 406 Rice Hall
Gabe's Vitae / Resume (NIH Biosketch)

Lecture videos:


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.

  1. Lecture 1: syllabus, course overview, organization, readings, centrifuge problem, beautiful proofs

  2. Lecture 2: historical perspectives, Archimedes, Eratosthenes, al-Hasan, Fibonacci, decimal number system, Descartes, coordinates, Fermat, Fermat's Last Theorem, Pascal, Newton, Euler, graph theory

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

  4. Lecture 4: dovetailing, cardinality of the rationals and the reals, diagonalization, non-existence proofs, Cantor sets, Russell, Principia Mathematica, Russell's paradox, Hardy, Ramanujan

  5. Lecture 5: Ramsey, Pigeon-hole principle, Ramsey theory, Hilbert, Hilbert's problems, Goldbach's conjecture, Millennium Prize, Hilbert's Tenth Problem, packings and tilings

  6. Lecture 6: aperiodic tilings, DARPA's problems, Godel, incompleteness, Turing, apologies, countability of algorithms, uncountability of functions, the halting problem,

  7. Lecture 7: the halting problem, halting and mathematical proof, undecidability, finitely-describable numbers, uncomputable numbers, misconceptions, Turing's seminal paper

  8. Lecture 9: regular expresions, FA minimization, characterizations, generalized finite automata, identities, decidable FA problems, RE/TM minimization, context-free grammars and lanugages, derivations, palindromes

  9. Lecture 8: Shannon, entropy, Kleene, Chomsky, formal languages, Kleene closure, finite automata, JFLAP, cross-product construction, closure properties, powerset consruction, nondeterminism

  10. Lecture 10: context-free grammars and lanugages, pushdown automata, closure properties of CFLs, decidable PDA / CFG problems, PDA enhancements

  11. Lecture 11: pushdown automata, undecidable PDA / CFG problems, PDA enhancements, proving non-regularity, pumping theorem

  12. Lecture 12: non-regular languages, pumping theorem reloaded, Turing machines and variations, alphabet size, double-infinite tapes, multiple heads and tapes, 2D tapes, nondeterminism

  13. Lecture 13: Turing machines, TM enhancements, multitapes, nondeterministic TMs, combining multiple enhancements, decidability, recognizability, enumeration, lexicographic orderings

  14. Lecture 14: recognition vs. enumeration reloaded, characterization theorems

  15. Lecture 15: decidability, recognizability, closure properties, reducibilities, reductions, undecidability of halting on empty input

  16. Lecture 16: reductions, undecidability of halting on empty input, undecidability of language emptyness and regularity, language properties, Rice's theorem, the extended Chomsky hierarchy

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

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

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

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

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

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

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

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

  3. Lecture 3: summary of Cantor / infinities / countability, dovetailing, uncountability of reals, diagonalization, non-existence proofs, Cantor sets, Aristotle, the scientific method

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  10. 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:

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

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