Dependency parsing has played a pivotal role in NLP over the last few decades, and non- projective, graph-based dependency parsers have become a dominant approach for this task in the 21st century. While much research has focused on advancing log-linear parameterisations and neural network development, there has been a paucity of research addressing the fundamental algorithms that allow us to use graph-based dependency parsers. This thesis examines algorithms used in four stages of non-projective, graph-based dependency parsers: inference, sampling, decoding, and significance testing. The thesis will guide the reader through a series of novel extensions to existing algorithms, as well as the original develop- ment of new algorithms concerning these four processes in the dependency parsing galaxy. We provide a framework for efficiently evaluating a family of expectations that can be used for inference, such as risk, the Shannon entropy, the KL divergence, inter alia, by capitalising on the connection between gradients and expectations. We further introduce two fast methods for sampling trees from graph theory, and extend them to satisfy a common constraint in dependency parsing schemes that only allows one edge to emanate from the root. Additionally, we contribute the first sampling-without-replacement algorithm for graph-based dependency parsers. We also analyse, simplify, and extend algorithms for decoding the one-best and K-best trees and discuss existing algorithms and new modifications to enable root constrained decoding. Finally, we propose a novel algorithm to perform an exact paired permutation significance tests when comparing the performance of two parsers. Not only is this the first exact algorithm to perform this test, but it is also faster than current approximation strategies. This thesis offers insights into efficient algorithms in different aspects of dependency parsing. We shed light on core algorithms from the graph theory literature and develop these algorithms so that they execute more efficiently and satisfy necessary constraints in dependency parsing. This hitchhiker’s guide to dependency parsing is accompanied by publicly available code that can be easily integrated into modern parsers, enabling more efficient parsers in future research.