Nonstandard Computation

CS 410, Section 006 / CS 510, Section 010
Fall Quarter 2005

Time : Mondays and Wednesdays, 10:00-11:50am
Location: Neuberger Hall, Room 389

Instructor: Melanie Mitchell, FAB 120-24 (503) 725-2412 (mm@cs.pdx.edu)

Office Hours: 1:30-2:30pm, Mondays and Wednesdays, or by appointment

Course web site:: http://www.cs.pdx.edu/~mm/nonstandard-computation2005

Course description: This course is a seminar that will cover several nonstandard computational methods and theories, including quantum computation, molecular computation, cellular automata, and the 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, and compare these results to those of classical computational methods. 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, probability theory, 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.

Text: None

Assignments: This is a seminar class in which students will read, present, and lead discussion on the assigned papers. Each student will read and present approximately 2-3 papers to the class. All students will read the assigned papers before the discussion of them in class.

There will be selected short homework assignments on each topic to help solidify the students' understanding of what we cover.

Finally, each student will choose a topic related to the assigned readings but not covered in class, and will find and read research papers on that topic and write a 20-30 page "review article" using the papers they have read. A one paragraph proposal for the paper, including bibliography, will be due Wednesday October 26. The first draft of the paper will be due Wednesday, November 30. Each draft will be assigned two reviewers, who will read the paper and submit written comments on it by Tuesday December 7. Students will give in-class presentations of their papers during the last two weeks of the course (including finals week). The final revised written paper will be due by 5:00 pm on the last day of finals week, Friday, December 9.

Exams : None

Grading : Presentations of readings: 20%; homework: 20% final paper writeup: 30%; final paper in-class presentation: 20%: reviews of other students' papers: 10%.

Academic integrity: Students will be responsible for following the PSU Student Conduct Code, and in particular, the policy concerning academic honesty.

Syllabus (subject to change):

Date	Topic	Reading
Monday September 26	Course overview; Physics of computation overview Presenter: Mitchell	...
Wednesday September 28	Physics of computation Presenter: Mitchell	C. H. Bennett, "Logical Reversibility of Computation" Homework 1 assigned, due Wednesday October 5.
Monday October 3	Physics of computation Presenters: Lashelle Cline (Sections 1-3), Caleb Phillips (Sections 4-6)	Fredkin & Toffoli, "Conservative logic", Sections 1-6
Wednesday October 5	Cellular automata overview Presenter: Mitchell (Sections 1,2)	Mitchell, "Computation in celullar automata: A selected review"
Monday October 10	Cellular automata Presenters: MM (Section 8) Ryan Phan (Section 3) Tashell Kelly (Sections 5-6)	Mitchell, "Computation in celullar automata: A selected review", continued.
Wednesday October 12	Miscellaneous topics on cellular automata Computation universality of ECA 110 Coevolution of CAs Applications of cellular automata: Cellular automata in image processing Cellular automata for modeling traffic Quantum dot cellular automata Presenter: Mitchell	Optional reading: A. Popovici and D. Popovici, Cellular automata in image processing K. Nagel and M. Schreckenberg, A cellular automaton model for freeway traffic C. S. Lent, Bypassing the transistor paradigm Homework 2 assigned. Due Wednesday October 19.
Monday October 17	Quantum computation overview Presenter: Mitchell	Rieffel & Polak, An introduction to quantum computing for non-physicists (ACM Computing Surveys 32(3), 300-335, 2000). Sections 1-3.
Wednesday October 19	Quantum computation overview, continued Presenters: Aden Ahmed (Section 4), Dilip Sundarraj (Section 5)	Rieffel & Polak, Sections 4-5.
Monday October 24	Quantum computation Presenters: Mitchell	Optional readings: D. Deutsch & R. Jozsa, Rapid solution of problems by quantum computation S. Gulde et al., Implementation of the Deutsch-Jozsa algorithm on an ion-trap quantum computer
Wednesday October 26	Quantum computation Presenters: Caleb: Section 7.1 Tashell: Section 8 Lashelle: Steffen et al. paper	Classical Fourier transforms Rieffel & Polak, Sections 6, 7.1 (skip 7.2), 8 M. Steffen, L. M. K. Vandersypen, and I. L. Chuang, Toward quantum computation: A five-qubit quantum processor Short proposal (1 paragraph) for final paper due.
Monday October 31	Quantum computation Presenters: MM, LaShelle Molecular computation overview Presenter: MM	Quantum computataion continued from Wednesday October 26. Molecular computation reading: L. A. Adleman, Molecular computation of solutions to combinatorial problems. Optional reading: D. S. Abrams & S. Lloyd, Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems. Homework 3 assigned. Due Wednesday November 9.
Wednesday November 2	Molecular computation Presenters: Dilip Sundarraj: Lipton paper Aden Ahmed: Ouyang paper	R. J. Lipton, Using DNA to solve NP-complete problems Q. Ouyang et al., DNA solution of the maximal clique problem
Monday November 7	Molecular computation, continued Presenters: Caleb Phillips: Sotjanovic & Stefanovic paper Lashelle Cline : Making DNA computers error resistant MM: A biomolecular implementation of logically reversible computation with minimal energy dissipation MM: Evolutionary computation as a paradigm for DNA-based computing	M. N. Sotjanovic & D. Stefanovic, A deoxyribozyme-based molecular automaton D. Boneh, and R. Lipton, Making DNA computers error resistant J. P. Klein, T. H. Leete, and H. Rubin, A biomolecular implementation of logically reversible computation with minimal energy dissipation T. Back, J. N. Kok, and G. Rozenberg, Evolutionary computation as a paradigm for DNA-based computing , (skip section 2.2).
Wednesday November 9	Computation by DNA Self-Assembly Presenter: Mitchell	E. Winfree, On the computational power of DNA annealing and ligation , 1995 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 (2003)
Monday November 14	Molecular Computation and Cryptography Presenters: Lashelle Cline (Sections 1-3 of Boneh et al.) Tashell Kelly (Sections 4-6 of Boneh et al.) Aden Ahmed (Section 7 of Boneh et al.) MM: Immune system overview	D. Boneh, C. Dunworth, and R. Lipton, Breaking DES using a molecular computer Optional reading: A. Gehani, T. LaBean, and J. Reif, DNA-based cryptography
Wednesday November 16	Computer Immunology Presenter: Dilip Sundarraj: Both Forrest et al. papers	S. Forrest et al. Self-nonself discrimination in a computer S. Forrest et al. A sense of self for Unix processes
Monday November 21	Computer Immunology, continued Ant-Colony Inspired Computing Presenters: Dilip Sundarraj: Finish presentations on computer immunology Tashell Kelly (Sections 1-3) Caleb Phillips (Sections 4-5) Aden Ahmed (Sections 6-9)	M. Dorigo, V. Maniezzo, and A. Colorni, The Ant System: Optimization by a colony of cooperating agents (1996) (I had trouble printing the pdf version, but the postscript version worked).
Wednesday November 23	Amorphous computing Presenter: Mitchell	Optional reading: H. Abelson et al., Amorphous computing R. Nagpal, Organizing a global coordinate system from local information on an amorphous computer R. Nagpal, A. Kondacs, and C. Chang, Programming methodology for biologically inspired self-assembling systems T. F. Knight, Jr. and G. J Sussman, Cellular gate technology
Monday November 28	No class	...
Wednesday November 30	Final paper presentations: Caleb Phillips Aden Ahmed	First draft of final papers due. Reviewers assigned.
Tuesday December 6	Final paper presentations: LaShelle Cline Tashell Kelly Dilip Sundarraj	Reviews due back to authors. Final papers due by Friday December 9.