Book recommendations on the analysis of randomized algorithms
Randomized Algorithms by Motwani, Rajeev, and Raghavan contains a lot of excellent material on the design and analysis of algorithms.  They show many proofs of correctness for different randomized algorithms.