230
edits
Changes
CMSC498C - Randomized Algorithms (view source)
Revision as of 18:20, 10 October 2016
, 18:20, 10 October 2016no edit summary
'''Course Information''' <br>
'''Course Information''' <br>
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.
{| style="text-align:left; width: 550PX;"
{| style="text-align:left; width: 550PX;"
''' Recommended Prior Experience ''' <br>
''' Recommended Prior Experience ''' <br>
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 ''' <br>
''' Projects, Exams, or other Assessments ''' <br>
The grading will be based on regular homework problem sets, a mid-term, and a final exam.
''' Misc Info ''' <br>
''' Misc Info ''' <br>