NonStandard Computing
Purpose of Course showclose
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 realitybased 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, selforganizing 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 nondeterminism, finitestate 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 showclose
 Describe abstracted finitememory program, a finite state automaton, and regular language.
 List and explain the characteristics of universal Turing transducers.
 Describe the computational idea behind the DNAbased computer.
 Explain the differences between bioelectronic, 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 showclose
√ Have access to a computer.
√ Have continuous broadband Internet access.
√ Have the ability/permission to install plugins 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.
√ Have completed the Cell Biology (BIO301) course. It is also recommended that you have completed the courses in “The Core Program” of the Computer Science discipline (CS101 through CS405).Unit Outline show close
Expand All Resources Collapse All Resources

Unit 1: Review: Theory of Computation
In the first part of this unit, the student will learn about representing information, the concept of languages, the notion of programs, and the concept of nondeterminism. Then, we will get an overview of the mathematical systems of finitestate transducers and grammatical characterizations of the languages that finitememory programs accept. The last part of the unit covers the mathematical systems of Turing transducers. Also, we will discuss the relationship between determinism and nondeterminism in Turing transducers.
Unit 1 Time Advisory show close
Unit 1 Learning Outcomes show close

1.1 General Concepts
 Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 1: General Concepts”
Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 1: General Concepts” (HTML)
Instructions: Read the introductory webpage titled “General Concepts." Then, click on the hyperlinks for each section 1.11.5, and read each webpage in its entirety. From this reading, you will learn about strings and the role that strings have in representing information. This reading relates the concept of languages to the notion of strings and introduces grammars for characterizing languages. Also, this text deals with the notion of programs and the concept of nondeterminism in programs. This reading covers subunits 1.1.1 through 1.1.3 of this course.
Terms of Use: Please respect the copyright and terms of use displayed here.
 Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 1: General Concepts”
 1.1.1 Alphabets, Strings, and Representations
 1.1.2 Formal Languages and Grammars
 1.1.3 Programs

1.2 FiniteMemory Programs
 Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 2: FiniteMemory Programs”
Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 2: FiniteMemory Programs” (HTML)
Instructions: Please read the “FiniteMemory Programs” webpage, and then click on each hyperlink for sections 2.12.6. Read each section in its entirety to learn about the mathematical systems of finitestate transducers. This reading also provides grammatical characterizations for the languages that finitememory programs accept. This reading covers subunits 1.2.1 through 1.2.3 of this course.
Terms of Use: Please respect the copyright and terms of use displayed here.
 Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 2: FiniteMemory Programs”
 1.2.1 Motivation
 1.2.2 FiniteState Transducers
 1.2.3 FiniteState Automata and Regular Languages

1.3 Recursive FiniteDomain Programs
 Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 3: Recursive FiniteDomain Programs”
Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 3: Recursive FiniteDomain Programs” (HTML)
Instructions: Please read the introductory webpage titled “Recursive FiniteDomain Programs.” Then, click on each hyperlink for sections 3.13.6, and read each section in its entirety to learn about the notion of recursion in programs and recursive finitedomain programs, which are characterized by finitestate transducers. A grammatical characterization for recursive finitedomain programs is provided in section 3.3. This reading covers subunits 1.3.1 through 1.3.3 of this course.
Terms of Use: Please respect the copyright and terms of use displayed here.
 Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 3: Recursive FiniteDomain Programs”
 1.3.1 Recursion
 1.3.2 Pushdown Transducers
 1.3.3 ContextFree Languages

1.4 General Programs
 Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 4: General Programs”
Link: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 4: General Programs” (HTML)
Instructions: Please read the introductory page titled “General Programs.” Then, click on the hyperlinks for sections 4.14.7, and read each webpage in its entirety. Section 4.1 is about the mathematical systems of Turing transducers as a generalization to pushdown transducers. In section 4.2, you will learn about the relationship between the general class of programs and Turing transducers. Section 4.3 considers the relationship between determinism and nondeterminism in Turing transducers. Section 4.4 shows the existence of a Turing transducer, called a universal Turing transducer, which can be programmed to compute any computable function. This reading covers the topics outlined in subunits 1.4.1 through 1.4.4 of this course.
Terms of Use: Please respect the copyright and terms of use displayed here.
 Reading: Ohio State University: Eitan Gurari’s An Introduction to the Theory of Computation: “Chapter 4: General Programs”
 1.4.1 Turing Transducers
 1.4.2 Programs and Turing Transducers
 1.4.3 NonDeterminism versus Determinism

