CS411: Non-Standard Computing

Course Syllabus for "CS411: Non-Standard Computing"

This is a course that will cover several unconventional computational methods and theories, such as quantum computation, DNA and molecular computation, genetic algorithms, and cellular automata.  Note: Before taking this course, it is strongly recommended that you complete Cell Biology (BIO301).  This course is inspired by reality-based computing from the natural world.  It explores new computational paradigms that break the classical computational assumptions.  The real world provides the inspiration for novel computations through the genetic algorithms, complex adaptive systems, self-organizing networks, and quantum computing. In the first unit, we will review the basics of computational theory.  We will discuss information representation, languages, programs, concept of non-determinism, finite-state transducers, and Turing transducers.  The second unit covers the structure and manipulation of DNA for computational purposes as well as the development of biocomputers and biologically derived materials for computational purposes.  The third unit is about genetic algorithms.  In the fourth unit, there is a description of a cellular automaton, and we will discuss some properties of the regular language sets generated by a finite number of steps of cellular automaton evolution.  We will use resources by Stephen Wolfram to explore cellular automaton behavior.  Also, we will learn about a standard cellular neural network model and its potential applications.  Then, we will view a video about the complex systems or system composed of interconnected parts that as a whole exhibit one or more properties not obvious from the properties of the individual parts.  The last unit consists of topics related to quantum computation.  It shows quantum notation, how arbitrary logic gates may be constructed for quantum bits, as well as a description of a simple model for a quantum computer.  At the end of the course, you will find video lectures by David Deutsch.  These lectures are about the quantum theory of computation and show examples of how quantum computation should work.

Learning Outcomes

Upon successful completion of this course, the student will be able to:

  • Describe abstracted finite-memory program, a finite state automaton, and regular language.
  • List and explain the characteristics of universal Turing transducers.
  • Describe the computational idea behind the DNA-based computer.
  • Explain the differences between bio-electronic, biochemical, and biomechanical computers.
  • Describe the functional principles of genetic algorithms and list their limitations.
  • Define the cellular automaton and the cellular neural network, and show examples of how they compute.
  • Describe how logic gates may be constructed for quantum bits.
  • Describe a simple model for a quantum computer based on a classical computer.
  • Describe an algorithm which makes use of quantum parallelism.

Course Requirements

In order to take this course, you must:

√    Have access to a computer.

√    Have continuous broadband Internet access.

√    Have the ability/permission to install plug-ins or software (e.g. Adobe Reader or Flash).

√    Have the ability to download and save files and documents to a computer.

√    Have the ability to open Microsoft files and documents (.doc, .ppt, .xls, etc.).

√    Be competent in the English language.

√    Have read the Saylor Student Handbook.