1. Home
  2. Material Detail: 6.856J Randomized Algorithms | Electrical Engineering and Computer Science

Material Detail

6.856J Randomized Algorithms | Electrical Engineering and Computer Science

6.856J Randomized Algorithms | Electrical Engineering and Computer Science

This course examines how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, and Markov chains. Topics covered include: randomized computation; data structures (hash tables, skip lists); graph algorithms (minimum spanning trees, shortest paths, minimum cuts); geometric algorithms (convex hulls, linear programming in fixed or arbitrary dimension); approximate counting; parallel algorithms; online algorithms; derandomization techniques; and tools for probabilistic analysis of algorithms.
Keywords:
parallel algorithms, tail inequalities, symmetry breaking, arbitrary dimension, basic probability theory, efficient in time and space, conditional expectation, online algorithms, game-theoretic techniques, combinatorial optimization, estimation, geometric algorithms, geometry, shortest paths, occupancy problems, 6.856J, derandomization techniques, randomized complexity classes, searching, parallel and distributed algorithm, algorithms, parallel and ditributed algorithm, convex hulls, moment inequalities, linear programming, Markov chains, probabilistic analysis, simplicity, computational problems, limited independence, randomization, design, Algorithms and Data Structures, parallel and distributed algorithms, data structures, computational number theory, graph algorithms, probability amplification, skip lists, random selection of witnesses, random walks, approximation, minimum spanning trees, sampling, coupon collection, counting problems, application, 6.856, distributed algorithms, Computation, randomized computational models, 18.416J, probabilistic method, approximate counting, hash tables, Chernoff bound, Randomized Algorithms, random sampling, Chebyshev, speed, sorting, optimization, minimum cuts, 18.416, algebraic techniques, fixed dimension
Disciplines:
Go to Material 
Bookmark / Add to Course ePortfolio
Create a Learning Exercise
Add Accessibility Information
Rate
Add a Comment

Quality

  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material

Material Type:
Online Course
Date Added to MERLOT:
May 12, 2016
Date Modified in MERLOT:
May 12, 2016
Author:
Unknown (Know the author?)
Submitter:
Barbra Bied Sperling
Hispanic Serving Institution
Primary Audience:
Graduate School
Technical Format:
Website
Mobile Compatibility:
Not specified at this time
Language:
English
Cost Involved:
No
Source Code Available:
No
Accessibility Information Available:
Unknown
Creative Commons:
Creative Commons License
This work is licensed under a Attribution-NonCommercial-ShareAlike 3.0 United States

Browse...

Disciplines with similar materials as 6.856J Randomized Algorithms | Electrical Engineering and Computer Science
People who viewed this also viewed
Other materials like 6.856J Randomized Algorithms | Electrical Engineering and Computer Science

Comments

Log in to participate in the discussions or sign up if you are not already a MERLOT member.