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 as a long playlist in a YouTube playlist format:

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

The individual lectures are also listed below:

  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.

These lectures are also available as a single long continuous playlist in a YouTube playlist format as follows:

The individual lectures are also listed below:

  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:

  12. Lecture 12 (there is also an alternate camera-angle version of this lecture): the Chomsky Hierarchy, regular / context-free / decidable / recognizable languages, Turing machines (TMs), tapes, tape alphabet, TM recognition, power and generality of TMs, TM to recognize 0^n1^n2^n, "marking" the tape, arbitrary complexity arises from interacting simple parts, accepting and rejecting strings, "crossing off" tape characters, "simplicity" and ubiquity of the Turing machine model, TM "enhancements", larger alphabets, double-sided infinite tapes, multiple heads, multiple tapes, two-dimensional tapes, row-major order, compositions:

  13. Lecture 13 (there is also an alternate camera-angle version of this lecture): Turing machine "enhancements", larger alphabets, double-sided infinite tapes, multiple heads, multiple tapes, higher-dimensional tapes, non-determinism, combinations of enhancements, commutativity of compositions, equivalent TMs and programs, recognizability vs. decidability vs. enumerability, decidability and lexicographic orders, recognizability and enumerability, parallel simulation, non-response vs. explicit no, "simple" examples of recognizable non-decidable sets:

  14. Lecture 13: Chomsky hierarchy revisited, closure properties of decidable and recognizable languages, reducibilities / reductions, additional undecidable problems, the halting problem on the empty string, existence vs. knowing the value, the language emptyness problem, the language regularity problem, language properties, undecidability of almost all properties, Rice's theorem:

  15. Lecture 15 (there is also an alternate camera-angle version of this lecture): type errors revisited, reducibilities, examples of reductions, properties of recognizable languages, uncountability of the properties, the two trivial properties, Rice's theorem, corollaries and misapplications of Rice's theorem, negative results, Streisand Effect, Chomsky hierarchy revisited, closure properties of decidable and recognizable languages:

  16. Lecture 16 (there is also an alternate camera-angle version of this lecture): computational universality, the Church-Turing thesis, equivalent computational systems, smallest universal Turing machine, computational universality of toys / nuts-and-bolts / water pipes / billiards, complex gravitational systems, chaos and the butterfly effect, computable puzzles and games, chess, Jeopardy, AlphaGo, self-driving cars and Tesla Model S, uncomputable things: humor / emotions / weather / turbulence / tsunamis / elections / compound pendulums, fractals, algorithmic art, context-sensitive grammars and languages:

  17. Lecture 17 (there is also an alternate camera-angle version of this lecture): Chomsky hierarchy reloaded, resource-bounded computation, time / space / other resources, the dramatic difference between disk & RAM speeds, complexity classes, deterministic vs. non-deterministic time & space, time is tape-dependent, space is tape-independent, 1-tape simulation of k-tapes, 0^n1^n is in DTIME(n^2) / DSPACE(n) / DTIME(n log n) for 1-tape TMs, 0^n1^n is in DTIME(n) and DSPACE(log n) for 2-tape TMs

  18. Lecture 18: review of resource-bounded computation / time and space complexity classes / time-space usage and tradeoffs / P / NP / PSPACE / EXPTIME / EXPSPACE / LOGSPACE, space-time relationships, re-usability of space vs non-re-usability of time, Genie-in-a-Bottle, eliminating non-determinism w.r.t. time and space, Chomsky hierarchy reloaded, time complexity hierarchy, space complexty hierarchy, preview of Savitch's theorem

  19. Lecture 19: the course TAs talk at length to the class about cheating/plagiarism -related issues - please don't cheat!, the Chomsky hierarchy revisited, infinite time and space hierarchies, proof of Savitch's theorem, dramatic time-space tradeoffs, NPSPACE = PSPACE, space analogue of P=NP question, non-deterministic space is closed under complementation, Immerman's theorem

  20. Lecture 20: review of space/time complexity classes and their relationships, denseness of the space and time hierarchies, proper and non-proper containments among complexity classes, P=NP -type open problems, extended Chmosky hierarchy reloaded, other proper infinite hierarchies, Turing degrees and levels of impossibility, star-height regular hierarchy, infinities hierarchy, powersets, Rucker's book "Infinity and the Mind", fast-growing functions, gap theorem, non-computable time/space bounds, complexity gap between constance and log-log space, speedup theorem, Traveller's Dillema and Nash equilibria, complexity pathologies, abstract complexity theory, alternation, "Snakes on Every Plane", generalized two-player games, exploring the "Complexity Zoo"

  21. Lecture 21: resource-bounded computation, the "Complexity Zoo", the extended Chomsky hierarchy reloaded, NP-completeness, tractability, computation vs. decision, non-determinism, reducibilities reloaded, polynomial-time reductions, problem transformations, NP-hardness and -completeness, P=co-P, is NP=co-NP?, logspace reductions, Boolean Satisfiability (SAT), history of the Cook-Levine theorem, Garey & Johnson's classic NP-completeness book, practical benefits of NP-completeness, proof of the Cook-Levine theorem

  22. Lecture 22: recap of NP-completeness, tractability / parallelism, polynomial-time reducibilities, NP-hardness, Satiafiability, Cook-Levin theorem, "guess and verify" non-deterministic algorithms, why P=NP is difficult to resolve, robustness of P and NP, quantum computing, reduction types, 3-SAT, graph cliques, set covers, Hamiltonian cycles, graph coloring, partitioning

  23. Lecture 23: NP-completeness reloaded, satisfiability, 1-SAT, 2-SAT, 3-SAT, cliques, covers, Hamiltonian cycles, graph coloring, partitioning, knapsacks, bin packing, Steiner trees, traveling salesman, moving-target TSP, TSP heuristics, 2-OPT, triangle inequality, graph colorability, Karp's seminal paper, reductions scheme, origin of NP-completeness

  24. Lecture 24: classic NP complete problems, decision vs. optimization, building optimizers from deciders, "playing Twenty-Questions", graph clique problem is NP-complete, independent set problem is NP-complete, graph colorability is NP-complete, "OR gate" gadget, example of reducing Boolean satisfiability to graph 3-colorability, colorability of degree-bounded graphs, 1-colorability, 2-colorability, degree-0 / degree-1 / degree-2 colorability

  25. Lecture 25: bounded-degree graph colorability, NP-completeness of max-degree-4 graph colorability, degree-reduction "gadgets", 3-colorability constraint-propagation, local replacement of nodes by super-gadgets, threshold of intractability, 2-colorability, odd cycles, infinite graphs, chromatic numbers, membership-preserving transformations, planar graphs, Kuratowski's theorem, planarity-preserving gadgets, NP-completeness of 3-coloring planar graphs, composing reductions, 3-colorability of planar max-degree-4 graphs is NP-complete, searching for smaller / simpler gadgets, Four-Color Theorem, graph-colorability on tori

  26. Lecture 26: graph coloring applications, job scheduling, register allocation, non-approximability, solving large instances, SAT solvers, approximation schemes, provably-good heuristics, local vs global minima, "wishful thinking" approaches, minimum vertex covers, 2*OPT approximation for minimum vertex covers, worst-case vs. average-case behaviors, heuristic variations, counter-examples, bound-preserving meta-heuristics, maximum-cut problem, 2*OPT approximation for maximum cut, 2-OPT swaps and other variations, 2*OPT approximation for metric traveling salesperson tours, triangle inequality, (1+e)*OPT geometric TSP approximation

  27. Lecture 27: graph isomorphism, friend-or-foe identification, zero-knowledge proofs, graph isomorphisms as "secrets", "approximating" mathematical proofs, caveats and pitfalls, exams as "proof protocols", zero-knowledge proofs for other NP problems, IP=PSPACE, zero-knowledge protocols in financial transactions, the Turing test, defining intelligence, who/what can "think"?, Turing's seminal paper, "The Imitation Game", "The Turk", Eliza, Elbot, who/what can pass the Turing test?, AI's from Star Wars / Star Trek / Terminator / Matrix / Battlestar Galactica / Blade Runner, criticisms of the Turing Test, the Chinese Room scenario, The Matrix triology, reverse Turing tests / CAPCHAs, Frankenstein stories, robots in movies, self-driving cars

  28. Lecture 28: the Turing test (continued), who/what can pass the Turing test?, Frankenstein stories, sentient beings from science fiction movies, Westworld, Asimov's Laws of Robotics, robotics on land / air / sea / space, DARPA's Urban Challenge, self-driving cars, biped robots, exoskeletons, robotic surgeons, societal resistance to new technology, robots in space, robots in factories, robotic pets, exo-skeletons, robotic surgeons, reality surpasing science fiction, Star Trek communication vs. smart phones, chess playing, "IBM Watson" Jeopardy AI, Google "Alpha Go", robotic household appliances, cloaking devices, technological singularity, gray goo, law of accelerating returns, augmented humans, course summary: concepts / techniques / ideas / proofs, Occam's razor, "Ask Me Anything" session



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:

  11. Lecture 6 (part 1 of 2): recognizable vs. decidable, enumeration and lexicographic order, closure properties of decidable and recognizable languages, reducibilities / reductions, the halting problem on the empty string, Rice's theorem, properties, ubiquity of undecidability, the Chomsky hierarchy revisited, proper and non-proper containments, space and time hierarchies

  12. Lecture 6 (part 2 of 2): generalized numbers, Boole, De Morgan, Babbage, difference and analytical engines, Ada Lovelace, Venn, Venn diagrams / humor, Carroll, Alice in Wonderland, Through the Looking Glass, semantics, Cantor, Russell, Principia Mathematica, Russell's paradox, "Pinocchio's paradox", diagonalization disguised, Hardy, Ramanujan, the Hardy-Ramanujan number 1729, Ramanujan identities, Good Will Hunting, Ramsey, pigeon-hole principle, monochromatic triangles in K_6, Ramsey theory, order among chaos, Ramsey numbers, "The Big Picture"

  13. Lecture 7 (part 1 of 2): Hilbert and his list of open problems, the continuum hypothesis, consistency of the axioms, polyhedra dissections, axiomatization of physics, transcendental numbers, Riemann hypothesis, Goldbach's conjecture, Hilbert's Tenth Problem, Diophantine equations, Matiyasevich, universal polynomials, degree vs. dimension tradeoffs, Julia Robinson, space-filling tilings, sphere packing, aperiodic tilings, Penrose tilings, 3D tilings, tiling undecidability, gallery of aperiodic tilings, DARPA-hard problems, quantum computers

  14. Lecture 7 (part 2 of 2): Godel, incompleteness, automatic theorem proving, soundness, completeness, consistency, catastrophic inconsistency, Godel's incompleteness theorem, propositional logic, is mathematics consistent?, Church, Lambda calculus, Turing, halting problem, Russell's paradox, Lego / Mechano / Tinker Toy computers, nuts-and-bolts / hydraulic computers, smallest universal Turing machine, neural nets, oracles, hyper-computation, undecidability hierarchy, Turing degrees, the usefulness of negative / impossibility results

  15. Lecture 8 (part 1 of 2): review of Turing degrees, von Neumann, game theory, stored program, self replication, self-printing programs, Nash equilibria, von Neumann architechtures / languages / bottlenecks, functional programming, EDVAC, cellular automata, robotics, Shannon, digital circuits, information theory, entropy, randomness, compression:

  16. Lecture 8 (part 2 of 2): Kleene, regular expresions, Chomsky, linguistics, formal languages, grammars, resource-bounded computation, time and space complexity classes, multiple tapes, space/time tradeoffs and usage, P and NP, complexity analysis

  17. Lecture 9 (part 1 of 2): resource-bounded computation, time and space complexity classes, time-space usage and tradeoffs, P / NP / PSPACE / EXPTIME / EXPSPACE / LOGSPACE, space-time relationships, re-usability of space, non-re-usability of time, Genie-in-a-Bottle, eliminating non-determinism w.r.t. time and space, Savitch's theorem, Chomsky hierarchy reloaded, infinite time complexity hierarchy, infinite space complexity hierarchy, revisiting diagonalization / dovetailing / pigeon-hole principle, pathological / non-computable resource bounds / functions

  18. Lecture 9 (part 2 of 2): proof of Savitch's theorem, dramatic time-space tradeoffs, real-life time-money tradeoffs, P=NP and non-existence proofs, space closure under complementation / Immerman's theorem, enumeration of TMs for P / NP / PSPACE, denseness of infinite time and space hierarchies, pathological / non-computable time and space bounds, proper and non-proper complexity classes containment, additional P=NP -type open open questions, infinite dense proper hierarchies in the Chomsky hierarchy, star-depth regular hierarchy, Generalized Go is EXPTIME-complete, exploring the "Complexity Zoo"

  19. Lecture 10 (part 1 of 2): review of space/time complexity classes and relationships, P=NP -type open problems, gap and speedup theorems, axiomatic complexity theory, alternation, alternating complexity classes, alternation-related relationships, quantified Boolean formulas (QBF), Quantified Satisfiability (QSAT), two-player games, "completeness" of generalized games, the polynomial hierarchy, more open complexity class containment and non-containment problems, Chomsky hierarchy reloaded

  20. Lecture 10 (part 2 of 2): the course TAs talk about cheating/plagiarism -related issues - please don't cheat!, probabilistic Turing machines, the power of randomness in computation, Bounded-error Probabilistic Polunomial time (BPP), primality testing, BPP and the polynomial hierarchy, pseudorandom number generators, the "Complexity Zoo", the extrended Chomsky hierarchy, the "busy beaver" function, non-halting space-bounded computations, context-sensitive grammars, universality of context-sensitive grammars, Occam's razor

  21. Lecture 11 (part 1 of 2):

  22. Lecture 11 (part 2 of 2):

  23. Lecture 12 (part 1 of 2): review of some classic NP-complete problems, decision vs. optimization problems, building an optimizer from a decider, playing "Twenty Questions", "Obi-Wan has taught you well!", counting solutions and #P, NP and efficient verifiability, "guess and verify" algorithms, complexity of sorting vs verifying sortedness, graph clique problem is NP-complete, hard problems can have easy instances, independent set problem is NP-complete, graph coloraility is NP-complete, "gadget"-based reductions, solving satisfiability via colorability, colorability of degree-contrained graphs, odd cycles, colorability of max-degree-4 graphs is NP-complete, planar graph colorability, K_5 and K_3,3 are not planar, Kuratowski's theorem

  24. Lecture 12 (part 2 of 2): NP-completeness of planar graph 3-colorability, "gadget"-based proof, 3-colorability constraint propagation, NP-completeness of max-degree-4 planar graph 3-colorability, combining parameter constraints, composing reductions, four-color theorem, computer-generated proofs, planarity testing in linear time, colorability on torus-embedable graphs, coloring theorems for other manifolds, applications of graph coloring, optimization and local minima, heuristics and approximations, "wishful thinking" algorithms, 2*OPT vertex cover heuristic, practical optimizations, meta-heuristics, some NP-complete problems are not approximable, approximation-preserving transformations, 2*OPT approximation heuristic for maximum cuts, getting trapped in local minima, provably-good TSP heuristics, approximating proofs and zero-knowledge protocols

  25. Lecture 13 (part 1 of 2): heuristics and approximation algorithms, 2*OPT traveling salesperson heuristic, triangle inequality, 1.5*OPT TSP heuristic, minimum matchings, handshaking lemma, Euler tours, non-uniqueness of minimum spanning trees, negative weights, repeat node visits, bound-preserving post-processing, 2-OPT / 3-OPT / k-OPT, meta-heuristics, bounds vs. solution quality in practice, sorting example, bounds don't survive transformations, approximability and non-approximability, solving large SAT instances, branch-and-bound, Arora' s TSP approximation scheme, graph isomorphisim, friend-or-foe identification, zero-knowledge proofs, exams as "proof protocols", zero-knowledge proofs for other NP problems, IP=PSPACE, zero-knowledge protocols in financial transactions

  26. Lecture 13 (part 2 of 2): the Turing Test, defining intelligence, who/what can "think"?, Turing's paper, "The Imitation Game", "The Turk", Eliza, Elbot, sentient beings from Star Wars / Star Trek / Terminator / Matrix / Battlestar Galactica, Blade Runner, criticisms of the Turing Test, the Chinese Room scenario, The Matrix triology, reverse Turing tests, CAPCHAs, Frankenstein stories, robots in movies, Westworld, Asimov's Laws of Robotics, robotics on land / air / sea / space, DARPA's Urban Challenge, self-driving cars, biped robots, exoskeletons, robotic surgeons

  27. Lecture 14 (part 1 of 2): the Turing Test, review of autonomous vehicles on road / air / sea / space, automation in factories and homes, pet robots, wearable robots, reality surpassing science fiction, iPhone as supercomputer, chess playing, "IBM Watson" Jeopardy champion, Google "Alpha Go", self-driving cars in films, drones, robo-surgeons, cloaking devices, narrowing gap between science fiction and reality, technological singularity, "virtuous cycles", "gray goo" phenomena, law of accelerating returns, lots of "Moore's Laws", augmented humans, Singularity Summit, course summary: from abbacus to iPhones in 2500 years, 400+ concepts / techniques / ideas / proofs, Dedekind cuts, Occam's razor, flip side to every technology, ethics of engineering / science, 3D printing, what's depicted on currencies of the world

  28. Lecture 14 (part 2 of 2): "ask me anything" session



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