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
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:
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
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
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
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
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
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
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 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 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
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
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
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
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:
Theory of Computation (CS3102), Spring 2017:
A Brief History of Computing, Spring 2018: