Union Find

• We learn about the Dynamic Connectivity Problem.

• We learn about the union-find data type.

• Implementations of Union Find Data type.

  • Quick Find

  • Quick Union

  • Weighted Quick Union

  • Weighted Quick Union with Path Compression.

• Apply Union Find Data type for the Percolation Problem from Physical Chemistry.

Lecture Slides

• https://www.coursera.org/learn/algorithms-part1/supplement/bcelg/lecture-slides

Programming Assignment

Percolation

Given a composite systems comprised of randomly distributed insulating and metallic materials: what fraction of the materials need to be metallic so that the composite system is an electrical conductor? Given a porous landscape with water on the surface (or oil below), under what conditions will the water be able to drain through to the bottom (or the oil to gush through to the surface)? Scientists have defined an abstract process known as percolation to model such situations.

• https://www.coursera.org/learn/algorithms-part1/programming/Lhp5z/percolation

• Problem Statement: http://coursera.cs.princeton.edu/algs4/assignments/percolation.html

Programming assignment gives an opportunity to apply the concepts of Union-Find to a fundamental problem in physical chemistry.

It is the first of many examples where a good algorithm, weighted quick union, makes the difference between being able to efficiently solve a problem and not being able to address it at all.