Abstract
Everything You Always Wanted to Know About Theoretical Computer Science (But Were Afraid to Ask) (Tutorial)
Dimitris Achlioptas
UC Santa Cruz
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):
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.
No video available