What's new

Lecture  ( sd = slide gif,  ppt = powerpoint,   scm = screencam )

• Graph algorithm
• Bread first search :  html  sd1  sd2
• Shortest parth :   sd1  sd2  sd3
• Depth first search :  html  sd1  sd2
• Topological sort :  html  sd
• Strongly connected components :  html sd1  sd2
• Minimum spanning tree  :   html
• generic MST
• Kruskal's algorithm
• Prim's algorithm
• Single source shortest path
• slides   sd1   sd2 sd3
• screencam part1 part2part3part4part5
• power point presentation
• Branch and Bound  ppt  scm1scm2scm3scm4
• Probabilistic algorithm ( whole ppt zip 205K )
• introduction ppt  scm1scm2
• numerical : Buffon's needle  pptscm1scm2
• numerical : Monte Carlo integration pptscm
• probabilistic counting  scm
• Monte Carlo : Primality test  ppt
• amplification of stochastic advantage pptscm1scm2
• Las Vegas algorithm  ppt scm1scm2 scm3
• factorising large integers  ppt scm1scm2scm3
• NP-complete  ( whole ppt  zip  42K )
• class P : ppt   scm1  scm2   scm3  scm4  scm5
• class NP :  ppt  scm1  scm2   scm3  scm4
• NP-complete problem & unsolvable : ppt   scm1  scm2  scm3

Programming Assignment

• RSA Crypto System (old)
• Large Prime (old)
• 0/1 Knapsack due date 25 August 2000

Excercise for practicing your skill

• Branch and Bound
• Buffon's needle
• Probabilistic counting
• Probabilistic algorithm
• NP-complete