Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-11-1 [2018/11/24 15:08]
schabanel [Course Summary: Molecular programming (Lectures 5-8)]
cours:c-2-11-1 [2019/09/18 13:42] (current)
huang [Course Summary 2019-20: Approximation Algorithms (Lectures 1-4)]
Line 1: Line 1:
  
-===== **Approximation Algorithms\\ & Molecular Algorithms**\\ (2018/2019, 8x3h, 3 ECTS)\\ //Mondays 12:45-15:45 Room SG1004// =====+===== **Approximation Algorithms\\ & Molecular Algorithms**\\ (2019/2020, 8x3h, 3 ECTS)\\ //Wednesdays 8:45-11:45 Room SG1014// =====
  
----- +**<color green>Presumed dates for the lectures:</color>**\\ \\ 
- +** <color gray>Approximation algorithms</color> ** 
-**<color green>Dates for the next lectures:</color>** +  * Lecture 1: Wed 11 SEP //Approximation algorithms 1/4// 
-  * <color gray>Lecture 1: Mon 17 SEP //Approximation algorithms 1/4//</color> +  * Lecture 2: Wed 18 SEP //Approximation algorithms 2/4// 
-  * <color gray>Lecture 2: Mon 24 SEP //Approximation algorithms 2/4//</color> +  * Lecture 3: Wed 25 SEP //Approximation algorithms 3/4// 
-  * <color gray>Lecture 3: Mon 1 OCT //Approximation algorithms 3/4//</color> +  * Lecture 4: Wed 2 OCT //Approximation algorithms 4/4// 
-  * <color gray>Lecture 4: Mon 8 OCT //Approximation algorithms 4/4//</color> +** <color gray>Molecular programming</color> ** 
-  * <color gray>//No lecture on Mon 15 OCT//</color> +  * Lecture 5: Wed 9 OCT //Molecular algorithms 1/4// 
-  * <color gray>Lecture 5: Mon 22 OCT //Molecular algorithms 1/4//</color> +  * Lecture 6: Wed 16 OCT //Molecular algorithms 2/4// 
-  * <color gray>Lecture 6: Mon 29 OCT //Molecular algorithms 2/4//</color> +  * Lecture 7: Wed 23 OCT //Molecular algorithms 3/4// 
-  * <color gray>Lecture 7: Mon 5 NOV //Molecular algorithms 3/4//</color> +  * <color gray>// No lecture on Wed 30 OCT //</color> 
-  * <color gray>Lecture 8: Mon 12 NOV //Molecular algorithms 4/4//</color> +  * Lecture 8: Wed 6 NOV //Molecular algorithms 4/4// 
-  * <color gray>//No lecture on Mon 19 NOV//</color> +** <color gray>Final exam</color> ** 
-  * <color purple>**Final Exam: Mon 26 NOV**</color>+  * <color gray>// No lecture on Wed 13 OCT //</color> 
 +  * <color purple>**Final Exam: Wed 20 or 27 NOV**</color>
  
 ---- ----
