Classes are Tuesdays from 14h30 to 17h30 in room 330
of Allen Building, the building for Physics.

Lecture notes: 

• Course organization
• Introductory concepts on formal languages
• Finite Automata
• Regular Expression
• Context-Free Grammars
• Turing Machine
• Decidability
• Reducibility
• Introduction to complexity theory
• NP problems
• NP-Completeness
• Space Complexity
• Intractability
• Kolmogorov Complexity
  

• Biological Automata: to be defined
• Quantum Computation:
• John Preskill's quantum computing class at Caltech (see lecture notes)
• Quantum computation: a tutorial, by Samuel L. Braunstein
• DNA Computation:
• Simple Guide to DNA Computers  (and this paper: Molecular Computation of Solutions to Combinatorial Problems)
• Massively Parallel Computation by DNA (at Rochester University, you will find several papers, look at "Biomolecular Computing---Recent Theoretical and Experimental Advances")
• DNA Computers: Advantages and Disadvantages
• The complexity and viability of DNA computations
• Bibliography of Molecular Computation
• Cellular Automata:
• Introduction to cellular automata
• A very brief introduction to CA
• Stephen Wolfram's web page
• Software for cellular automata simulations
• CA-FAQ