CMSC498C - Randomized Algorithms
Course Information
Randomness can be a powerful resource in almost every area of computer science. This course gives an overview of this subject: how to analyze random processes, and how to apply them to computational tasks. Subjects include: an introduction to discrete probability theory, random variables, and concentration inequalities; randomized sorting and searching algorithms, approximation algorithms via randomized rounding, randomized data structures, distributed computing, summary statistics, sampling, and streaming. The course outline follows Mitzenmacher & Upfal's "Probability and Computing" textbook, with additional supplementary material and examples.
| Instructor | Section | Day & Time | Location |
|---|---|---|---|
| David Harris | 0101 | TuTh 5:00PM - 6:15PM | CSI 2120 |
Course Prerequisite(s)
Prerequisite: CMSC330 and CMSC351; and permission of department.
Class Webpage
Hours Per Week
Languages Used
Recommended Prior Experience
This course will use discrete probability, and will not deal rigorously with more advanced forms of probability theory which would be studied in a mathematics department. Only a high-school level background in this subject is assumed. Aside from this it will be mathematically rigorous and students are expected to be comfortable with formal proofs and analysis of algorithms.
Projects, Exams, or other Assessments
The grading will be based on regular homework problem sets, a mid-term, and a final exam.
Misc Info
