Go to Main Content

Purdue Self-Service



Detailed Course Information


Fall 2022
Aug 07, 2022
Transparent Image
Information Select the desired Level or Schedule Type to find available classes for the course.

CS 58800 - Randomized Algorithms
Credit Hours: 3.00. The area of randomized algorithms has grown from being a tool in computational number theory to finding widespread application in algorithms in all areas of computer science. Two practical benefits of randomization are its simplicity and speed. Deep and important computational complexity connections have been developed, from bridging the gap between discrete and continuous optimization, bypassing deterministic barriers in online settings, summarizing massive data in polylogarithmic space, probabilistically checkable proofs, privacy enhancing techniques, modeling the web and other large networks, and sparsifying and compressing complicated combinatorial structures such as graphs. Randomization is an essential key ingredient in the algorithmic breakthroughs today and in the future. This course presents the basic concepts in the design and analysis of randomized algorithms and shows how to apply them to algorithms for a wide range of problems. The course covers a broad range of problems benefitting from randomized computation including data structures, graph algorithms, online algorithms, geometric algorithms, streaming algorithms, derandomization techniques, and tools for probabilistic analysis of algorithms.
3.000 Credit hours

Syllabus Available
Levels: Undergraduate, Graduate, Professional
Schedule Types: Distance Learning, Lecture

Offered By: College of Science
Department: Computer Science

Course Attributes:
Upper Division

May be offered at any of the following campuses:     
      West Lafayette

Learning Outcomes: 1. Describe the main principles underlying the design and analysis of a randomized algorithm. 2. Explain concepts of randomized algorithms used in specific domains; e.g., graph-theory, number theory, and linear algebra problems. 3. Apply measure concentration results from probability theory to analyze a given randomized algorithm. 4. Determine the running times, failure probabilities, and accuracy guarantees of a randomized algorithm. 5. Apply learned design techniques and analysis tools to design and analyze new randomized algorithms. 6. Explain material from published research in the area of randomized algorithms using field-specific language.

Must be enrolled in one of the following Programs:     
      Computer Science-PHD
      Computer Science-MS

Short Title: Randomized Algorithms

Course Configurations:

Configuration 1: 3.0 Credits
Schedule Type Weekly Contact Hours Instructional Credit Distribution
Lecture 3 3.0
Configuration 2: 3.0 Credits
Schedule Type Weekly Contact Hours Instructional Credit Distribution
Distance Learning 0 3.0

Transparent Image
Skip to top of page
Release: 8.7.2