View source for EE5393

== Circuits, Computation and Biology ==

'''Semester''': Spring, 2015<br>

'''Time''': Wed. and Fri., 2:30pm - 3:45pm. (''Also offered through [https://hermes.unite.umn.edu/index.html UNITE]''.)

=== Syllabus ===

This course explores connections between engineering concepts — circuit theory, digital computation and distributed computing in particular — and biological systems. A broad theme is the application of expertise from the former to the latter — specifically, the application of algorithmic and computational expertise from circuit design to the analysis and synthesis of biochemical and neural systems. 

This course is aimed at a wide audience: graduate students and upper-level undergraduates from engineering, computer science, mathematics, biology and the life sciences. No prior knowledge of engineering or biology is assumed; only basic college-level mathematics is required. While the course investigates a variety of topics from disparate fields, it does not attempt to survey the research exhaustively. Rather, it strives for depth and mathematical rigor in select areas.

Topics that are covered include:

====Biology====

* Analyzing and Simulating Stochastic Chemical Kinetics
* Computing  with Molecular Reactions
** Computing Logical Functions
** Computing Iterative Functions
** Computing Stochastic Functions
** Digital Signal Processing
* DNA Strand Displacement Reactions

====Circuits====
* Nanoscale Switching Lattices
* Circuits with Feedback
* Logical Computation on Random Bit Streams
* Linear Threshold Logic

====Computation====
* Conditional Permutations
* Distributed Coordination
* Graph-based Data Structures for Boolean Functions
* Symbolic Boolean Data Structures
* Neural Computation

== Organization ==

=== People ===

* Instructor: Prof. [[Marc Riedel]] ([mailto:mriedel@umn.edu mriedel@umn.edu])

=== Lecture ===

* Wed. and Friday, 2:30pm - 3:45pm, Keller Hall, 3-230

=== Office Hours ===

* Mon. 1 - 3pm (''or by appointment'')

=== Text & Manuals ===

* No textbook is required. 
* Research papers (in the form of PDFs) will be posted for most of the research topics that are covered.

=== Grading ===

* Homework: '''80%'''
** best 3 of 4 homeworks

* Quizzes: '''20%'''
** 10 of them.

Letter grades will be assigned according to the following (absolute) scale:
{|
|A ≥ 90%,	|| A- ≥ 85%,	
|-
| B+ ≥ 80%, || B ≥ 75%, || B- ≥ 70%,
|-
| C+ ≥ 65%, || C ≥ 60%, || C- ≥ 55%,
|- 
| D ≥ 40% (or having a pulse),
|-
| F < 40%.
|}

Even though the grading is quantitative and objective, we must state the following '''university grading standards'''. According to University policy, grades are assigned with the following meaning:
* A - Achievement that is outstanding relative to the level necessary to meet course requirements.
* B - Achievement that is significantly above the level necessary to meet course requirements.
* C - Achievement that meets the course requirements in every respect.
* D - Achievement that is worthy of credit even though it fails to meet fully the course requirements.
* S - Achievement that is satisfactory (equivalent to a C or better).
* F (or N) - Represents failure (or no credit) and signifies that the work was either completed, but at a level of achievement that is not worthy of credit, or was not completed and there was no agreement between the instructor and the student that the student would be awarded an incomplete.
* I (Incomplete) - Assigned at the discretion of the instructor when, due to extraordinary circumstances, a student is prevented from completing the work of the course on time. Assignment of an ‘‘I’’ grade requires a written agreement between the instructor and the student. ‘‘Extraordinary circumstances’’ are such things as hospitalization, serious car accidents, and major illnesses. They do not include excuses such as ‘‘working too much,’’ ‘‘took too many credits,’’ and so forth. Furthermore, an ‘‘I’’ can be assigned only when a small portion of the course remains to be completed.

== Lectures ==

Per UNITE policy, videos of the lectures can only be posted 10 days after the fact. Slides will be posted immediately.

* Jan. 21, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-01-21.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-01-21.pptx Slides]. Topic: Random sampling of course topics, Part I.
* Jan. 23, 2015:  [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-01-23.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-01-23.pptx Slides]. Topic: Random sampling of course topics, Part II.
* Jan. 28, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-01-28.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-01-28.pptx Slides]. Topic: Logical Computation on Stochastic Bit Streams, Part I.
* Jan. 30, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-01-30.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-01-30.pptx Slides]. Topic: Logical Computation on Stochastic Bit Streams, Part II.
* Feb. 04, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-04.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-04.pptx Slides]. Topic: Logical Computation on Stochastic Bit Streams, Part III.
* Feb. 06, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-06.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-06.pptx Slides]. Topic: Computing with Nanoscale Switches.
* Feb. 11, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-11.mov Video],  [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-11.pptx Slides]. Topic: Percolation in Nanoscale Switches.
* Feb. 13, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-13.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-13.pptx Slides]. Topic: Chemical Kinetics.
* Feb. 18, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-18.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-18.ppt Slides]. Topic: Stochastic Simulation of Chemical Kinetics.
* Feb. 20, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-20.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-20.ppt Slides]. Topic: Cycle and Event Leaping
* Feb. 25, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-25.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-25.pptx Slides]. Topic: Synthesizing Stochasticity with Molecular Reactions.
* Feb. 27, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-27.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-02-27.pptx Slides]. Topic: Sequential Computation with Molecular Reactions.
* Mar. 06, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-03-06.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-03-06.pptx Slides]. Topic: Oscillations and Iterative Computation with Molecular Reactions.
* Mar. 11, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-03-11.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-03-11.pptx Slides]. Topic: Locking Chemical Computation. 
* Mar. 13, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-03-13.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-03-13.ppt Slides]. Topic: Graphical Data Structures.
* Mar. 25, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-03-25.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-03-25.ppt Slides]. Topic: Conditional Permutations, Part I.
* Mar. 27, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-03-27.mov Video]. Topic: Conditional Permutations, Part II.
* Apr, 01, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-01.mov Video]. Topic: Conditional Permutations, Part III.
* Apr. 08, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-08.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-08.pptx Slides]. Topic: Distributed Sorting, Part I.
* Apr. 10, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-10.mov Video], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-10.pptx Slides]. Topic: Distributed Sorting, Part II.
* Apr. 15, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-15.ppt Slides]. Topic: Distributed Counting.
* Apr. 17, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-17.mov Video]. Topic: XOR Function, Part I.
* Apr. 17, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-17.mov Video]. Topic: XOR Function, Part II.
* Apr. 22, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-22.mov Video]. Topic: XOR Function, Part III.
* Apr. 24, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-24.mov Video]. Topic: Neural Logic, Part I. 
* Apr. 29, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-29.ppt Slides]. Topic: Circuits with Feedback, Part I 
* Apr. 30, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-30.ppt Slides], [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-04-30.mov Video]. Topic: Symbolic Timing Analysis. 
* May &nbsp;1, 2015: [http://www.cctbio.ece.umn.edu/ee5393-2015-spring/2015-05-01.ppt Slides]. Topic: Circuits with Feedback, Part II.

== Quizzes ==

Quizzes are posted on the class Moodle page.

== Homeworks ==

* [[Media:ee5393-2015-spring-homework-01.pdf |Homework 1]], due Feb. 27, 2015
* [[Media:ee5393-2015-spring-homework-02.pdf |Homework 2]], due March 27, 2015
* [[Media:ee5393-2015-spring-homework-03.pdf |Homework 3]], due April 24, 2015
* [[Media:ee5393-2015-spring-homework-04.pdf |Homework 4]], due May 18, 2015

== Assigned Reading ==


=== Computing with Probabilities ===

* W. Qian and M. Riedel, "[[Media:Qian_Riedel_Synthesizing_Logical_Computation_on_Stochastic_Bit_Streams.pdf |Synthesizing Logical Computation on Stochastic Bit Streams]]," ''Proceedings of the Design Automation Conference'', 2009.
* W. Qian, H. Zhou, M. Riedel, and J. Bruck, "[[Media:Qian_Riedel_Zhou_Bruck_Transforming_Probabilities_with_Combinational_Logic.pdf |Transforming Probabilities with Combinational Logic]]," ''IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems'', Vol. 30, No. 9, pp. 1279&ndash;1292, 2011.
* M. Altun and M. Riedel, "[[Media:Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf |Logic Synthesis for Switching Lattices]]," ''IEEE Transactions on Computers'', Vol. 61, No. 11, pp. 1588&ndash;1600, 2012.
* M. Altun and M. Riedel, "[[Media:Altun_Riedel_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf|Synthesizing Logic with Percolation in Nanoscale Lattices]]," ''International Journal of Nanotechnology and Molecular Computation'', Vol. 3, No. 2, pp. 12&ndash;30, 2011.

=== Nanoscale Switches ===

* M. Altun and M. Riedel, "[[Media:Altun_Riedel_Logic_Synthesis_for_Switching_Lattices.pdf |Logic Synthesis for Switching Lattices]]," ''IEEE Transactions on Computers'', Vol. 61, No. 11, pp. 1588&ndash;1600, 2012.
* M. Altun and M. Riedel, "[[Media:Altun_Riedel_Synthesizing_Logic_with_Percolation_in_Nanoscale_Lattices.pdf|Synthesizing Logic with Percolation in Nanoscale Lattices]]," ''International Journal of Nanotechnology and Molecular Computation'', Vol. 3, No. 2, pp. 12&ndash;30, 2011.
* C. E. Shannon, "[[Media:Shannon_A_Symbolic_Analysis_of_Relay_and_Switching_Circuits.pdf |A Symbolic Analysis of Relay and Switching Circuits]]," ''Transactions of the AIEE'', Vol. 57, pp. 713&ndash;723, 1938.
* J. von Neumann, [[Media:Von_Neumann_Probabilistic_Logics_and_the_Synthesis_of_Reliable_Organisms_from_Unreliable_Components.pdf | Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components]], in ''Automata Studies'', C.E. Shannon and J. McCarthy eds., pp. 329&ndash;378, 1956.
* E. F. Moore and C. E. Shannon, "[[Media:Moore_Shannon_Reliable_Circuits_Using_Less_Reliable_Relays.pdf |Reliable Circuits Using Less Reliable Relays]]," ''Journal of the Franklin Institute'', Vol. 262, pages 191&ndash;208, 1956.

=== Computing with Molecules ===

* D. Gillespie, "[[Media:Gillespie-Daniel-T_Stochastic_Simulation_of_Chemical_Kinetics.pdf |Stochastic Simulation of Chemical Kinetics]]," ''Annual Revue Physical Chemistry'', Vol. 58, pp. 35&ndash;55, 2007.
* A. Arkin, J. Ross and H. McAdams, "[http://www.genetics.org/content/149/4/1633.full.pdf Stochastic Kinetic Analysis of Developmental Pathway Bifurcation in Phage lambda-Infected Escherichia coli Cells]," ''Genetics'', Vol. 149, pp. 1633&ndash;1648, 1998
* D. Gillespie, "[[Media:Gillespie-Daniel-T_Stochastic_Simulation_of_Chemical_Kinetics.pdf |Stochastic Simulation of Chemical Kinetics]]," ''Annual Revue Physical Chemistry'', Vol. 58, pp. 35&ndash;55, 2007.
* H. Jiang, A. Salehi, M. Riedel, and K. Parhi, "[[Media:Jiang_Salehi_Riedel_Parhi_Discrete-Time_Signal_Processing_with_DNA.pdf|Discrete-Time Signal Processing with DNA]]," ''ACS Synthetic Biology'', to appear, 2013.
* J. Hopfield, "[[Media:Hopfield_Neural_Networks_and_Physical_Systems_with_Emergent_Collective_Computational_Abilities.pdf |Neural Networks and Physical Systems with Emergent Collective Computational Abilities]]," Proceed
ings of the National Academy of Sciences'', Vol. 79. pp. 2554&ndash;2558, 1982.

===  Data Structures and Computation ===

* J. Aspnes, M. Herlihy, and N. Shavit, "[[Media:aspnes-herlihy-shavit-counting-networks.pdf |Counting Networks]]," ''Journal of the Association for Computing Machinery'', Vol. 41, No. 5, pp. 1020&ndash;1048, 1994.
* R. E. Bryant, "[[Media:Bryant_Symbolic_Boolean_Manipulation_with_Ordered_Binary-Decision_Diagrams.pdf |Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams]]," ''ACM Computing Surveys'', Vol. 24, No. 3, pp. 293&ndash;318, 1992.
* M. Barrington, "[[Media:Barrington_Bounded-Width_Polynomial-Size_Branching_Programs_Recognize_Exactly_Those_Languages_in_NC1.pdf | Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1]]," ''ACM Symposium on Theory of Computing'', pp. 1&ndash;5, 1986.
* M. Cook, [[Media:Cook_Networks_of_Relations.pdf | Networks of Relations]], ''Ph.D Dissertation'', Caltech, 2005.
* M. Riedel and J. Bruck, "[[Media:Riedel_Bruck_Tolerating_Faults_in_Counting_Networks.pdf |Tolerating Faults in Counting Networks]]," Chap. 12, ''Dependable Network Computing'', Kluwer, 2000.