1.4.4 Universal Turing Transducers
 Assessment: The Saylor Foundation's "CS411: Unit 1 Quiz"
Link: The Saylor Foundation's "CS411: Unit 1 Quiz"
Instructions: Please take this Unit 1 quiz. When you are done, check your work against the Saylor Foundation's "CS411: Unit 1 Quiz Answer Key" (PDF). This quiz should require less than one hour to complete.The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
 Assessment: The Saylor Foundation's "CS411: Unit 1 Quiz"

Unit 2: Molecular Computation
The first part of this unit covers the structure and manipulation of DNA for computational purposes. Then, we discuss the development of biocomputers and biologically derived materials to perform computational functions. In order to understand biocomputers better, we list some elementary concepts and building blocks of supramolecular chemistry. The last part of the unit shows a video about the workings of a DNA computer.
Unit 2 Time Advisory show close
Unit 2 Learning Outcomes show close

2.1 DNABased Computation
 Reading: G. Sweety Peter’s “DNABased Computation”
Link: G. Sweety Peter‘s “DNABased Computation” (HTML)
Instructions: Read the webpage to learn about the structure and manipulation of DNA, about the operations of DNA sequences, and about DNA computing models. Make sure you understand the shortcomings of DNA computation. This reading covers subunits 2.1.1 through 2.1.5.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: G. Sweety Peter’s “DNABased Computation”
 2.1.1 The Structure and Manipulation of DNA
 2.1.2 Operations of DNA Sequences
 2.1.3 The Case for DNA Computing
 2.1.4 Models and Formats of DNA Computation
 2.1.5 Pitfalls of DNA Computing

2.2 Biocomputers
 Reading: Wikipedia: “Biocomputers”
Link: Wikipedia: “Biocomputers” (PDF)
Instructions: Read this webpage to learn about the development of biocomputers and biologically derived materials to perform computational functions. Pay particular attention to the differences among bioelectronic, biochemical, and biomechanical computers. This reading covers subunits 2.2.1 through 2.2.7.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).
 Reading: Wikipedia: “Biocomputers”
 2.2.1 Scientific Background
 2.2.2 Biochemical Computers
 2.2.3 Biomechanical Computers
 2.2.4 Bioelectronic Computers
 2.2.5 Engineering Biocomputers
 2.2.6 Economical Benefit of Biocomputers

2.2.7 Notable Advancements in Biocomputer Technology
 Reading: Biocomputers
The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
 Reading: Biocomputers

2.3 Supramolecular Systems
 Reading: Wikipedia: “Supramolecular Chemistry”
Link: Wikipedia: “Supramolecular Chemistry” (PDF)
Instructions: Read this webpage to learn about the concepts and building blocks of supramolecular chemistry. Please pay particular attention to section five “Applications,” which provides examples of how supramolecular chemistry is used. This reading covers subunits 2.3.1 through 2.3.3.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).
 Reading: Wikipedia: “Supramolecular Chemistry”
 2.3.1 Concepts in Supramolecular Chemistry
 2.3.2 Building Blocks of Supramolecular Chemistry
 2.3.3 Applications

2.4 Biomolecular Computing of FiniteState Automata
 Assessment: The Saylor Foundation's "CS411: Unit 2 Quiz"
Link: The Saylor Foundation's "CS411: Unit 2 Quiz"
Instructions: Please take this Unit 2 quiz. When you are done, check your work against the Saylor Foundation's "CS411: Unit 2 Quiz Answer Key" (PDF). This quiz should require less than one hour to complete.The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
 Web Media: Videolectures.net: Yasubumi Sakakibara’s “BioMolecular Computing of FiniteState Automata”
Link: Videolectures.net: Yasubumi Sakakibara’s "BioMolecular Computing of FiniteState Automata" (YouTube)
Instructions: Watch this video to learn what a DNA computer is and to see some examples of how a DNA computer works. Please take notes as you watch the video and review portions of the video as necessary to make sure you understand each concept. This should take approximately 3 hours of study time.
Terms of Use: This video is licensed under a Creative Commons AttributionNonCommercialNoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.
 Assessment: The Saylor Foundation's "CS411: Unit 2 Quiz"

