[MPRI 2014] 1.24 Algorithmes randomisés (Cours n°3 - Partie C/C)
Nicolas Schabanel
2014-02-07
Views 37
MPRI 1.24 - Randomized Algorithms - Nicolas Schabanel
Lecture 3 (Part C/C): Thursday Feb 6, 8:45-11:45 - Streaming, Property testing, Self-correction
• Streaming algorithm for computing the second moment of frequencies F2 : 4-wise independent hash functions
• Self-correcting integer product
Exercise session 3: PDF Due on Thursday Feb 13 before noon
• A Fixed Parameter Tractable algorithm for finding k disjoints triangles
• A deterministic algorithm for uniformity dectection
• Matrix multiplication testing
Lecture 3 (Part C/C): Thursday Feb 6, 8:45-11:45 - Streaming, Property testing, Self-correction
• Streaming algorithm for computing the second moment of frequencies F2 : 4-wise independent hash functions
• Self-correcting integer product
Exercise session 3: PDF Due on Thursday Feb 13 before noon
• A Fixed Parameter Tractable algorithm for finding k disjoints triangles
• A deterministic algorithm for uniformity dectection
• Matrix multiplication testing
Report form
RELATED VIDEOS