Line 23: Line 24:
   * [[http://www.di.ens.fr/~cchuang/|Chien-Chung Huang]] ([[http://www.cnrs.fr/ins2i/|CNRS]] - [[http://www.di.ens.fr/|DIENS]]): //Approximation Algorithms//   * [[http://www.di.ens.fr/~cchuang/|Chien-Chung Huang]] ([[http://www.cnrs.fr/ins2i/|CNRS]] - [[http://www.di.ens.fr/|DIENS]]): //Approximation Algorithms//
  
-//**<color blue>Note that there will be __no intersection__ with [[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-1-24|Course 1.24]].</color>**// +Lectures will take place every **Wednesdays 08:45-11:45 in room SG1014** starting on 11/9. 
- +
-Lectures will take place every **Mondays 12:45-15:45 in room SG1004** starting on 17/9. +
  
 ==== Goals ==== ==== Goals ====
Line 74: Line 73:
   * Data Streams: Algorithms and Applications (Foundations and Trends in Theoretical Computer Science). S. Muthukrishnan. Now Publishers Inc, 2005.   * Data Streams: Algorithms and Applications (Foundations and Trends in Theoretical Computer Science). S. Muthukrishnan. Now Publishers Inc, 2005.
  
-There are no lecture notes. The lectures will be give on the board. Students will be encourage to write down lecture notes that will be made later available to everyone.+There are no lecture notes. The lectures will be given on the board. Students will be encouraged to write down lecture notes that will be made later available to everyone.
 Some additional reading will be suggested during the course. Some additional reading will be suggested during the course.
      
Line 113: Line 112:
   * [[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-11-1|2.11.1 Approximation Algorithms & molecular programming]]   * [[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-11-1|2.11.1 Approximation Algorithms & molecular programming]]
   * [[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-19|2.19 Biochemical Programming]]   * [[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-19|2.19 Biochemical Programming]]
- 
-==== Course Summary: Molecular programming  (Lectures 5-8) ==== 
  
 Some related research articles: Some related research articles:
Line 131: Line 128:
   * Oritatami:   * Oritatami:
     * [[http://perso.ens-lyon.fr/nicolas.schabanel/publications/2018/2018-ISAAC-OritatamiTuring-GearyMeunierSchabanelSeki.pdf|Oritatami is Turing universal]]      * [[http://perso.ens-lyon.fr/nicolas.schabanel/publications/2018/2018-ISAAC-OritatamiTuring-GearyMeunierSchabanelSeki.pdf|Oritatami is Turing universal]] 
-    * [[http://perso.ens-lyon.fr/nicolas.schabanel/publications/2018/2018-DNA24-OritatamiShapes-DemaineHendricksOlsenPatitzRogersSchabanelSekiThomas.pdf|Shapes in Oritatami]] +    * [[http://perso.ens-lyon.fr/nicolas.schabanel/publications/2018/2018-DNA24-OritatamiShapes-DemaineHendricksOlsenPatitzRogersSchabanelSekiThomas.pdf|Shapes in Oritatami]] 
 +==== Course Summary 2019-20: Approximation Algorithms  (Lectures 1-4) ====
  
-**Lecture 8Oritatami: A computational model for cotranscriptional molecular folding [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4.pdf|Slides]] ]**+**Lecture 1Introduction ** 
 +  * Introduction to Approximation Algorithms & overview of the field 
 +  * Examples of Combinatorial/LP-Based/Randomized Algorithms for NP-hard Problems 
 +  * Min-Cut Algorithm of Karger 
 +  * First Assignment [[http://www.di.ens.fr/~cchuang/devoirs_aama_2019/premier.pdf|PDF]] 
 + 
  
-Movies & animations: [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/RNAfolding.mov|RNA folding (slide 11)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-step1.gif|Oritatami step 1 (slide 15)]] [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-step2.gif|(slide 21)]] [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-several-max.gif|3 (slide 25)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-counter.mp4|Oritatami counter (slide 30)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/ModuleG.mp4|Module G (slide 102)]] ]+**Lecture 2: Chernoff Bounds ** 
 +  * Christofides' TSP algorithm 
 +  * Chernoff Bounds 
 +  * Integer Multi-commodity Flow 
 +  * 3-Coloring Dense Graphs 
 +  * Second Assignment [[http://www.di.ens.fr/~cchuang/devoirs_aama_2019/deuxieme.pdf|PDF]]
  
-  * **Co-transcriptional RNA folding experiment** +**Special Announcement: There will be a seminar talk by Professor Jens Vygen on traveling salesman problem this Friday (Sep 20, 2019), 3PMIt will be held at ENS Ulm, Salle de réunionIf you are interested in attending, feel free to contact the instructor.**  
-  * **Oritatami** +===== **Archives 2018-2019 (8x3h)** ===== 
-    * The model +==== Course Summary 2018-19: Approximation algorithms  (Lectures 1-4) ====
-    * A binary counter +
-    * Proving the binary counter +
-  * **Complexity** +
-    * NP-hardness of the rule design problem +
-    * Fixed parameter linear-time algorithm of the rule design problem +
-  * **Efficient Turing machine simulation in oritatami** +
-    * Skipping cyclic tag systems (SCTS) +
-    * Simulating SCTS with oritatami +
-    * Proving the correctness of the simulation +
-    * Oritatami programming toolbox: switchback/glideroffsets, exponential coloring & socks +
-    * Proving the correctness of the implementation +
-  * **Exercise sessions** +
-      - HW2 exercise 1       +
-      - HW3 exercise 2 +
- +
-**Lecture 7: Strand Displacement** +
-  * **Boolean circuits using Strand displacement [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture3.pdf|Slides (by Chris Thachuk)]] ]** +
-    * Making an AND gate: rough computation of energy and entropy deltas +
-    * Composing gates: making a wire +
-    * Reading the result optically: fluorophore and quencher +
-    * Implementing a reaction gate +
-    * Implementing monotonic gates (AND and OR) +
-    * Handling NOT gates with dual rails +
-    * Moving NOT gates to the top +
-    * Robustness: preventing leaking: +
-      * Fixing molecular synthesis imperfection +
-      * Using double long domains (DLD) +
-    * Presenting Breadboard 1.+
-  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW3.pdf|HW3]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW3-SOL.pdf|Solutions]] ] +
-      - :!: **DNA circuits (Assignment to return on Monday 12/11 before 12:45)**  +
-      - Building shapes with oritatami +
- +
-**Lecture 6: Universality in assembly models & Introduction to Strand displacement** +
-  * **Universality in assembly models [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture2A.pdf|Slides A]] ]** +
-    * aTAM simulate Turing machines at temperature T=+
-    * Optimal seed encoding at T=2: Kolmogorov complexity & unpacking +
-    * aTAM simulate Turing machines at temperature T=1 in 3D but not 2D +
-    * Intrinsic universality of aTAM at temperature T=+
-    * One (polygonal) tile is enough! +
-  * **Introduction to Strand displacement [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture2B.pdf|Slides B (by Chris Thachuk)]] ]** +
-  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW2.pdf|HW2]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW2-SOL.pdf|Solutions]] ] +
-    - Tileset for simulating cellular automata +
-    - Probabilistic simulation of Turing machine at temperature T=1 in 2D +
-    - :!: **Window movie lemma (Assignment to return on Monday 5/11 before 12:45: solve questions 3.1 and 3.2)**  +
- +
-**Lecture 5: Introduction to DNA programming & Tile Assembly Systems [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture1.pdf|Slides]] ]** +
-  * Introduction to DNA programming & overview of the field +
-  * Abstract tile assembly systems: +
-    * Definition +
-    * Minimizing the assembly time +
-  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW1.pdf|HW1]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW1-SOL.pdf|Solutions]] ] +
-    - Guess the assembly 1 +
-    - Guess the assembly 2 +
-    - **:!: A binary counter (Assignment to return on Monday 29/10 before 12:45)**  +
-    - Staged self-assembly +
-    - Assembly time O(rank of the produced shape) +
-    - Minimum number of tiles self-assembling squares and rectangle +
- +
-==== Course Summary: Approximation algorithms  (Lectures 1-4) ====+
  
 **Lecture 1 Introduction to Randomised and Approximation Algorithms** **Lecture 1 Introduction to Randomised and Approximation Algorithms**
