CS 410/510
Nonstandard Computation
Spring Term 2008
Time : Tuesdays and Thursdays, 12:001:50pm
Location: Ondine Room 220.
Instructor:
Melanie Mitchell,
FAB 12024, (503) 7252412, mmATcs.pdx.edu.
Office hours: Tuesdays and Thursdays, 2:003:00pm, or by appointment.
Class Web Page:
http://web.cecs.pdx.edu/~mm/nonstandardcomputation2008/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: Undergraduatelevel 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 
... 
Reading for next class:

Thursday April 3 

... 
Problems:
Problem set 1 (Physics of Information). Due Thursday April
10.

Tuesday April 8 
Cellular automata 
... 
Reading for next class:

Thursday April 10 
Cellular automata 
Chuankai Lin: E. Fredkin and T. Toffoli, Conservative logic 
Reading for next class:

Tuesday April 15 
Cellular automata 
John Balwit: M. Mitchell, Coevolutionary learning with spatially distributed populations 
Problems:
Problem set 2 (Cellular Automata). Due Tuesday April 29.

Thursday April 17 
Amorphous computing 
Jeff Weston:, A. Bhattacharyya, Morphogenesis as an amorphous computation 
Reading for next class:

Tuesday April 22 
Quantum computation: Overview 
... 
Reading for next class:

Thursday April 24 
Quantum Computation: 
Sky Cunningham: Rieffel and Polak, Section 4 
Reading for next class:

Tuesday April 29 
Quantum computation: 
Zig Rosinski: Rieffel and Polak, Section 6. 
Problems:
Problem set 3 (Quantum Computation). Due Tuesday May 13.

Thursday May 1 
Class cancelled. 
... 
Reading for next class:

Tuesday May 6 
Quantum computation: 
Tim Pepper: Rieffel and Polak, Section 7 
Reading for next class:

Thursday May 8 
Molecular computation: Overview 
... 
Reading for next class:

Tuesday May 13 
Molecular computation: 
Nish Aravamudan: LaBean, Winfree, and Reif paper. 
Reading for next class:

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 
Thursday May 22 
Immune system and swarm inspired computing 
Ian Billington: Burgess paper Ian's slides. 
Dorigo, M. et al.,
Ant colony optimization: Artificial ants as a computational intelligence technique 
Tuesday May 27 
Ant colonies and swarm inspired computing 
Garrett Morris: Rizzoli et al. paper 
M. Amos, Bacterial Computing 
Thursday May 29 
Cellular computing and quorum sensing, continued 
... 
T. BernersLee et al., A framework for
Web science, Sections 1 and 4. 
Tuesday June 3 
Web Science 
Leif Warner: Dill et al. paper. 
... 
Thursday June 5 
Final paper presentations: 
... 
... 
Tuesday June 10 
Final paper presentations: 
... 
... 