[FRIAM] Fwd: Cris Moore's CS 500 Theory of Computation on ITV in Santa Fe!

Sun, 20 Dec 2009 16:58:16 -0800

It just occurred to me that we didn't forward this to folks not on the SFI mail list!

Also, the Class Attendees mail list mentioned below is not restricted to people taking the class, we can have e-members who read the book chapters join in to the conversation (go to the book site and ask to have access to the preview chapters).  But please, only for folks serious about discussing the book!

Begin forwarded message:

From: Santa Fe Institute <[email protected]>
Date: December 7, 2009 1:59:00 PM MST
Cc: Owen Densmore <[email protected]>
Subject: Cris Moore's CS 500 Theory of Computation on ITV in Santa Fe!

We're delighted to announce SFI's Cris Moore's  Theory of Computation class will be available here in Santa Fe via Instructional TV from the University of New Mexico, Albuquerque.  Please sign up for this class if you have an interest in this topic. We hope to have a very collaborative group up here in Santa Fe.

The class is held on Tues/Thurs, 2:00-3:15 this Spring 2010 semester beginning January 19.  The ITV service is located at the Santa Fe Community College.

The class is based on Cris's forthcoming book The Nature of Computation, a refreshing new approach to the theory of computation.  The syllabus is attached.

If you would like to join an email list for the local attendees of the class, you can join this email list.

Further information may be had by contacting:
  Owen Densmore: [email protected] (505) 988-3787
  Stephen Guerin: [email protected] (505) 995-0206
  
{\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\
}

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

Reply via email to