4 Software implementation
This chapter covers
- Data structures: linear, nonlinear, and probabilistic
- Problem-solving paradigms: complete search, greedy, divide and conquer, and dynamic programming
- ML research: sampling methods and variational inference
In the previous chapters, we looked at two main camps of Bayesian inference: Markov chain Monte Carlo and variational inference. In this chapter, we review computer science concepts required for implementing algorithms from scratch. To write high-quality code, it’s important to have a good grasp of data structures and algorithm fundamentals. This chapter is designed to introduce common computational structures and problem-solving paradigms. Many of the concepts reviewed in this section are interactively visualized on the VisuAlgo website (https://visualgo.net/en).
4.1 Data structures
A data structure is a way of storing and organizing data. Data structures support several operations, such as insertion, search, deletion, and updates, and the right choice of data structure can simplify the runtime of an algorithm. Each data structure offers different performance tradeoffs. As a result, it’s important to understand how data structures work.