The course with the Cockertoo...

Randomized Algorithms

CSCE 658, Course Information, Spring 2019

The course gives an introduction to randomized algorithms. Randomization allows to design efficient algorithms, which are often of elegant simplicity. Selected tools and techniques from probability theory and game theory are reviewed, with a view towards algorithmic applications. The main focus is a thorough discussion of the main paradigms, techniques, and tools in the design and analysis of randomized algorithms. A detailed analysis of numerous algorithms will illustrate the abstract concepts and techniques. You will learn about random walks, Markov chains, the probabilistic method, discrepancy theory, etc. The basics of probability theory will be reviewed.

Instructor Dr. Andreas Klappenecker,
Office HRBB 509B
Office hours T 10:30am-11:30am, W 11:00am-noon or by appointment

General Information

Lecture Notes or Slides



R Jan 15 Introduction, Primality Tests
T Jan 17 Basics of Probability Theory
R Jan 22 Basics of Probability Theory
T Jan 24 Random Variables
T Jan 29 Random Variables, Minimum Cuts
R Jan 31 Minimum Cuts
T Feb 05 Expectation, Variance, Tail Inequalities,
R Feb 07 Conditional Expectation, Quicksort
T Feb 12 Computational Complexity Quicksort
R Feb 14 Computational Complexity
T Feb 19 Chernoff Bounds, Probability Generating Functions
R Feb 21 Probability Generating Functions, Permutation Routing on Graphs
T Feb 26 Permutation Routing on Graphs
R Feb 28 Skiplists, Probabilistic Method
T Mar 05 Probabilistic Method, Review
R Mar 07 Midterm
T Mar 12 Spring Break
R Mar 14 Spring Break
T Mar 19 The Lovász Local Lemma
R Mar 21 The Lovász Local Lemma
T Mar 26 Markov Chains
R Mar 28 Markov Chains, Coupling
R Apr 02 Markov Chains, Coupling