### From SOSwiki

Current revision (15:36, 4 June 2013) (view source) (→Projects) |
|||

(14 intermediate revisions not shown.) | |||

Line 12: | Line 12: | ||

* [http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/053494728X Sipser], 1st Edition (1996), Chapters 0-4. | * [http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/053494728X Sipser], 1st Edition (1996), Chapters 0-4. | ||

* [http://www.amazon.com/Computation-Finite-Infinite-Machines-Automatic/dp/0131655639/ref=sr_1_1?s=books&ie=UTF8&qid=1364831956&sr=1-1&keywords=minsky+computation Minsky], 1967, selected chapters. | * [http://www.amazon.com/Computation-Finite-Infinite-Machines-Automatic/dp/0131655639/ref=sr_1_1?s=books&ie=UTF8&qid=1364831956&sr=1-1&keywords=minsky+computation Minsky], 1967, selected chapters. | ||

- | * | + | ** Chapter 3 on Neural Networks |

+ | ** Chapter 11 which describes register machines | ||

+ | * [http://dna.caltech.edu/Papers/sCRN_computation_TR2007.pdf Computation with Finite Stochastic Chemical Reaction Networks], the Register Machines and Chemical Reactions paper by D. Soloveichik et al. | ||

+ | * [http://en.wikipedia.org/wiki/Busy_beaver The Busy Beaver Problem] | ||

+ | * [http://www.dna.caltech.edu/Papers/dimacs.pdf A DNA and Restriction enzyme implementation of Turing Machines], by P. Rothemund. | ||

+ | * Charles Bennett: | ||

+ | ** [http://www.cc.gatech.edu/computing/nano/documents/Bennett%20-%20The%20Thermodynamics%20Of%20Computation.pdf The Thermodynamics of Computation]. | ||

+ | ** [http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/Bennett_Reversibiity.pdf Logical Reversibility of Computation]. | ||

+ | ** [http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/Bennett_Tradeoffs.pdf Time/Space Trade-offs for Reversible Computation]. | ||

+ | * Algorithmic Self-Assembly | ||

+ | ** [http://www.dna.caltech.edu/Papers/ligation.pdf Theory Paper], Winfree, 1995. | ||

+ | ** [http://www.dna.caltech.edu/Papers/lattice.pdf First Experiments], Winfree, Liu, Wenzler, Seeman, 1998. | ||

+ | ** [http://www.dna.caltech.edu/Papers/squares_STOC.pdf Binary Counter Theory], Rothemund and Winfree, 2000. | ||

+ | ** [http://www.dna.caltech.edu/Papers/SAcircuits_DNA9.pdf Other things you can make], Cook, Rothemund, Winfree, 2004. | ||

+ | ** [http://www.dna.caltech.edu/Papers/SierpinskiDNA_PLoS2004.pdf Self assembled DNA Sierpinski Triangles], Rothemund, Papadakis, Winfree, 2004. | ||

+ | ** [http://www.dna.caltech.edu/Papers/binary_counters_NanoLetters2005.pdf Copying and Counting], Barish, Rothemend, Winfree, 2005. | ||

+ | ** [http://www.dna.caltech.edu/Papers/snaked_DNA_2007.pdf Error correction], Chen, Schulman, Goel, Winfree, 2007. | ||

+ | ** [http://www.dna.caltech.edu/Papers/snaked_DNA_2007.pdf Seeds], Barish, Schulman, Rothemund, Winfree, 2009. | ||

== Assignments == | == Assignments == | ||

- | Note: All assignments will be submitted through the [https://drive.google.com/?tab=oo&authuser=0#folders/0B-zQzHys9hv0Ui1pRzAzY3Jybk0 EE590 Google Drive] | + | Note: All assignments are listed and will be submitted through the [https://drive.google.com/?tab=oo&authuser=0#folders/0B-zQzHys9hv0Ui1pRzAzY3Jybk0 EE590 Google Drive]. |

- | + | ||

- | + | ||

== Projects == | == Projects == | ||

- | Each student will complete an analysis/design project in which they describe how to implement computation in a novel setting, and/or describe how to implement an interesting or useful class of algorithms on an unconventional computer. | + | Each student will complete an analysis/design project in which they describe how to implement computation in a novel setting, and/or describe how to implement an interesting or useful class of algorithms on an unconventional computer. Project presentations are due during finals week, although project updates will be required through the course. Students are encouraged to discuss project ideas and issues at great length with the instructor. |

+ | |||

+ | Grading: Projects will be evaluated based on (a) your presentation, (b) the slides you prepare for the presentation, (c) paragraph length comments on each slide in your presentation, so that they can be understood in your absence. Note: Not separate write-up is required. Powerpoint or Google Presentation is preferred. In your presentation and slides you must | ||

+ | * Clearly state the problem you are considering. | ||

+ | * Describe the computation device or machine you are considering as formally as possible. | ||

+ | * Relate your system to ideas we discussed in class or read about in textbooks and the literature. | ||

+ | * Give a history of your device: What is known about it? When? What has been done formally? Experimentally? | ||

+ | * Explain what you figured out about your system in the above context. | ||

+ | Typically I rank order projects to determine grades. | ||

+ | |||

+ | == Grading == | ||

+ | |||

+ | The homework will account for 75% of the grade. The project will account for 25% of the grade and will be graded based on (a) the quality of the work done on the project; (b) the quality of the writeup; (c) the quality of the presentation. Note that the professor has extreme distaste for projects that appear to be done in haste. Choose your project by the end of the first week in May and make sure to attend to it daily, figuring out ideas, writing simulations, building things, proving, theorems, implementing algorithms, etc. Grades will be assigned by taking the lowest raw score and assigning it to be somewhat less than 3.5, while the maximim grade is likely to be assigned to 4.0. | ||

== Links == | == Links == | ||

- | * | + | * [http://co2.ini.uzh.ch/Courses/Models/info.php Matt Cook]'s course. |

+ | * [http://www.dna.caltech.edu/courses/cs191/index.html Erik Winfree]'s course. |

## Current revision

# EE590 : Unconventional Computing

- Instructor : Prof. Eric Klavins
- Time: Tu, Th, 9:00 - 10:20a
- Location: MGH 234
- Office hours by appointment

## Reading

- Sipser, 1st Edition (1996), Chapters 0-4.
- Minsky, 1967, selected chapters.
- Chapter 3 on Neural Networks
- Chapter 11 which describes register machines

- Computation with Finite Stochastic Chemical Reaction Networks, the Register Machines and Chemical Reactions paper by D. Soloveichik et al.
- The Busy Beaver Problem
- A DNA and Restriction enzyme implementation of Turing Machines, by P. Rothemund.
- Charles Bennett:
- Algorithmic Self-Assembly
- Theory Paper, Winfree, 1995.
- First Experiments, Winfree, Liu, Wenzler, Seeman, 1998.
- Binary Counter Theory, Rothemund and Winfree, 2000.
- Other things you can make, Cook, Rothemund, Winfree, 2004.
- Self assembled DNA Sierpinski Triangles, Rothemund, Papadakis, Winfree, 2004.
- Copying and Counting, Barish, Rothemend, Winfree, 2005.
- Error correction, Chen, Schulman, Goel, Winfree, 2007.
- Seeds, Barish, Schulman, Rothemund, Winfree, 2009.

## Assignments

Note: All assignments are listed and will be submitted through the EE590 Google Drive.

## Projects

Each student will complete an analysis/design project in which they describe how to implement computation in a novel setting, and/or describe how to implement an interesting or useful class of algorithms on an unconventional computer. Project presentations are due during finals week, although project updates will be required through the course. Students are encouraged to discuss project ideas and issues at great length with the instructor.

Grading: Projects will be evaluated based on (a) your presentation, (b) the slides you prepare for the presentation, (c) paragraph length comments on each slide in your presentation, so that they can be understood in your absence. Note: Not separate write-up is required. Powerpoint or Google Presentation is preferred. In your presentation and slides you must

- Clearly state the problem you are considering.
- Describe the computation device or machine you are considering as formally as possible.
- Relate your system to ideas we discussed in class or read about in textbooks and the literature.
- Give a history of your device: What is known about it? When? What has been done formally? Experimentally?
- Explain what you figured out about your system in the above context.

Typically I rank order projects to determine grades.

## Grading

The homework will account for 75% of the grade. The project will account for 25% of the grade and will be graded based on (a) the quality of the work done on the project; (b) the quality of the writeup; (c) the quality of the presentation. Note that the professor has extreme distaste for projects that appear to be done in haste. Choose your project by the end of the first week in May and make sure to attend to it daily, figuring out ideas, writing simulations, building things, proving, theorems, implementing algorithms, etc. Grades will be assigned by taking the lowest raw score and assigning it to be somewhat less than 3.5, while the maximim grade is likely to be assigned to 4.0.

## Links

- Matt Cook's course.
- Erik Winfree's course.