(Register for MS&E 319/CS 369X: Research Topics in Optimization)

Spring 2003-04, Stanford University

Instructor: **Ashish Goel** (Office
Hours: Tue 1-2)

**Essential Class
Information**: Syllabus, Grading policy, Timetable etc.

** **

**Announcements:
**HW 1 is now online.
Also, there is no class on Thu, Apr 22^{nd}. Please use this time to do
the background work mentioned in HW1.

** **

** **

**Description:
**Self-assembly
is the ubiquitous process by which objects autonomously assemble into
complexes. Nature provides many examples: Atoms react to form molecules. Molecules
react to form crystals and supramolecules. Cells coalesce to form organisms.
Precisely controlled molecular self-assembly has the potential to be a whole
new engineering paradigm, much like the engine and the semiconductor. It will
enable nano-machines, computation at the molecular level, fractal antennas, and
molecular circuits, among other things.

DNA
is a natural candidate for molecular self-assembly. It has the right size, its
functionality is determined largely by its combinatorics rather than geometry,
and nature offers a "proof of concept" for DNA self-assembly.

In this class, we will develop models and algorithms to facilitate efficient and robust self-assembly at the nano scale. We will study self-assembly from combinatorial, optimization, and stochastic viewpoints. We will point out the broad topics where further mathematical research is urgently needed. We will also describe some of the recent experimental advances in DNA self-assembly, and the applications which motivate these experiments.

** **

** **

**Grading:
**There will
be four homework assignments, one of which will be an open-ended research
project and another will be a take-home midterm. It is expected that most of
the students will register for this class using the P/NC option. For these
students, there will be no final exam – your grade will be determined by class
participation and your performance on the homework assignments. If you are
signed up for a letter grade, please let me know in advance – you will be given
an extra take home exam.

** **

**Collaboration
Policy: **No
collaboration is allowed on any of the homework assignments unless explicitly
permitted.

**Prerequisites: **Students must have taken one class (or have an
equivalent background) from each of the following categories:

- CS 161 or MS&E 212
- MS&E 121 or STATS
217
- Basic calculus

** **

** **

Motivating
examples

What
is molecular self-assembly?

An
abstract combinatorial model for DNA self-assembly

Universal
computation using self-assembly

Assembly
time and design complexity of self-assembled systems

Constructing
counters using self-assembly – the difference between natural and engineered
self-assembly

Efficient construction of fixed sized squares using
self-assembly – upper and lower bounds

Techniques for analyzing assembly time

Optimization problems in self-assembly

Some interesting self-assembled patterns

Fractals

Spirals

Memory
chips?

Reversible self-assembly: a thermodynamic model

Entropy

Equilibria

Convergence rates

Why errors happen

Approaches to make self-assembling systems robust:
coding theory for natural systems

Step-wise self-assembly: trading design complexity
for experiment complexity

State of the art – a review of recent experimental
progress

Self-assembly at larger scales:

Ant
colony optimization

Algorithms
for assembling tiny robots

** **

** **

** **

** **

** **

Self-Assembled
Circuit Patterns** **** **by Matthew Cook, Paul W.K.
Rothemund, and Erik Winfree** **

** **

The Program-Size
Complexity of Self-Assembled Squares by Paul W. K. Rothemund and Erik Winfree

Running time and
program size for self-assembled squares by Adleman, Cheng, Goel,
and Huang

Optimal
self-assembly of counters at temperature two by Q. Cheng, A. Goel, and P. Moisset

Combinatorial optimization
problems in self-assembly. By Adleman, Cheng, Goel, Huang, Kempe.
Moisset, and Rothemund. Read the first three sections.

Proof-reading for error-correction: Initial paper, Snaked proofreading.

** **

** **

** **

** **

** 3/31/04.** Note
to auditors: Please subscribe to the email list** **msande319-spr0304-guests
using https://lists.stanford.edu

** 4/20/04. **HW 1 is now online.
Due 4/30.

** 4/20/04. **There will be no class on Thu, 4/22.** **Please use this time to do
the background work mentioned in HW1.

** **

** **