3
$\begingroup$

I would like to read some books (or any other material) that cover the design of randomized algorithms with a particular focus on the analysis. My main goal is to develop the rigour needed to construct the proof of correctness for such algorithms.

I am currently reading Probability and Computing - M. Mitzenmacher, E. Upfal, which I find to be a good introduction to this topic.

What are your suggestions?

$\endgroup$
  • 1
    $\begingroup$ If you truly want to develop 100% mathematical rigour, you will have to first learn to use a deductive system for FOL (first-order logic), and then you can easily do all mathematics in any field (not just in algorithm analysis) completely rigorously even if you are reading a mathematically sloppy book. I assure you that this is more important than many people think, because I have seen many people who are well-published in top CS journals on algorithms who make basic quantifier errors. You might escape most errors if your intuition is sharp enough, but true rigour requires a full grasp of FOL. $\endgroup$ – user21820 Jul 27 at 3:30
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

I do not know if it meets your needs but MIT's OCW site has free lecture notes from a class on the subject here:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-856j-randomized-algorithms-fall-2002/lecture-notes/

It also has assignments and answers here:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-856j-randomized-algorithms-fall-2002/assignments/

The syllabus refers to the book one of the other answers lists and it has links to related OCW classes:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-856j-randomized-algorithms-fall-2002/syllabus/

Maybe this material will help. Nice that they provide free lecture notes as PDF files.

Bobby

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The Book 'The Design of approximation algorithms' contains some chapters regarding randomized (approximation) algorithms.

I think it is well written and some algorithms would be easy to understand for 'beginners'.

It is free for everyone https://www.designofapproxalgs.com/index.php

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.