Partitioning algorithms是用来解决复杂且大量规模的计算问题,就像松散grid的四元airfoil.(影像乃取材自NASA的网站:http://www.nasa.gov.) Partitioning algorithms are used to solve complex large scale computational problems, as shown in this unstructured grid for a four element airfoil. (Image is taken from NASA's Web site: http://www.nasa.gov.)
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.