Unit 3: Genetic Algorithms
In this unit, we start with an overview of genetic algorithms. Then, we show a practical example of genetic algorithms that demonstrate the application of event classification and feature selection. Also, we show a video about computational systems that have been used for natural selection on complex artificial problems.
Unit 3 Time Advisory show close
Unit 3 Learning Outcomes show close

3.1 Introduction to Genetic Algorithms
 Reading: www.rennard.org: JeanPhilippe Rennard’s “Introduction to Genetic Algorithms”
Link: www.rennard.org: JeanPhilippe Rennard’s “Introduction to Genetic Algorithms” (HTML)
Instructions: Read this webpage for general overview of genetic algorithms. This reading covers subunits 3.1.1 through 3.1.3.
Terms of Use: The linked material above has been reposted by the kind permission of JeanPhilippe Rennard, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: www.rennard.org: JeanPhilippe Rennard’s “Introduction to Genetic Algorithms”
 3.1.1 Evolution and Optimization
 3.1.2 Evolution and Genetic Algorithms
 3.1.3 Functioning of a Genetic Algorithm
 3.1.4 Adaptation and Selection: the Scaling Problem

3.2 Genetic Algorithm Classifiers
 Reading: McGill University: Gabriel Kevorkian and Marko Milek’s “Genetic Algorithm Classifiers”Link: McGill University: Gabriel Kevorkian and Marko Milek’s “Genetic Algorithm Classifiers” (HTML and Java)
Instructions: Please read this entire study of genetic algorithms (7 pages). Click on the “Next” button at the bottom of the text to move on to each subsequent webpage. Also, go through the example by clicking on the 'Algorithm' and 'Applet' links at the top of the webpage. The example demonstrates specific application of event classification and feature selection. This reading covers subunits 3.1.1 through 3.1.3 of this course.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: McGill University: Gabriel Kevorkian and Marko Milek’s “Genetic Algorithm Classifiers”
 3.2.1 Introduction
 3.2.2 Classifiers
 3.2.3 Algorithm

3.3 Evolutionary Algorithms
 Web Media: Videolectures.net: Adam PrügelBennett’s "Evolutionary Algorithms”
Link: Videolectures.net: Adam PrügelBennett’s "Evolutionary Algorithms" (YouTube)
Instructions: Watch this video on computational systems that have been used for natural selection on complex artificial problems. There have been some successes, but the complexity of artificially evolved systems remains short of the complexity one easily finds in biology. You may benefit from viewing certain sections of this video more than once; repeat watching any sections of the video that are hard to follow. It may also help to take notes as you view this video. This should take approximately 2 hours of study time.
Terms of Use: This video is licensed under a Creative Commons AttributionNonCommercialNoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.
 Web Media: Videolectures.net: Adam PrügelBennett’s "Evolutionary Algorithms”

3.4 Another Example: A Genetic Algorithm for Text Classification Rule Induction
 Web Media: Videolectures.net: Adriana Pietramala, Veronic L. Policicchio, Pasquale Rullo, and Inderbir Sidhu’s "A Genetic Algorithm for Text Classification Rule Induction”
Link: Videolectures.net: Adriana Pietramala, Veronic L. Policicchio, Pasquale Rullo, and Inderbir Sidhu’s "A Genetic Algorithm for Text Classification Rule Induction" (YouTube)
Instructions: Watch the video about genetic algorithm for the induction of rulebased text classifiers. You may benefit from viewing certain sections of this video more than once; repeat watching the sections of the video that are hard to follow. This should take approximately 1 hour of study time.
Terms of Use: This video is licensed under a Creative Commons AttributionNonCommercialNoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.  Assessment: The Saylor Foundation's "CS411: Unit 3 Quiz"
Link: The Saylor Foundation's "CS411: Unit 3 Quiz"
Instructions: Please take this Unit 3 quiz. When you are done, check your work against the Saylor Foundation's "CS411: Unit 3 Quiz Answer Key" (PDF). This quiz should require less than one hour to complete.The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
 Web Media: Videolectures.net: Adriana Pietramala, Veronic L. Policicchio, Pasquale Rullo, and Inderbir Sidhu’s "A Genetic Algorithm for Text Classification Rule Induction”

