CPS 296.4: Alternative Computational Models

Department of Computer Science

Duke University

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

         Phone: 919-660-6568

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.


Course Syllabus:


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 & Teleportation
- 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: ??

Homework Rules:

·      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.

Final Project:

·      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.