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

**Lectures:**

** 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:**

**Surveys:**

**Prerequisites:**

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

**Grading:**

(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.*