Unit 4: Computation in Cellular Automata: Selected Review
In the first part of this unit, we provide the description of one dimensional cellular automaton and study some rules by which cellular automaton evolved. Then, we will discuss some properties of the regular language sets generated by a finite number of steps of cellular automaton evolution. Also, we show Stephen Wolfram's classes of cellular automaton behavior. Next, we show the standard cellular neural network model and its potential applications. In the end of the unit, we will study complex systems, such as living organisms, the brain, society, the economy, etc. Complex systems are part of computer science and a computer scientist invents algorithmic processes and formulates suitable abstractions to model complex systems to predict its behavior. Complex systems depend on a huge number of details making them nearly irreducible, so that they cannot be described in terms of a small number of variables.
Unit 4 Time Advisory show close
Unit 4 Learning Outcomes show close
 4.1 Computation Theory of Cellular Automata

4.1.1 Introduction
 Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Introduction”
Link: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Introduction” (HTML)
Instructions: Read the description of one dimensional cellular automaton. Please make sure to carefully review the examples and figures given.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Introduction”

4.1.2 Construction of Finite Time Sets
 Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Construction of Finite Time Sets”
Link: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Construction of Finite Time Sets” (HTML)
Instructions: Read the webpage in its entirety to learn how cellular automaton evolved. Be sure that you understand the examples and figures provided before moving on to other readings.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Construction of Finite Time Sets”

4.1.3 Properties of Finite Time Sets
 Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Properties of Finite Time Sets”
Link: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Properties of Finite Time Sets” (HTML)
Instructions: Read the webpage in its entirety for a discussion about some properties of regular language sets generated by a finite number of steps of cellular automaton evolution. Please pay careful attention to the examples and figures provided.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Properties of Finite Time Sets”

4.1.4 Evolution of Finite Time Sets
 Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Evolution of Finite Time Sets”
Link: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Evolution of Finite Time Sets” (HTML)
Instructions: Read the webpage about several types of cellular automaton behavior. Pay attention to classes of cellular automaton behavior defined by dynamical systems theory.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Evolution of Finite Time Sets”

4.1.5 Some Invariant Sets
 Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Some Invariant Sets”
Link: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Some Invariant Sets” (HTML)
Instructions: Read the webpage in its entirety for information on limiting sets of configurations generated by many steps of cellular automaton evolution.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Stephenwolfram.com: Stephen Wolfram's Computation Theory of Cellular Automata: “Some Invariant Sets”

4.2 Cellular Neural Network
 Reading: Scholarpedia: Tamás Roska and Giovanni E. Pazienza's “Cellular Neural Network”
Link: Scholarpedia: Tamás Roska and Giovanni E. Pazienza's “Cellular Neural Network” (HTML)
Instructions: Read the website to learn about standard CNN model, the potential applications of a Cellular Neural/Nonlinear Network, and biological and technological motivations for computational models. This reading covers subunits 4.2.1 through 4.2.3.
Terms of Use: The linked material above has been reposted by the kind permission of Tamás Roska and Giovanni E. Pazienza, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: Scholarpedia: Tamás Roska and Giovanni E. Pazienza's “Cellular Neural Network”
 4.2.1 Standard CNN Model
 4.2.2 CNN  Universal Machine and Cellular Wave Computing
 4.2.3 Biological and Technological Motivations

4.3 Strong Random Correlations in Complex Systems
 Web Media: Videolectures.net: Imre Kondor’s "Strong Random Correlations in Complex Systems”
Link: Videolectures.net: Imre Kondor’s "Strong Random Correlations in Complex Systems" (YouTube)
Instructions: Watch this video about the complex systems (living organisms, the brain, society, the economy, etc.), which depend on a large number of details making them nearly irreducible, so that they cannot be described in terms of a small number of variables. Repeat watching any sections of the video that are hard to follow. When necessary, pause the video to take the notes. This should take about 3 hours of study time.
Terms of Use: This video is licensed under a Creative Commons AttributionNonCommercialNoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.
 Web Media: Videolectures.net: Imre Kondor’s "Strong Random Correlations in Complex Systems”

4.4 Similarity and Differences by Finite Automata
 Web Media: Videolectures.net: Tamás Gaál’s "Similarity and Differences by Finite Automata”
Link: Videolectures.net: Tamás Gaál’s "Similarity and Differences by Finite Automata" (YouTube)
Instructions: Watch this video about the similarity and differences between finite automata, kernels, morphological analyzers, compilers, and image processors. You may benefit from viewing certain sections of this video more than once; repeat watching the sections of the video that are hard to follow. It may also help to take notes as you watch the video. This should take approximately 3 hours of study time.
Terms of Use: This video is licensed under a Creative Commons AttributionNonCommercialNoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.  Assessment: The Saylor Foundation's "CS411: Unit 4 Quiz"
Link: The Saylor Foundation's "CS411: Unit 4 Quiz"
Instructions: Please take this Unit 4 quiz. When you are done, check your work against the Saylor Foundation's "CS411: Unit 4 Quiz Answer Key" (PDF). This quiz should require less than one hour to complete.The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
 Web Media: Videolectures.net: Tamás Gaál’s "Similarity and Differences by Finite Automata”

