Gang: Here's more information on the SFCC/UNM/ITV course. The
attachment has the up-to-date syllabus.
I'd *really* like someone else to take this, we need the start of
higher ed here in Santa Fe to be successful. A lot of us *use*
computers, but many of us do not understand the fundamentals of
computation. I was certainly surprised when I started digging into
automata, decidability, and computational complexity. Cris is a great
lecturer too, he's presented at the SFI summer school and was very
well received.
And there are other ITV courses we would like as well, so this is not
only for Cris's class, there will be others as we start becoming more
involved with UNM via ITV. Hopefully this is the kickoff for several
more to come.
-- Owen
Begin forwarded message:
From: Cris Moore <[email protected]>
Date: December 1, 2009 7:46:10 PM MST
Subject: Re: [sfx: Discuss] Higher Ed in Santa Fe: CS 500 Theory of
Computation
Here is a copy of the syllabus. I usually teach the class to
beginning grad students, but it's accessible to motivated
undergrads, and to scientists from other fields. I would love to
have some students from the SFI community.
Cris
{\rtf1\ansi\ansicpg1252\cocoartf949\cocoasubrtf540
{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
{\colortbl;\red255\green255\blue255;}
\margl1440\margr1440\vieww9600\viewh8400\viewkind0
\pard\tx720\tx1440\tx2160\tx2880\tx3600\tx4320\tx5040\tx5760\tx6480\tx7200\tx7920\tx8640\ql\qnatural\pardirnatural
\f0\fs24 \cf0 CS500, Introduction to the Theory of Computation\
\
Basics:\
Defining inputs, algorithms, and complexity\
Asymptotics and Moore's law\
\
Automata and languages\
DFAs and NFAs\
Closure properties\
Equivalence classes and minimal automata\
The Pigeonhole Principle and the Pumping Lemma\
Context-free grammars\
\
Algorithm review\
Recursion: Towers of Hanoi\
Greedy algorithms: Minimum Spanning Trees\
Divide-and-conquer: Sorting\
Dynamic programming: Genome Alignment \
Max Flow and Min Cut\
Perfect Matching and reductions\
\
NP-completeness\
Boolean circuits and formulas\
3-SAT and NAESAT\
Graph coloring\
Independent Sets, Vertex Covers, and Cliques\
Integer Linear Programming\
What if P=NP? Proofs and creativity\
\
The Grand Unified Theory of Computation\
Universal computation and interpreting programs\
1936: Turing machines, lambda-calculus, and partial recursive functions\
Diagonalization\
The Halting Problem, self-reference, and undecidability\
\
Randomness and Approximation\
The Birthday Problem and hash functions\
Coupon Collecting\
Fingerprinting and the primes\
Karger's Min Cut algorithm\
Walk-SAT\
Relaxation and rounding: the 2-approximation for Vertex Cover\
Christofides' 3/2-approximation for TSP\
\
Memory [optional]\
Log-space and Reachability\
Games, Quantifiers, and PSPACE\
\
More topics [optional]\
Secret Sharing\
RSA cryptography\
Diffie-Helman key exchange\
Quantum computing: Shor's factoring algorithm\
}
Cristopher Moore
Professor, Computer Science / Physics and Astronomy
University of New Mexico
and the Santa Fe Institute
[email protected]
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
