Skip to content

Projects from "Algorithms", Part I and Part II, by Princeton University

License

Notifications You must be signed in to change notification settings

aziqikang/algs4

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

14 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Algorithms - Princeton University

This repository contains my solutions for the online courses "Algorithms, Part I" and "Algorithms, Part II" from Princeton University.

Coursera:

Algorithms, Part I

Algorithms, Part II

Text:

Algorithms, 4th ed., by Robert Sedgewick and Kevin Wayne

Projects

Part I, Week 1: Percolation

Percolation

Project Specification

"Percolation" calculates whether we can traverse through adjacent open sites to get from the top of the lattice to the bottom. As an analogy, I like to think of water being poured over a lattice containing sites that are either open (holes!) or closed. The question now is whether the water percolate through the lattice...

image

Calculating percolation using the Union Find Data Structure

The percolation problem implements the Union-Find, or Disjoint-Set, data structure, which simulates set partitioning. Union Find uses an array id[] to append an id to each index; if the two elements corresponding to indexes a and b are such that id[a] = id[b], then the two elements are in the same equivalence class.

The time complexity of normal Union-Find, which I found most intuitive, is O(n). With optimizations, Sedgewick and Wayne's WeightedQuickUnionUF takes O(n) to construct and O(log n) to merge equivalence classes and find the representative element of a set.

Estimating the value of the percolation threshold using a Monte Carlo simulation

Finally, the "Percolation" class is used to empirically estimate the value of the percolation threshold for a square lattice. By running a Monte Carlo simulation and randomly opening sites, as shown below, we experimentally estimate when a lattice transitions from non-percolating to percolating state.

image

Notes:

When I was working on this project two years ago, I ran into some issues (now fixed!) with backwashing.

In cases where a Percolation object does percolate, some sites that aren't connected appear to be connected because the we union() sites at the top of the lattice to sites at the bottom of the lattice as a part of implementing Union-Find.

For example, running PercolationVisualizer.java on input10.txt results in the solution to the right rather than the solution to the left (this is mentioned in the FAQ!).

image

The solution I implemented simply uses two Union-Find objects. Doing this seems to satisfy the Coursera autograder, but it's also pretty costly in terms of memory. I'd be interested in hearing about any other solutions out there!

About

Projects from "Algorithms", Part I and Part II, by Princeton University

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages