CMSC498C - Randomized Algorithms

From CS 400 Level Course Wiki
Jump to: navigation, search

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