Everything You Always Wanted to Know About Theoretical Computer Science (But Were Afraid to Ask) (Tutorial)

Dimitris Achlioptas
Microsoft Research

I will try to compress an introductory Algorithms/Complexity
class and a Probabilistic Analysis of Algorithms class in 2 hours
(while leaving time for questions). Obviosuly, I will fail. Yet, I hope
that at the end of the talk the following will be clear(er):



1) The difference between NP-complete and NP-hard,

2) What is a greedy algorithm (formally),

3) The first and second moment methods,

4) The principle of deffered decisions,

5) The use of differential equations to approximate Markov chains.


Presentation (PowerPoint File), Graphs (PDF File), Formulas (PDF File)
Notes by Stephan Mertens (PDF File)

Back to Phase Transitions And Algorithmic Complexity