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

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

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:

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

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:
- 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
- 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"
- 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
- 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
- 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:
- 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
- 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
- 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"
- 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
- 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
- Lecture 11
(part 1 of 2):
- Lecture 11
(part 2 of 2):
- 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
- 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

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