Monte Carlo methods provide a powerful computational tool with a vast range of scientific applications, and I will apply them to real-world problems such as urban traffic flow. However, current methods can become hopelessly inefficient when applied to complex physical phenomena such as phase transitions. I will develop novel Monte Carlo methods, for a range of models in statistical mechanics, which as radically more efficient than current methods. Indeed, many of these novel methods exhibit critical speeding-up; a remarkable phenomenon, which I co-discovered, in which a Monte Carlo algorithm's efficiency actually increases near a phase transition. In addition, I will prove the correctness of these algorithms using rigorous mathematics.