Nonstandard Computation

Time : Tuesdays and Thursdays, 12:00-1:50pm
Location: Ondine Room 220.

Instructor: Melanie Mitchell, FAB 120-24, (503) 725-2412, mm-AT-cs.pdx.edu.
Office hours: Tuesdays and Thursdays, 2:00-3:00pm, or by appointment.

Class Web Page: http://web.cecs.pdx.edu/~mm/nonstandard-computation2008/index.html

Course Description: This is a seminar course that will cover several prominent "unconventional" computational methods and theories. Topics will include quantum computation, DNA and molecular computation, cellular automata and amorphous computing, immune and swarm computing, and physics of computation.

After covering the basic concepts underlying each approach, we will read and discuss recent papers detailing specific theory and applications in each of these areas. Students can expect to come away from this course with an understanding of the basic issues, prominent results, and open research questions in each of these areas. They will also come away with an understanding of the promise and possible future applications of technologies based on the novel ideas encountered here.

Prerequisites: Undergraduate-level courses on linear algebra and the theory of computation (automata, formal languages, computability, and computational complexity). No prior knowledge of quantum mechanics or other areas of physics is necessary.

Homework: The assignments for this class will consist of reading articles and doing homework problems, which will include written work and computer simulations. Graduate students will each present one article in class (this is optional for undergraduates). Each student will also do a term project, including a class presentation and written report (more details in class). There will be no exams.

Grading: Homework: 50%; Class presentation(s): 20%; Term project written report: 30%.

Syllabus (subject to change):

Date	Main Topics	Student Presentations	Homework
Tuesday March 31	Class overview What are "information" and "computation"? Physics of computation Here are the slides.	...	Reading for next class: M. Mitchell, What is Information? and What is Computation? C. Bennett, Logical reversibility of computation (Optional) M. P. Frank, Introduction to reversible computing: Motivation, progress, and challenges (Optional) E. Fredkin and T. Toffoli, Conservative logic
Thursday April 3	Physics of computation Cellular automata introduction Here are the slides.	...	Problems: Problem set 1 (Physics of Information). Due Thursday April 10. Reading for next class: M. Mitchell, Cellular automata, life, and the universe (Optional) S. Wolfram, A New Kind of Science , Chapters 2-3
Tuesday April 8	Cellular automata Here are the slides.	...	Reading for next class: M. Mitchell, Computation in celullar automata: A selected review, parts 1-4
Thursday April 10	Cellular automata Here are the slides.	Chuan-kai Lin: E. Fredkin and T. Toffoli, Conservative logic Chuan-kai's slides.	Reading for next class: M. Mitchell, Computation in celullar automata: A selected review, parts 5-9 (Optional) M. Mitchell, Coevolutionary learning with spatially distributed populations
Tuesday April 15	Cellular automata Here are the slides.	John Balwit: M. Mitchell, Coevolutionary learning with spatially distributed populations John's slides.	Problems: Problem set 2 (Cellular Automata). Due Tuesday April 29. Reading for next class: R. Nagpal, A. Kodacs, and C. Chang, Programming methodology for biologically-inspired self-assembling systems (Optional) H. Abelson et al., Amorphous Computing (Optional) J. T. Lizier et al., Detecting non-trivial computation in complex dynamics
Thursday April 17	Amorphous computing Here are the slides.	Jeff Weston:, A. Bhattacharyya, Morphogenesis as an amorphous computation Jeff's slides. Kenny Graunke: Jonathan Bachrach, Radhika Nagpal, Micheal Salib, and Howard Shrobe, Experimental Results and Theoretical Analysis of a Self-Organizing Global Coordinate System for Ad Hoc Sensor Networks Kenny's slides.	Reading for next class: E. Rieffel and W. Polak, An introduction to quantum computing for non-physicists (ACM Computing Surveys 32(3), 300-335, 2000). Sections 1-3.
Tuesday April 22	Quantum computation: Overview Here are the slides.	...	Reading for next class: Rieffel and Polak, Sections 4-5.
Thursday April 24	Quantum Computation: Quantum gates Quantum parallism Here are the quantum parallism slides.	Sky Cunningham: Rieffel and Polak, Section 4 Sky's slides.	Reading for next class: Rieffel and Polak, Section 6.
Tuesday April 29	Quantum computation: Quantum coin flipping Here are the quantum coin flipping slides. Shor's algorithm for factoring	Zig Rosinski: Rieffel and Polak, Section 6. Zig's slides.	Problems: Problem set 3 (Quantum Computation). Due Tuesday May 13. For a write-up of the quantum bit flipping protocol, see Section 3.1 of G. Brassard and C. Crepeau, Quantum bit commitment and coin tossing protocols Reading for next class: Rieffel and Polak, Section 7.
Thursday May 1	Class cancelled.	...	Reading for next class: Rieffel and Polak, Section 8.
Tuesday May 6	Quantum computation: Search algorithms Quantum error correction	Tim Pepper: Rieffel and Polak, Section 7 Tim's slides.	Reading for next class: L. A. Adleman, Molecular computation of solutions to combinatorial problems. Optional reading: R. J. Lipton, Using DNA to solve NP-complete problems
Thursday May 8	Molecular computation: Overview Here are the slides.	...	Reading for next class: T. H. LaBean, E. Winfree, and J. H. Reif, Experimental progress in computation by self-assembly of DNA tilings Optional reading E. Winfree, DNA computing by self-assembly
Tuesday May 13	Molecular computation: Self Assembly Here are the slides.	Nish Aravamudan: LaBean, Winfree, and Reif paper. Nish's slides.	Reading for next class: L. M. Smith, The manifold faces of DNA P. W. K. Rothemund, Folding DNA to create nanoscale shapes and patterns Optional reading: M. Cook, P. W. K. Rothemund, and E. Winfree, Self-assembled circuit patterns
Thursday May 15	Molecular computation: DNA oragami and circuits	...	...
Tuesday May 20	Guest lecture: Prof. Marek Perkowski (ECE Department) will speak about his work on quantum computing.	...	Forrest et al., Computation in the wild Optional reading: Burgess, M., Computer Immunology
Thursday May 22	Immune system and swarm inspired computing Here are the slides.	Ian Billington: Burgess paper Ian's slides.	Dorigo, M. et al., Ant colony optimization: Artificial ants as a computational intelligence technique Optional reading: Rizzoli, A. E., et al. Ant colony optimization for real-world vehicle routing problems
Tuesday May 27	Ant colonies and swarm inspired computing Overview of cellular computing Here are the slides.	Garrett Morris: Rizzoli et al. paper Garrett's slides.	M. Amos, Bacterial Computing Optional reading: M. Levy et al., Taking pictures with E. coli: Signal processing using synthetic biology. J. J. Tabor, Programming living cells to function as massively parallel computers.
Thursday May 29	Cellular computing and quorum sensing, continued The science of networks Here are the slides.	...	T. Berners-Lee et al., A framework for Web science, Sections 1 and 4. Optional reading: S. Dill et al., Self-similarity in the Web
Tuesday June 3	Web Science Here are the slides.	Leif Warner: Dill et al. paper.	...
Thursday June 5	Final paper presentations: Sky Cunningham Will Newell Kenny Graunke Chuan-kai Lin Zig Rosinski	...	...
Tuesday June 10	Final paper presentations: Ian Billington Garrett Morris Tim Pepper Jeff Weston Gregor Richards	...	...