Fall 2018
Molecular Computation
MW 3:05pm – 4:20pm

ENGR 1.236
Department of Computer Science
University of Texas - Rio Grande Valley

Synopsis:

This course covers theoretical models of molecular computing, DNA computing, and algorithmic self-assembly, with an emphasis on algorithmic design and analysis of self-assembling systems. Mathematical and algorithmic topics are covered along with the experimental motivation behind the models. The course will focus on models of unconventional and natural computation stemming from a selection of recently published research papers. Specific topics will includes DNA self-assembly, algorithmic tile self-assembly, DNA codeword design, and chemical reaction networks.

class syllabus

Instructor:

Robert Schweller
Office: ENGR 3.294
Phone: (office) 956-665-2667  (cell) 773-456-1722
Email: schwellerr@gmail.com
URL: http://faculty.utrgv.edu/robert.schweller/
Office Hours: Tue, Thur 11:00-12:00, Wed 10:00-12, or by appointment

.

Software to install:

· LaTex LaTex is the standard document preparation software used to write scientific papers.

o Sample latex file with figures and bibliography

§ Source

§ Should produce this pdf

· WinEdt A widely used text editor with plugins for LaTex.

· Inkscape A widely used vector graphics program for making figures.

· VersaTILE self-assembly simulator

Weekly Reading Assignments and Projects:

• Week 1: Algorithmic Tile Self-Assembly: Read The Program-Size Complexity of Self-Assembled Squares

- aTAM introduction, rectangle building: Slides

- Homework: rectangleHomework (due 1/29)

• Week 2: quiz: Provide a 10 tile-type aTAM system that uniquely assembles a 6 x 6 square.

- aTAM square building: Slides

- aTAM optimal square building

o Unique glue pairing model: notes

o Flexible glues model: slides

• Week 3: Read Complexity of Self-Assembled Shapes, review: Complexities for Generalized Models of Self-Assembly
1. Building a kxn rectangle efficiently: slides
2. nxn squares with flexible glues: slides
3. Turing machine implementation sketch: slides
4. Homework: TuringSimulation (due 2/12)
• Week 4: Run-time modelling in self-assembly: Read Fast Arithmetic in Algorithmic Self-Assembly
1. slides
2. Multiplication
1. Best known aTAM result: review Arithmetic computation in the tile assembly model: addition and multiplication
2. Standard computational model techniques
3. Homework: fastComputing (due 3/5)
• Week 5: Randomization in algorithmic self-assembly: Read Randomized Self-Assembly for Exact Shapes
1. Homework: probabilityAndRandomization (due 3/7)
2. Lame first approach for “approximate” shapes: slides
3. Improving to “exact” shapes:
4. Additional reading:
1. The power of non-determinism in self-assembly
2. “The Gap”

· Week 6: Read: The Tile Complexity of Linear Assemblies

1. Additional reading: Concentration independent random number generation in tile self-assembly

· Week 7: Open Problems. Homework: openProblems (due 3/21)

1. aTAM Assembly Verification Problems, Read: Combinatorial Optimization Problems in Self-Assembly

2. Pattern Assembly Problems, Read: Binary Pattern Tile Set Synthesis Is NP-Hard

3. Feature Assembly Problems, Read: Just think and discuss to come up with creative ideas

· Week 9: Verification problems, open problems 2ham-UAV

1. 2ham-UAV hardness: 2D, high temperature, 3D constant temperature

· Week 10: Discrete counts: homework (due 4/2)

· Week 11: Final project: finalProject