Notes on Randomized Algorithms

Notes on Randomized Algorithms

These are notes for the Yale course CPSC 469/569 Randomized Algorithms.

Publication date: 29 Oct 2020

ISBN-10: n/a

ISBN-13: n/a

Paperback: 459 pages

Views: 5,346

Type: Lecture Notes

Publisher: n/a

License: Creative Commons Attribution-ShareAlike 4.0 International

Post time: 03 Mar 2021 12:00:00

Notes on Randomized Algorithms

Notes on Randomized Algorithms These are notes for the Yale course CPSC 469/569 Randomized Algorithms.
Tag(s): Algorithms and Data Structures
Publication date: 29 Oct 2020
ISBN-10: n/a
ISBN-13: n/a
Paperback: 459 pages
Views: 5,346
Document Type: Lecture Notes
Publisher: n/a
License: Creative Commons Attribution-ShareAlike 4.0 International
Post time: 03 Mar 2021 12:00:00
Summary/Excerpts of (and not a substitute for) the Creative Commons Attribution-ShareAlike 4.0 International:
You are free to:

Share — copy and redistribute the material in any medium or format
Adapt — remix, transform, and build upon the material for any purpose, even commercially.

The licensor cannot revoke these freedoms as long as you follow the license terms.

Click here to read the full license.
From the Preface:

James Aspnes wrote:
These are notes for the Yale course CPSC 469/569 Randomized Algorithms. This document also incorporates the lecture schedule and assignments, as well as some sample assignments from previous semesters. Because this is a work in progress, it will be updated frequently over the course of the semester. 

Much of the structure of the course follows Mitzenmacher and Upfals's Probability and Computing: Randomized Algorithms and Probabilistic Analysis [MU05], with some material from Motwani and Raghavan's Randomized Algorithms [MR95]. In most cases you'll find these textbooks contain much more detail than what is presented here, so it is probably better to consider this document a supplement to them than to treat it as your primary source of information. 

The most recent version of these notes will be available at http://www.cs.yale.edu/homes/aspnes/classes/469/notes.pdf. More stable archival versions may be found at https://arxiv.org/abs/2003.01902

I would like to thank my many students and teaching fellows over the years for their help in pointing out errors and omissions in earlier drafts of these notes. 




About The Author(s)


James Aspnes is a professor in the Computer Science Department at Yale. He is also the Director of Undergraduate Studies for the Computer Science department. His main area of research is distributed algorithms. 

James Aspnes

James Aspnes is a professor in the Computer Science Department at Yale. He is also the Director of Undergraduate Studies for the Computer Science department. His main area of research is distributed algorithms. 


Book Categories
Sponsors