# 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 **