The interactions between adsorbates on a surface lead to coverage dependent properties such as adsorption energies and ultimately to different phase diagrams on different metal surfaces. Density functional theory can be used to calculate these interactions, but in using these calculations to determine the phase diagram there is always a concern that a relevant configuration was missed. We will discuss some algorithms we have used in conjunction with DFT to ensure that no configurations are missed in the construction of adsorbate phase diagrams. Finally, we will discuss correlations in the coverage dependence of the adsorption energy of oxygen on different close packed noble metal surfaces.