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 [2019/09/12 11:33]
huang [Course Summary 2019-20: Approximation Algorithms (Lectures 1-4)]
cours:c-2-11-1 [2019/11/01 15:25] (current)
schabanel [Approximation Algorithms& Molecular Algorithms(2019/2020, 8x3h, 3 ECTS)Wednesdays 8:45-11:45 Room SG1014]
Line 4: Line 4:
 **<color green>Presumed dates for the lectures:</color>**\\ \\ **<color green>Presumed dates for the lectures:</color>**\\ \\
 ** <color gray>Approximation algorithms</color> ** ** <color gray>Approximation algorithms</color> **
-  * Lecture 1: Wed 11 SEP //Approximation algorithms 1/4// +  * <color gray>Lecture 1: Wed 11 SEP //Approximation algorithms 1/4//</color> 
-  * Lecture 2: Wed 18 SEP //Approximation algorithms 2/4// +  * <color gray>Lecture 2: Wed 18 SEP //Approximation algorithms 2/4//</color> 
-  * Lecture 3: Wed 25 SEP //Approximation algorithms 3/4// +  * <color gray>Lecture 3: Wed 25 SEP //Approximation algorithms 3/4//</color> 
-  * Lecture 4: Wed 2 OCT //Approximation algorithms 4/4//+  * <color gray>Lecture 4: Wed 2 OCT //Approximation algorithms 4/4//</color>
 ** <color gray>Molecular programming</color> ** ** <color gray>Molecular programming</color> **
-  * Lecture 5: Wed 9 OCT //Molecular algorithms 1/4// +  * <color gray>Lecture 5: Wed 9 OCT //Molecular algorithms 1/4//</color> 
-  * Lecture 6: Wed 16 OCT //Molecular algorithms 2/4// +  * <color gray>Lecture 6: Wed 16 OCT //Molecular algorithms 2/4//</color> 
-  * Lecture 7: Wed 23 OCT //Molecular algorithms 3/4//+  * <color gray>Lecture 7: Wed 23 OCT //Molecular algorithms 3/4//</color>
   * <color gray>// No lecture on Wed 30 OCT //</color>   * <color gray>// No lecture on Wed 30 OCT //</color>
   * Lecture 8: Wed 6 NOV //Molecular algorithms 4/4//   * Lecture 8: Wed 6 NOV //Molecular algorithms 4/4//
 ** <color gray>Final exam</color> ** ** <color gray>Final exam</color> **
-  * <color gray>// No lecture on Wed 13 OCT //</color> +  * <color gray>// No lecture on Wed 13 and 20 OCT //</color> 
-  * <color purple>**Final Exam: Wed 20 or 27 NOV**</color>+  * <color red>**Final Exam: Wed 27 NOV 8:45-11:45**</color>
  
 ---- ----
