CS/EE/MA 129a
Information and Complexity (Part I only)
Prof. Erik Winfree Fall 2011. http://www.dna.caltech.edu/courses/cs129 |
Handouts
Office Hours Policy Syllabus Homework |

Time (CS 129a): Tuesday and Thursday 1:00pm - 2:25pm

Location: Annenberg 213

Location: Annenberg 213

Important historical papers: [ip restricted access]

**Information Theory:**"A Mathematical Theory of Communication" by Claude E. Shannon**Computation:**"On Computable Numbers, with an Application to the Entscheidungsproblem" by Alan Turing. Corrections.**Kolmogorov Complexity:**"A Theory of Program Size Formally Identical to Information Theory" by Gregory Chaitin

Professor | TAs (CS 129a only) |

Erik WinfreeHours: by arrangement Office: 204 Moore Extension: x6246 |
Brian Merlob and Suiyi (Doris) XinRuddock dining hall : Wednesdays 8-11pm (Brian) CS Lab, 1st floor Annenberg : Saturday 8-9pm (Brian) CS Lab, 1st floor Annenberg : Sunday 8-9pm (Doris) |

Email: <winfree@caltech.edu> | Email: <cs129_ta@dna.caltech.edu> |

**Format**: The class will be based on reading and discussion.
Each week, several of pages of lecture notes will be assigned. Read
them carefully and test your understanding by working out alternative
proofs or invent and solve simple problems investigating the material.
Monday's homework: Read the lecture notes, solve the assigned problem, provide a discussion point / clarification, and invent and solve your own problem.
Typical Tuesday's class: Summary of section, explanation of discussion points by students, quiz problem & discussion.
Typical Thursday's class: Continued discussion of discussion points, presentation of invented problems, quiz & discussion.

**Grading**: Homework (60%), class discussion (30%), in-class
problems (10%). There will be no midterm or final. Attendance is mandatory. Homework
questions will be open-ended; creative engagement with the subject
matter is encouraged and expected.
Clear presentation and rigorous proofs are important aspects of the homework exercises, and will be graded accordingly.
Programming will be part of some homework.

**Late Policy**: Homework (a single PDF file) must be handed in by email
(cs129_ta@dna.caltech.edu) before 11:59pm each Monday.
Please use a subject line that contains your name, the class name "CS129", and the homework number (e.g. "HW1");
also please give your PDF a filename containing all the same information.
You have 5 (total) "late days" which you may
allocate as you wish to avoid the lateness penalty.
For example, a homework turned in on Wednesday that was due Monday is 2
day late. When late homework is turned in, the time, date, and number
of "late days" used, must be clearly stated in the email. Beyond
institute-established cases of
illness or emergency, no other exceptions will be granted.
Use late days wisely, or not at all.

**Collaboration and Open-Book Policy**: Collaboration in the sense of
discussions is allowed, but you should write the final solutions alone
and understand them fully. Clear reasoning and presentation is as
important as correctness. Do not read class notes or homework
solutions from previous years at any time. Other books and notes can
be consulted, but not copied from; however, they shouldn't be
necessary for the homework problems. All programming must be entirely
your own.

Lecture notes will be handed out in class. A preliminary schedule, subject to change, is given below. Each line corresponds roughly to one or two class meetings.

- Course overview.
- Deterministic and probabilistic information.
- Entropy.
- Joint, marginal, and conditional ensembles & entropies.
- Equalities and inequalities for entropy.
- Mutual information.
- Law of large numbers, typical sets.
- Entropy vs probabilistic information: intuition
- Entropy vs probabilistic information: formal proof.
- Representation: coding and decoding.
- Uniquely decodable, instantaneous codes; Kraft's inequality.
- Optimal codeword length, Huffman codes.
- Formalizing computation: representation.
- Finite state automata and limitations.
- Turing machines, stack machines; computability
- Church-Turing thesis: composition and simulations.
- A universal machine.
- Undecidability: the halting problem (decidable vs acceptable).
- Undecidability: the tiling problem.
- Uncomputability: the busy beaver problem.
- Data compression and algorithmic complexity.
- Algorithmic entropy.

- Relative entropy, side information, gambling & investment.
- Communication: information channels and channel capacity.
- Capacity and rate theorem: intuition.
- Capacity and rate theorem: formal proof.
- Time complexity of algorithms: generation vs recognition, P vs NP.
- NP problems and NP-completeness.
- Data compression and Kolmogorov complexity; uncomputability thereof.
- Kolmogorov complexity, Levin complexity, and Universal Search.
- Formal logic and provability.
- Undecidability and the limits of math: Goedel's theorem and Chaitin's theorem.
- Solomonoff inference and optimal prediction.
- Hutter's algorithm.
- Algorithmic entropy: Kolmogorov complexity of ensembles.
- Chaitin's inequalities for Algorithmic Information Theory.

- A term-long mini research project of your own invention. Become interested in a question. Pose a clear problem. Investigate it. Reformulate it. Repeat.