2110712 Analysis of
Algorithms Part2
Somchai Prasitjutrakul
Part1
Prabhas Chongstitvatana Part2
My lecture this year will be mainly probabilistic algorithms and if
time permits, I will discuss comuputational complexity.
Lecture
basic statistics
probabilistic algorithms
introduction (ppt)
probabilistic counting
(ppt)
numerical: Buffon's estimate of
pi (ppt)
Monte Carlo algorithms (ppt)
amplification of stochastic
advantage (ppt)
Las Vegas algorithms (ppt)
8-queen backtrack
(ppt)
8-queen LV
computer code
primality testing (ppt)
Rabin Miller
factorization (ppt)
Computational Complexity
NP-Complete
Undicidability
Diagonalisation
Please hand in the solution by the next lecture.
1 cardinality of very large sets.
Reading
Brassard, G., Bratley, P., Fundamentals of algorithmics, Prentice hall,
1996.
Cormen,Lieserson, Rivest, Stein, Intro to algorithms, 2ed, MIT press,
2001.