Unit 5: The Theory of Quantum Computation: An Introduction
In this unit, we start with the review of basic logic elements. Then, we will study quantum notation and how arbitrary logic gates may be constructed for quantum bits. Next, we show a description of a simple model for a quantum computer based on a classical computer. The second part of this unit consists of video lectures by David Deutsch. These lectures cover an introduction to quantum theory, the quantum theory of computation, physical systems, and the simplest quantum physical system. Also, in the lectures you can see a singlephoton interference experiment and learn how to analyze pairs of interacting quantum systems. Other topics include the Schroedinger picture, density matrices, state vectors, pure states, the Schroedinger equation, and the Deutsch algorithm.
Unit 5 Time Advisory show close
Unit 5 Learning Outcomes show close

5.1 Quantum Computation
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Computation: a Tutorial”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Computation: a Tutorial” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version. You may also access the PDF version of this resource from this website. Read the webpage about a survey made by Keyes in 1988 and reversible computation. Then, review the basic logic elements and FANOUT and ERASE gates. This reading covers subunits 5.1.1 through 5.1.4.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Computation: a Tutorial”
 5.1.1 Computing at the Atomic Scale
 5.1.2 Reversible Computation
 5.1.3 Classical Universal Machines and Logic Gates
 5.1.4 FANOUT and ERASE

5.1.5 Computation without ERASE
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Computation without ERASE”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Computation without ERASE” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version and scroll down to access the above listed section. You may also access the PDF version of this resource from this website. Read the material from the webpage to see why primitive ERASE is not absolutely essential in computation.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Computation without ERASE”

5.1.6 Quantum Notation and Logic Gates for Quantum Bits
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Elementary Quantum Notation” and “Logic Gates for Quantum Bits”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Elementary Quantum Notation” and “Logic Gates for Quantum Bits” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version and scroll down to access the above listed sections. You may also access the PDF version of this resource from this website. Read the material on the webpage to learn about quantum notation and how arbitrary logic gates may be constructed for quantum bits.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here and here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Elementary Quantum Notation” and “Logic Gates for Quantum Bits”

5.1.7 Model Quantum Computer and Quantum Code
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Model Quantum Computer and Quantum Code”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Model Quantum Computer and Quantum Code” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version and scroll down to access the above listed section. You may also access the PDF version of this resource from this website. Read the webpage for a description of a simple model of a quantum computer based on a classical computer instructing a machine to manipulate a set of spins.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Model Quantum Computer and Quantum Code”

5.1.8 Quantum parallelism: Period of a Sequence
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Parallelism: Period of a Sequence”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Parallelism: Period of a Sequence” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version and scroll down to access the above listed section. You may also access the PDF version of this resource from this website. Read the webpage for a description of an algorithm which makes use of the quantum parallelism.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Quantum Parallelism: Period of a Sequence”

5.1.9 Factoring Numbers and Prospects
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Factoring Numbers” and “Prospects”
Link: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Factoring Numbers” and “Prospects” (HTML or PDF)
Instructions: From the site, click on the link for “Quantum computation tutorial” to open the HTML version and scroll down to access the above listed sections. You may also access the PDF version of this resource from this website. Read the two webpages to see an example of factoring a number and to learn about the prospects for quantum computation.
Terms of Use: The linked material above has been reposted by the kind permission of Samuel L. Braunstein, and can be viewed in its original from here and here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: The University of York’s Department of Computer Science: Samuel L. Braunstein's “Factoring Numbers” and “Prospects”
 5.2 Lectures on Quantum Computation

5.2.1 The Qubit
 Lecture: HewlettPackard: David Deutsch’s Lectures on Quantum Computation: "Lecture 1: The Qubit”
