Non-Standard 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 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  showclose

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  showclose

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.

√    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 non-determinism. Then, we will get an overview of the mathematical systems of finite-state transducers and grammatical characterizations of the languages that finite-memory programs accept.  The last part of the unit covers the mathematical systems of Turing transducers.  Also, we will discuss the relationship between determinism and non-determinism 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.1-1.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 non-determinism 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.

  • 1.1.1 Alphabets, Strings, and Representations  
  • 1.1.2 Formal Languages and Grammars  
  • 1.1.3 Programs  
  • 1.2 Finite-Memory Programs  
  • 1.2.1 Motivation  
  • 1.2.2 Finite-State Transducers  
  • 1.2.3 Finite-State Automata and Regular Languages  
  • 1.3 Recursive Finite-Domain Programs  
  • 1.3.1 Recursion  
  • 1.3.2 Pushdown Transducers  
  • 1.3.3 Context-Free 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.1-4.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 non-determinism 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.

  • 1.4.1 Turing Transducers  
  • 1.4.2 Programs and Turing Transducers  
  • 1.4.3 Non-Determinism 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.

      Submit Materials

  • 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 DNA-Based Computation  
    • Reading: G. Sweety Peter’s “DNA-Based Computation”

      Link: G. Sweety Peter‘s “DNA-Based 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.

  • 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 bio-electronic, 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 Attribution-Share-Alike License 3.0 (HTML).  You can find the original Wikipedia version of this article here (HTML).

  • 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.

      Submit Materials

  • 2.3 Supramolecular Systems  
  • 2.3.1 Concepts in Supramolecular Chemistry  
  • 2.3.2 Building Blocks of Supramolecular Chemistry  
  • 2.3.3 Applications  
  • 2.4 Bio-molecular Computing of Finite-State 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.

      Submit Materials

    • Web Media: Videolectures.net: Yasubumi Sakakibara’s “Bio-Molecular Computing of Finite-State Automata”

      Link: Videolectures.net: Yasubumi Sakakibara’s "Bio-Molecular Computing of Finite-State 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 Attribution-NonCommercial-NoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.

  • 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  
  • 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.

  • 3.2.1 Introduction  
  • 3.2.2 Classifiers  
  • 3.2.3 Algorithm  
  • 3.3 Evolutionary Algorithms  
    • Web Media: Videolectures.net: Adam Prügel-Bennett’s "Evolutionary Algorithms”

      Link: Videolectures.net: Adam Prügel-Bennett’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 Attribution-NonCommercial-NoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here.

  • 3.4 Another Example: 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  
  • 4.1.2 Construction of Finite Time Sets  
  • 4.1.3 Properties of Finite Time Sets  
  • 4.1.4 Evolution of Finite Time Sets  
  • 4.1.5 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. 

  • 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 Attribution-NonCommercial-NoDerivs 3.0 Unported License. It is attributed to videolectures.net and the original version can be found here

  • 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 Attribution-NonCommercial-NoDerivs 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.

      Submit Materials

  • 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 single-photon 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. 

  • 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. 

  • 5.1.6 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. 

  • 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. 

  • 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. 

  • 5.2 Lectures on Quantum Computation  
  • 5.2.1 The Qubit  
    • Lecture: Hewlett-Packard: David Deutsch’s Lectures on Quantum Computation: "Lecture 1: The Qubit”

      Link: Hewlett-Packard: 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.

  • 5.2.2 Interference  
    • Lecture: Hewlett-Packard: David Deutsch’s "Lecture 2: Interference”

      Link: Hewlett-Packard: 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 single-photon 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.

  • 5.2.3 Measurement  
    • Lecture: Hewlett-Packard: David Deutsch’s "Lecture 3: Measurement”

      Link: Hewlett-Packard: 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.

  • 5.2.4 The Schroedinger Picture  
    • Lecture: Hewlett-Packard: David Deutsch’s "Lecture 4: The Schroedinger Picture”

      Link: Hewlett-Packard: 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.

  • 5.2.5 A Quantum Algorithm  
    • Lecture: Hewlett-Packard: David Deutsch’s "Lecture 5: A Quantum Algorithm”

      Link:Hewlett-Packard: 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.

  • 5.2.6 Grover's Search Algorithm  
    • Lecture: Hewlett-Packard: David Deutsch’s "Grover's Search Algorithm”

      Link: Hewlett-Packard: 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.

      Submit Materials

  • Final Exam