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/10/21 15:48] (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//   * Lecture 7: Wed 23 OCT //Molecular algorithms 3/4//
   * <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 129: Line 129:
     * [[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 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 nantubes
 +    * Atomic Force Microscopy (AFM)
 +    * Marking 0s and 1s using biotin-ptreptavidin
 +    * kTAM cinetic 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]] ]**
 +    - Staged self-assembly (from HW1)
 +    - Exponential random variables and kTAM implementation
 +    - :!: Tileset for simulating cellular automata  //**return your solution by Wed Oct 23 before 11:45**//
 +    - 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 168:
   * 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