The course with the Cockertoo...

Randomized Algorithms

CSCE 658, Course Information, Spring 2018

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 TW 1:30-2:30pm or by appointment

General Information

Lecture Notes or Slides



R Jan 18 Introduction, Primality Tests
T Jan 23 Basics of Probability Theory
R Jan 25 Borel sets, Random Variables
T Jan 30 Random Variables, Minimum Cuts
R Feb 01 Minimum Cut Algorithms
T Feb 06 Expectation, Variance, Tail Inequalities
R Feb 08 Quicksort, Conditional Expectation
T Feb 13 Conditional Expectation given a Random Variable
R Feb 15 Conditional Expectation given a Sigma-Algebra, Quicksort (analysis w/ cond. expectation)
T Feb 20 Complexity Classes
R Feb 22 Complexity Classes, Chernoff Bounds
T Feb 27 Chernoff Bounds, Probability Generating Functions
R Mar 01 Probability Generating Functions, Permutation Routing on Graphs
T Mar 06 Permutation Routing
R Mar 08 Permutation Routing, Skip Lists
T Mar 13 Spring Break, no classes
R Mar 15 Spring Break, no classes
T Mar 20 Review
R Mar 22 Midterm
T Mar 27 Solution to midterm exam, Probabilistic Method
R Mar 29 Probabilistic Method
T Apr 03 The Lovasz Local Lemma
R Apr 05 Markov Chains
T Apr 10 Markov Chains, Markov Chain Monte Carlo
R Apr 12 Monte Carlo Methods
T Apr 17 Coupling of Markov Chains, Mixing Time
T Apr 19 Coupling of Markov Chains
T Apr 24 Expander Graphs
R Apr 26 Expander Graphs