Line 25: Line 25:
  
 Lectures will take place every **Wednesdays 08:45-11:45 in room SG1014** starting on 11/9.  Lectures will take place every **Wednesdays 08:45-11:45 in room SG1014** starting on 11/9. 
 +
 +----
 +
 +Internship proposals:
 +  * :!: **__2020 M2 Internship proposal:__ [[http://perso.ens-lyon.fr/nicolas.schabanel/stage/2020_M2_Internship.pdf|DNA computing: Theory, Models and wet lab experiments]]**
 +
 +----
  
 ==== Goals ==== ==== Goals ====
Line 129: Line 136:
     * [[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: Molecular programming  (Lectures 5-8) ====
 +
 +**Lecture 7 (2019.10.23): Universality in assembly Model (II): experiment, intrinsic universality and Oritatami**
 +  * **An experimental realisation of a universal computer (II) [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture2B.pdf|Slides (again)]] ]**
 +    * Examples of nanotube circuits
 +    * A 6-bits Turing universal nanotube circuit
 +    * Minimizing errors with proof-reading tiles
 +    * Counting the glues
 +    * Sequence design
 +    * Experiment results
 +  * **Intrinsic Universality in tile assembly model [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture3A.pdf|Slides]] ]**
 +    * Intrinsic universality at T°2
 +    * The supercell, the probes
 +    * One (polygonal) tile is enough
 +  * **Oritami: a computational model for co-transcriptional folding [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture3B.pdf|Slides]] ]**
 +    * RNA co-transcriptional folding
 +    * Oritatami model
 +    * A first example: a binary counter
 +    * Proving its correctness
 +    * Rule design is NP-hard but FP-tractable
 +    * Oritatami is Turing complete
 +    * Simple intrinsic Oritatami simulation of cellular automata
 +  * **Exercise sessions [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW3.pdf|HW3]] ]**
 +    - :!: Window movie Lemma //**return your solution to questions 1.1 and 1.2 by Wed Nov 6 before 11:45**//
 +
 +**Lecture 6 (2019.10.16): Universality in assembly Model (I): Theory and experiment**
 +  * **Universality in assembly Model (I) [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture2A.pdf|Slides]] ]**
 +    * Simulating a Turing machine at temperature T°=2 in aTAM
 +    * Optimal hardcoding of a binary string at T°=2 in aTAM
 +    * Simulating a Turing machine at temperature T°=1 in aTAM in 3D
 +  * **An experimental realisation of a universal computer (I) [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture2B.pdf|Slides]] ]**
 +    * Single stranded tile nanotubes
 +    * Atomic Force Microscopy (AFM)
 +    * Marking 0s and 1s using biotin-streptavidin
 +    * kTAM kinetic assembly model
 +    * Error correction using proof-reading tiles
 +    * DNA nanotube circuit model 
 +  * **Exercise sessions [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW2.pdf|HW2]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW2-SOL.pdf|Solutions]] ]**
 +    - Staged self-assembly (from HW1)
 +    - Exponential random variables and kTAM implementation
 +    - :!: Tileset for simulating cellular automata  
 +    - Probabilistic simulation of Turing Machine at T°=1 in 2D
 +
 +**Lecture 5 (2019.10.09): Introduction to DNA programming & Tile Assembly Systems [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/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/2019-2020/HW1.pdf|HW1]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW1-SOL.pdf|Solutions]] ]**
 +    - Guess the assembly 1
 +    - Guess the assembly 2
 +    - :!: A binary counter
 +    - Staged self-assembly
 +    - Assembly time = O(rank of the produced shape)
 +
 +
 ==== Course Summary 2019-20: Approximation Algorithms  (Lectures 1-4) ==== ==== Course Summary 2019-20: Approximation Algorithms  (Lectures 1-4) ====
  
Line 135: Line 198:
   * Examples of Combinatorial/LP-Based/Randomized Algorithms for NP-hard Problems   * Examples of Combinatorial/LP-Based/Randomized Algorithms for NP-hard Problems
   * Min-Cut Algorithm of Karger   * Min-Cut Algorithm of Karger
-  * First Assignment+  * First Assignment [[http://www.di.ens.fr/~cchuang/devoirs_aama_2019/premier.pdf|PDF]]
    
  
 +**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]]
 +
 +**Lecture 3: Random Walk and Submodular Function ** 
 +  * 2SAT
 +  * K-Coverage 
 +
 +**Lecture 4: Semi-Definitie Programming ** 
 +  * Max-Cut
 +  * Color-Coding
 +  * Vertex-Cover Revisited
 +  * Third Assignment [[http://www.di.ens.fr/~cchuang/devoirs_aama_2019/troiseme.pdf|PDF]]  
 +  
 ===== **Archives 2018-2019 (8x3h)** ===== ===== **Archives 2018-2019 (8x3h)** =====
 ==== Course Summary 2018-19: Approximation algorithms  (Lectures 1-4) ==== ==== Course Summary 2018-19: Approximation algorithms  (Lectures 1-4) ====
 
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