Line 225: Line 174:
   * Max-Cut   * Max-Cut
   * Color-Coding and Vertex-Feedback Set   * Color-Coding and Vertex-Feedback Set
 +
 +==== Course Summary 2018-19: Molecular programming  (Lectures 5-8) ====
 +
 +**Lecture 5: Introduction to DNA programming & Tile Assembly Systems [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture1.pdf|Slides]] ]**
 +  * Introduction to DNA programming & overview of the field
 +  * Abstract tile assembly systems:
 +    * Definition
 +    * Minimizing the assembly time
 +  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW1.pdf|HW1]] ]
 +    - Guess the assembly 1
 +    - Guess the assembly 2
 +    - :!: A binary counter
 +    - Staged self-assembly
 +    - Assembly time = O(rank of the produced shape)
 +    - Minimum number of tiles self-assembling squares and rectangle
 +
 +
 +
 +
 +**Lecture 6: Universality in assembly models & Introduction to Strand displacement**
 +  * **Universality in assembly models [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture2A.pdf|Slides A]] ]**
 +    * aTAM simulate Turing machines at temperature T=2
 +    * Optimal seed encoding at T=2: Kolmogorov complexity & unpacking
 +    * aTAM simulate Turing machines at temperature T=1 in 3D but not 2D
 +    * Intrinsic universality of aTAM at temperature T=2
 +    * One (polygonal) tile is enough!
 +  * **Introduction to Strand displacement [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture2B.pdf|Slides B (by Chris Thachuk)]] ]**
 +  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW2.pdf|HW2]] ]
 +    - Tileset for simulating cellular automata
 +    - Probabilistic simulation of Turing machine at temperature T=1 in 2D
 +    - :!: Window movie lemma
 +
 +**Lecture 7: Strand Displacement**
 +  * **Boolean circuits using Strand displacement [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture3.pdf|Slides (by Chris Thachuk)]] ]**
 +    * Making an AND gate: rough computation of energy and entropy deltas
 +    * Composing gates: making a wire
 +    * Reading the result optically: fluorophore and quencher
 +    * Implementing a reaction gate
 +    * Implementing monotonic gates (AND and OR)
 +    * Handling NOT gates with dual rails
 +    * Moving NOT gates to the top
 +    * Robustness: preventing leaking:
 +      * Fixing molecular synthesis imperfection
 +      * Using double long domains (DLD)
 +    * Presenting Breadboard 1.0
 +  * **Exercise sessions** [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/HW3.pdf|HW3]] ]
 +      - :!: DNA circuits
 +      - Building shapes with oritatami
 +
 +
 +**Lecture 8: Oritatami: A computational model for cotranscriptional molecular folding [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4.pdf|Slides]] ]**
 +
 +Movies & animations: [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/RNAfolding.mov|RNA folding (slide 11)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-step1.gif|Oritatami step 1 (slide 15)]] [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-step2.gif|2 (slide 21)]] [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-several-max.gif|3 (slide 25)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/oritatami-counter.mp4|Oritatami counter (slide 30)]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2018-2019/Lecture4media/ModuleG.mp4|Module G (slide 102)]] ]
 +
 +  * **Co-transcriptional RNA folding experiment**
 +  * **Oritatami**
 +    * The model
 +    * A binary counter
 +    * Proving the binary counter
 +  * **Complexity**
 +    * NP-hardness of the rule design problem
 +    * Fixed parameter linear-time algorithm of the rule design problem
 +  * **Efficient Turing machine simulation in oritatami**
 +    * Skipping cyclic tag systems (SCTS)
 +    * Simulating SCTS with oritatami
 +    * Proving the correctness of the simulation
 +    * Oritatami programming toolbox: switchback/glider, offsets, exponential coloring & socks
 +    * Proving the correctness of the implementation
 +  * **Exercise sessions**
 +      - HW2 exercise 1      
 +      - HW3 exercise 2
 +
  
 ===== **Archives 2017-2018 (8x3h)** ===== ===== **Archives 2017-2018 (8x3h)** =====
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA