Dates for the next lectures:
Lecture 1: Mon 17 SEP Approximation algorithms 1/4
Lecture 2: Mon 24 SEP Approximation algorithms 2/4
Lecture 3: Mon 1 OCT Approximation algorithms 3/4
Lecture 4: Mon 8 OCT Approximation algorithms 4/4
No lecture on Mon 15 OCT
Lecture 5: Mon 22 OCT Molecular algorithms 1/4
Lecture 6: Mon 29 OCT Molecular algorithms 2/4
Lecture 7: Mon 5 NOV Molecular algorithms 3/4
Lecture 8: Mon 12 NOV Molecular algorithms 4/4
No lecture on Mon 19 NOV
Final Exam: Mon 26 NOV
Teachers:
Note that there will be no intersection with Course 1.24.
Lectures will take place every Mondays 12:4515:45 in room SG1004 starting on 17/9.
This lecture explore actual trends in algorithms (and complexity). We will first focus on classic technique mainly based on randomness to obtain approximate solutions to NPhard problems with proven guarantee. Second, we will explore how algorithms (randomized algorithms and structures) can help understanding better how nature works.
Approximation algorithms: We will first learn how to provide guarantee on the quality of a solution with respect to the optimal when the optimal cannot be computed because either the problem considered is NPhard or no known exact algorithms are fast enough to be effective. We will practise the various technics designed to analyze its cost guarantee. This field makes extensive use of randomness in order to improve performances.
Molecular algorithms: The second part of the lectures will be dedicated to an introduction to the new field of molecular programming where people are developing theoretical algorithmic models and realizing in wetlab experiments computers compatible with life as we know it. Exploiting the flexibility of DNA molecule, implementations of this new of a kind computer are already happening. We will explore the very rich theory behind this field and hopefully realize some wetlab experiments together to implement algorithms using molecular interactions. Computations in these models are naturally random.
Approximation algorithm design essentially consists on the positive side in finding the proper relaxation of the constraints in the initial problem in order to get a polynomialtime estimate of the optimal that can then be converted into a solution of the initial problem. The art consists in showing that the quality of the solution does not change in the process. Typical tools are linear and semidefinite programming. On the negative side, it consists in using the celebrated PCP theorem and polynomial reductions (very similar to the classic NPhardness reductions) to show that some problems cannot be approached within some factor unless P=NP or other catastrophes of the same kind.
In this second part of the lecture, we will overview the various approaches to the exciting and uprising field of Molecular programming where one uses algorithms to design real molecules that processes information algorithmically. We will explore in details the various theoretical models, their complexity and expressiveness, learn how to program them and survey their experimental realizations, in particular how to design algorithmically these molecules for real. Depending on the timing, we hope to be able to have you take part to a real wetlab experiments where we will have molecules executing a (simple) program for us and observe at the end of its execution the nanoscopic results (usually only about few 100nm large) thru atomic force microscope (to be confirmed).
A good base in algorithms and complexity is helpful (elementary algorithms, circuits, complexity classes). Knowledge of discrete probabilities and basic information theory (Shannon entropy) helpful.
Approximation algorithms: (4 sessions)
Molecular Algorithms theory and practice (4 sessions)
Tile selfassembly system: model, intrinsic universality, algorithms, realizations, DNA computing nanotubes
Boolean circuits: model, circuit, realizations
RNA based computing: oritatami systems, shapes, Turing universality
Experiments: how do we proceed
The lectures will be given in english unless every attendee is fluent in french.
The exam will be given in English, and can be written by the students in either language (french or english).
Every session will consist in general of ≈2h lecture followed by ≈1h exercises session.
A small exercise will be given as an homework at the end of each session to be returned for the next session.
Algorithmes d'approximation, V. Vazirani, Springer, 2006 (traduit de l'américain par N. Schabanel)
Approximation algorithms, V. Vazirani, Springer, 2001
Probability And Computing: Randomized Algorithms And Probabilistic Analysis, by M. Mitzenmacher and E. Upfal, Cambridge University Press, 2005
Computational Complexity: A Modern Approach . S. Arora and B. Barak. Cambridge University Press, 2009.
Communication Complexity. E. Kushilevitz and N. Nisan. Cambridge University Press, 1997.
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.
Some additional reading will be suggested during the course.
Internships are available. Contact the teachers of the lectures directly (for instance by email):
The following is a coherent list of courses on the thematic 'Algorithms and Complexity'.
The following is a coherent list of courses on the thematic 'Molecular and Biological programming & modelling'.
Some related research articles:
Lecture 8: Oritatami: A computational model for cotranscriptional molecular folding [ Slides ]
Movies & animations: [ RNA folding (slide 11)  Oritatami step 1 (slide 15) 2 (slide 21) 3 (slide 25)  Oritatami counter (slide 30)  Module G (slide 102) ]
Lecture 7: Strand Displacement

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:
Presenting Breadboard 1.0

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 [ 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!


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 [ Slides ]
Lecture 1 Introduction to Randomised and Approximation Algorithms
Lecture 2 Chernoff Bounds
Lecture 3
Lecture 4
Lecture 1 Introduction to Approximation Algorithms
Introduction to the Course
Optimization problems & Approximation Algorithms
Set Cover (two LPbased approximation algorithms)
Min Cut of Karger

Lecture 2 Chernoff Bound
Lecture 3 Max Cut
An algorithm of Fernandez de la Vega for max cut in dense graph (an exposé of Nicholas Schabanel is here
PDF)

Lecture 4 SemiDefinite Programming
Lecture 5: Introduction to molecular programming & Tile assembly systems (Oct 18) Video
Introduction to the course [0:00:00]
A little history of the field [0:09:14]
Tile assembly systems [0:35:41]
A binary counter [0:51:50]
Minimizing the assembly time [1:10:01]
Exercises session [1:51:44] HW1 PDF
Guess the assembly 1
Guess the assembly 2
A counter
Staged assembly of a candelabrum
Expected assembly time & rank of a construction
Minimum number of tiles for the families of squares and rectangles
Lecture 6: Universality in tile assembly systems (Oct 25) Video
Simulating Turing Machines at T°=2 [0:00:00]
Kolmogorov Complexity [0:29:02]
Lower Bounding the minimal number of tiles to hardcode the input seed with Kolmogorov complexity [0:54:16]
Optimal number of tiles for hardcoding the seed [1:06:43]
Exercises session [1:42:54] HW2 PDF
HW1 exercise 5: Assembly time = O(rank) w.h.p.
Lecture 7: Universality in Tile Assembly and Oritatami Systems (Nov 8) Video
Tile sets selfassembling an arbitrary shape [0:00:00]
TuringUniversal tile set in 3D at T°1 [0:29:05]
Intrinsically universal tile set in 2D at T°2 [0:49:06]
Magic Powder [1:11:56]
Oritatami: A model for cotranscriptional folding [1:15:19]
Exercise session:
Designing DNA origami using cadnano [2:19:08]
Lecture 8: Some experimental achievements in DNA programing (Nov 15) Video
The equipment: Pipetters, thermocycler & AFM microscopy [0:00:00]
A tour of built DNA nanostructures [0:39:17]
DNA single stranded tiles [1:00:41]
Stacking interactions [1:01:29]
Strand displacement [1:03:55]
Exercise session:
cadnano is back [1:11:49]
HW16: Tile set of minimimum size for Squares and Rectangles [1:15:28]
HW21: Discrete slope [1:31:01]
HW22: Window movie lemma [1:42:40]
Lecture 1 [Wed 14/9/2016 16:1519:15] Introduction to Approximation Algorithms Video
Introduction to the Course
Optimization problems & Approximation Algorithms
About Hardness of approximation
Approximation Algorithms for Metric TSP

3/2Approximation for Metric TSP
Costbased approximation for Vertex Cover
Maximum ArcDisjoint Paths (1)
Lecture 2 [Wed 21/9/2016 16:1519:15] Mathematical Programming 1: Linear programming Video
Mathematical Programming [0:00:00]
Introduction to Linear Programming [0:01:45]
First Example: MaxCUT as an Integer Program [0:07:04]
LP Relaxation for MaxCUT & Randomized Rounding [0:38:16]
MaxSAT: Random Assignment [1:09:26]
MaxSAT: Randomized Rounding [1:24:23]
MaxSAT: Combining both Algorithms into One [2:12:33]

Dumb Algorithm for MaxSAT
Metric
kCenter
SDP Approximation for Weighted Max2SAT
Lecture 3 [Wed 28/9/2016 16:1519:15] Mathematical Programming 2: Semidefinite / Vector programming Video
0. Introduction [0:00:00]
1. A quadratic program for MaxCUT [0:02:09]
2. Relaxing a Quadratic Program as a Vector Program [0:10:17]
3. Vector Programs = SemiDefinite Programs [0:16:14]
4. VP is indeed a relaxation of integer QP [0:27:28]
5. Rounding VP: the Random Hyperplane Technic [0:38:43]
6. Analysis of the Random Hyperplane Algorithm [1:10:09]

Randomized Rounding for Set Cover
Lecture 4 [Wed 5/10/2016 16:1519:15] Polynomial Time Approximation Schemes Video
0. (F)PT(R)AS: (Fully) PolynomialTime (Randomized) Approximation Schemes [0:00:00]
1. A FPTAS for the Knapsack Problem [0:10:31]
2. A FPTRAS for MaxCut in αDense Graphs [1:05:27]

A PTAS for the Minimum Cost Overflow Problem
Lecture 5 [Wed 26/10/2016 16:1519:15] Nature Programming: Abstract Tile Assembly Model Slides
0. Introduction to Nature programming & DNA assembly
1. Abstract Tile Assembly Model
2. A binary counter
3. Minimizing the assembly time for squares & cubes

Guess the result of the algorithmic SelfAssembly (I)
Guess the result of the algorithmic SelfAssembly (II)
Counter at T°=2
Staged assembly scheme at temperature T°=1
Concentrations, Rank and Assembly time
Minimum number of tile types for squares and rectangles
Lecture 6 [Wed 2/11/2016 16:1519:15] Nature Programming: Universality in Tile Assembly Systems Video
0. HW4: NPcompleteness & Optimization Problems [0:00:00]
1. Turing Universality in tile assembly systems [0:05:43]
2. Turing universality at T°=2 [0:12:31]
3. Turing universality at T°=1 [0:36:19]
4. Minimizing the number of tiles to build a shape [1:19:04]
Exercise Session 6: [2:31:39]
HW5(2): Assembly time, rank & concentrations
Lecture 7 [Wed 9/11/2016 16:1519:15] Nature programming: Intrinsic Universality & Other Models including Oritatami Video
0. Theory vs Practice [0:00:00]
1. Intrinsic Universality of Tile Assembly Systems at T°=2 [0:04:59]
2. One (Polygonal) Tile is Enough! [0:39:20]
3. Other Models: BioLogical Circuits [0:43:00]
4. Nubots: a Model for Molecular Reconfiguration [0:49:43]
5. About Experiments: Nanotubes that Compute [0:54:07]
6. Oritatatami: one Molecule that computes cotranscriptionally [0:58:26]
6.1 Experiment: Synthetic RNA CoTranscriptional Foldingbased Meshes [0:58:54]
6.2 Oritatami: A Model for CoTranscriptional Folding [1:11:58]
6.3 Oritatami: How to Compute? [1:18:02]
6.4 Oritatami: Rule Design is NPhard but Fixed Parameter Tractable [1:31:55]
6.5 Oritatami Systems simulate efficiently Turing machines [1:41:20]
6.6 Oritatami: How to Prove the Correctness? [2:04:36]
6.7 Oritatami: Conclusion [2:28:48]
No Exercise Session
Lecture 8 (last) [Wed 9/11/2016 16:1519:15] Nature programming: Experiments
1. Description of the recent experiment of Damien Woods et al on building nanotubes implementing 6bit circuits computation
2. Introduction to CADNano, a DNA Origami Designer
3. Introduction to NUPack, a DNA/RNA strand(s) energy/partition function calculator
Lecture 1 [18/9/2014] NPcompleteness, Hardness of approximation & Approximation algorithms Video 1 2 3
Introduction to approximation algorithms
NPcompleteness, PCP theorem & hardness of approximation
Definitions: Optimization problem & Approximation
Hardness of approximation for nonmetric TSP
A 2approximation for metric TSP
A 3/2approximation for metric TSP

MaxCut: randomized 2approximation and greedy approximation by the conditional expectation method
Coloring 3colorable graphs
Costbased 2approximation for Vertex Cover
Lecture 2 [25/9/2014] Introduction to Integer Programming, Linear Relaxation and Rounding Video 1 2 3
MaxSAT
Random solution to MaxSAT
A (11/e)approximation based on a randomized rounding of a solution to a linear program for MaxSAT
Mixing both algorithms yield a 3/4approximation

Dumb algorithm for MaxSAT
Simple rounding fapproximation for Set Cover
Randomized rounding (ln(n)+O(1))approximation for Vertex Cover
2 and 3approximations for Minimum Weighted Sum of Completion Time Scheduling with dependencies and with and without release dates
Lecture 3 [16/10/2014] PTAS: Polynomial Time Approximation Schemes Video 1 2 3
Lecture 4 [23/10/2014] Introduction to semidefinite programming Video 1 2 3
From quadratic formulation to vector program
Rounding with cutting hyperplanes for MaxCut
A O(n^{1/3})approximation for coloring 3colorable graphs

How to draw unit vector uniformly at random
A O(n^{1/4})approximation for coloring 3colorable graphs
Lecture 5 [30/10/2014] Introduction to Lasserre's hierarchy (1/2) Video 1 2 3
Important properties of semidefinite matrices
Equivalence of vector programs and semidefinite programming
Definition of Lasserre's hierarchy
First properties of the solutions
Decomposition: lemma and theorem
No exercise session today
Lecture 6 [6/11/2014] Lasserre's hierarchy (2/2) Video 1 2 3
Lecture 7 [13/11/2014] Natural algorithms: the SmallWorld phenomenon Video 1 2 3
Sociological context: Milgram's experiment
First Small World models
Kleinberg's augmented grid model
Case α < 2: Longrange links are too messy
Case α > 2: Longrange links are too short
Case α = 2: The greedy algorithm
SmallWorld emergence: the MoveandForget model
No exercise session today
Lecture 8 (last) [20/11/2014] Algorithmic selfassembly & Nonclairvoyant scheduling Video 1 2 3
Introduction to Approximation Algorithms
P vs NP, a refinement of NPcompleteness: Inapproximability results
Definitions of Optimization problems and Approximation algorithms
General principles for obtaining approximation algorithms
An exemplary example: the Travelling Salesman Problem
Definition of TSP
Inapproximability of general TSP unless P = NP
A first 2approximation algorithm (MSTbased)
Cristofides algorithm: a 3/2approximation algorithm
Family of tight instances for both algorithms
Random Cut for MaxCut and derandomization by the conditional expectation method
2approximation for Metric Steiner Tree and isofactor reduction from general to metric
Linear Programming
Introduction, LP Relaxation, First rounding (VertexCover)
Duality and Complementary Slackness Conditions
Application: primaldual algorithm for VertexCover & Maximum/al Matching
(Note for next year: primal dual algorithm for SetCover would have been a better choice)
Basic duality manipulation
A randomized LProunding algorithm for SetCover
Definition of PTAS, PTRAS, example of dependence in ε
Dense MaxCut
A first algorithm
The PTRAS
A FixedParameter Tractable (FPT) algorithm for k disjoint triangles
A Constant Time Approximation Scheme (CTAS) for the size of a maximal matching
A little bit of history
Gap problems and Hardness of approximation
The CSP: Graph Constraints Satisfaction Problem
Overview of the Gap amplication process 2.a) definition
A key tool: Expander graphs I
Step 1: Degree uniformization
Step 2: Expanderization
Expander graphs II: spectral theory and random walks
Step 3: Gap amplification
Step 4 (last): Alphabet reduction
Gappreserving reductions
Gappreserving reductions for VertexCover and Steiner Tree
Random walks on expanders