CSE 432LEC - Randomized Algorithms Analysis and Design

This course explores applications of probabilistic techniques to computer science. The main focus is how to leverage randomness in algorithms and how to perform probabilistic analysis of algorithms. Randomized algorithms are often faster and simpler than their deterministic counterparts, with the weaker assertion that correctness is not always guaranteed. Coverage includes analyzing algorithms via proofs and programming assignments to implement algorithms and sampling techniques. Topics include probabilistic method, balls and bins, random graphs, random walks, discrete time Markov chains, the Monte Carlo method, and examples of applications in many areas of computer science.

Credits: 3

Grading
Graded (GRD)

Typically Offered:
Spring

Requisites:
Pre-requisite: CSE 331 and (EAS 305 or EE 305 or MTH 411 or STA 301 and STA 301). Computer Science, Computer Engineering, or Bioinformatics majors only.