Nonstandard Computation

CS 410/510
Nonstandard Computation
Spring Term 2008


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:

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:

Tuesday April 8

Cellular automata

Here are the slides.

...

Reading for next class:

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:

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:

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:

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:

Thursday May 8

Molecular computation: Overview

Here are the slides.

...

Reading for next class:

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:

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

...

...