John H. Reif
Spring Semester, 2010
Instructor: John H. Reif
A. Hollis Edens Professor of Computer Science
D223 LSRC Building
E-mail: reif AT cs.duke.edu
Detailed Description of Course Material: see Schedule
Lecture Times: Tuesday & Thursday 1:15 PM – 2:30 PM (See Schedule for details)
Lecture Location: Room North 225
Reif Office Hours: Mon, Wed, Fri 11:00 AM - Noon D223 LSRC Building
Summary Description of Course:
Science and technology is now venturing to build synthetic devices that do communication, locomotion, and computation in previously unexplored areas such as within cells and at the molecular scale. At these scales, the traditional models of computation such as the Turing Machine and Random Access Machine are not appropriate, and alternative models are needed. The course will cover a spectrum of emerging alternative computing models including: quantum computation, cellular and other biological computation modes,and molecular computation. Algorithms, communication techniques, error correction, energy efficiency, scaling laws and computational limits will be covered for each of these computational models.
Introduction & Foundations: 3 lectures
- Conventional Computing Models, Simulation, Reductions, Completeness and Universality
- Cellular Automata
- Reversible Computation & Thermodynamics of Computation
Quantum Computation: 8 lectures
- Introduction to Quantum Mechanics: Hilbert Space, Qubits, Unitary Operations & Projections
- Quantum Circuits and other Quantum Computational Models
- Experimental Quantum Devices
- Quantum Sensing and Quantum Zeno Effect
- Quantum Search
- Quantum Random Walks
- Quantum Factoring
- Adiabatic Quantum Computation
- Quantum Information Theory: Quantum Compression
- Quantum Cryptography &
- Quantum Error Correction
- Quantum Games
Analog & Physical Computational Models: 4 lectures
- Real Number Computational Models
- Computing using Mechanical Devices
- Computing using Newtonian Physics: Bouncing Balls and Movement in Gravitational Fields
- Optical Computing Models
- Dynamical Chaos and Fractal Geometry
Topological and Geometric Computing Models:
Computing via Folding Devices, Knots, and other Topological Objects
DNA Computational Models: 5 lectures
- Overview of DNA structure, hybridization and DNA Nanostructures
- Molecular Computation via DNA hybridization: Adleman’s Experiment
- Molecular Robotics using DNA hybridization
- DNA Computation via Self-Assembly of DNA Tiling Nanostructures
- Assembly Error-Correction
- DNA Computation via Polymerase Reactions: Whiplash PCR
- Molecular Robotics using DNA polymerase
- DNA Computation via Enzymic and DNAzme Reactions
- Spiders: Molecular Robotics using DNAzyme
Ciliate Computation: 1 lecture
- Template-guided Recombination Mechanisms
- Universality Proofs
Reprogrammed Cellular Computation & Robotics: 1 lecture
- Cellular Molecular Switches
- Inter-Cellular Communication: Quorum Sensing
- Natural Molecular Motors and their Reprogramming
Artificial Immune Systems: 1 lecture
Swarming Models: 1 lecture
- Artificial Potential Fields
- Swarm Intelligence and Optimization
- examples: Ant Colony Optimization
Neural Networks: 1 lecture
- Natural Neural Networks
- Models of Neural Networks: Threshold Circuits and other Computational Models
- Training Neural Networks
Evolutionary Algorithms: 1 lecture
- Evolutionary Algorithms
- stochastic models
TA: To be determined
· TA email: To be determined
· TA office hours: To be determined
Required Hardcopy Text Book:
Additional Digital Text Books:
There are no formal prerequisites for the course, except mathematical maturity. However, it would help to have a working knowledge of Complexity Theory and Algorithms at the level of an undergraduate algorithms class.
Topics: see above Schedule
(Tentative) There will be 4 homeworks (5% each, 20% total), a quiz on reductions (10%), a midterm exam (10%), an end-term Final Exam (25%), and a Final Project (30%) for the course. Also attendance and class interaction will provide an additional 5% of the total grade.
Homeworks: To be prepared using LATEX (preferred) or WORD.
· Homework4: Assigned: ?? Due: ??
· Be sure to provide enough details to convince me, but try to keep your answers to at most one or two pages.
· It is OK to answer a problem by stating it is open, but if so, please convincingly explain the reasons you believe this.
· It is permitted to collaborate with your classmates, but please list your collaborators with your homework solution.
· There is no credit given for homework past their due date.
· The final project is a short (at most 12 pages) paper over viewing (definition of the problem and terminology, and the details of some part of the proof) a prior result in alternative computing modelsy.
· The topic is of your choice, and the instructor will provide guidance on relevant literature.
· Novel topics and/or new research may result, but is not necessarily required to still produce an excellent project paper.