Link: HewlettPackard: David Deutsch’s Lectures on Quantum Computation: "Lecture 1: The Qubit" (Windows Media Player)
Instructions: Click on the hyperlink titled “Click to Launch Lecture 1” to download the video. Watch this video lecture about the introduction to quantum theory, the quantum theory of computation, physical systems, observations, and the simplest quantum physical system, the qubit. Repeat watching the sections of the video that are hard to follow. When necessary, pause the video to take the notes. This should take approximately 3 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the web page above.
 Lecture: HewlettPackard: David Deutsch’s Lectures on Quantum Computation: "Lecture 1: The Qubit”

5.2.2 Interference
 Lecture: HewlettPackard: David Deutsch’s "Lecture 2: Interference”
Link: HewlettPackard: David Deutsch’s "Lecture 2: Interference" (Windows Media Player)
Instructions: Select the “click on to launch” hyperlink to download the video. Watch this video to see a singlephoton interference experiment. Repeat watching the sections of the video that are hard to follow. When necessary, pause the video to take the notes. This should about take 2 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Lecture: HewlettPackard: David Deutsch’s "Lecture 2: Interference”

5.2.3 Measurement
 Lecture: HewlettPackard: David Deutsch’s "Lecture 3: Measurement”
Link: HewlettPackard: David Deutsch’s "Lecture 3: Measurement" (Windows Media Player)
Instructions: Select the “click on to launch” hyperlink to download the video. Watch this video to learn how to analyze pairs of interacting quantum systems. You may benefit from viewing certain sections of this video more than once; repeat watching the sections of the video that are hard to follow. It may also be useful to take the notes as you watch the video. This should take approximately 2 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Lecture: HewlettPackard: David Deutsch’s "Lecture 3: Measurement”

5.2.4 The Schroedinger Picture
 Lecture: HewlettPackard: David Deutsch’s "Lecture 4: The Schroedinger Picture”
Link: HewlettPackard: David Deutsch’s "Lecture 4: The Schroedinger Picture" (Windows Media Player)
Instructions: Select the “click on to launch” hyperlink to download the video. Watch this video about the Schroedinger picture, density matrices, state vectors, pure states, and the Schroedinger equation. This video may require multiple viewings. Repeat watching the sections of the video that are hard to follow. Also, pause the video, when necessary, to take the notes. This should take about 2 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Lecture: HewlettPackard: David Deutsch’s "Lecture 4: The Schroedinger Picture”

5.2.5 A Quantum Algorithm
 Lecture: HewlettPackard: David Deutsch’s "Lecture 5: A Quantum Algorithm”
Link:HewlettPackard: David Deutsch’s "Lecture 5: A Quantum Algorithm" (Windows Media Player)
Instructions: Select the “click on to launch” hyperlink to download the video. Watch this video to learn about the Deutsch algorithm. This video may require multiple viewings. You may benefit from reviewing sections of this video multiple times; repeat watching any sections of the video that are hard to follow. When necessary, pause the video to take the notes. This should take approximately 2 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Lecture: HewlettPackard: David Deutsch’s "Lecture 5: A Quantum Algorithm”

5.2.6 Grover's Search Algorithm
 Lecture: HewlettPackard: David Deutsch’s "Grover's Search Algorithm”
Link: HewlettPackard: David Deutsch’s "Lecture 6: Grover's Search Algorithm" (Windows Media Player)
Instructions: Select the “click on to launch” hyperlink to download the video. Watch this video to learn how to use quantum computation to search through N possibilities in a time proportional to the square root of N. You may benefit from viewing this video more than once. Repeat watching the sections of the video that are hard to follow. When necessary, pause the video to take the notes. This should take about 2 hours of study time.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.  Assessment: The Saylor Foundation's "CS411: Unit 5 Quiz"
Link: The Saylor Foundation's "CS411: Unit 5 Quiz"
Instructions: Please take this Unit 5 quiz. When you are done, check your work against the Saylor Foundation's "CS411: Unit 5 Quiz Answer Key" (PDF). This quiz should require less than one hour to complete.The Saylor Foundation does not yet have materials for this portion of the course. If you are interested in contributing your content to fill this gap or aware of a resource that could be used here, please submit it here.
 Lecture: HewlettPackard: David Deutsch’s "Grover's Search Algorithm”

Final Exam
 Final Exam: The Saylor Foundation's CS411 Final Exam
Link: The Saylor Foundation's CS411 Final Exam
Instructions: You must be logged into your Saylor Foundation School account in order to access this exam. If you do not yet have an account, you will be able to create one, free of charge, after clicking the link.
 Final Exam: The Saylor Foundation's CS411 Final Exam