Algorithms

Introduction

The previous parts of this guide describe data structures: how to store items and the relations between them. This part is about algorithms: procedures that compute something from a structure, such as a sorted order, a shortest path or a posterior probability.

In sds the two are kept strictly apart. Structures live in sds.linear, sds.tree, sds.graph, sds.advanced and sds.probabilistic; algorithms live in sds.algorithms and receive the structure they work on as a parameter.

        graph LR
    subgraph "Structures (store)"
    L[sds.linear]
    T[sds.tree]
    G[sds.graph]
    P[sds.probabilistic]
    end

    subgraph "sds.algorithms (compute)"
    S[sorting]
    TA[tree_algorithms]
    GA[graph_algorithms]
    PA[probabilistic_algorithms]
    end

    L --> S
    T --> TA
    G --> GA
    P --> PA

    style S fill:#3498db,color:#fff
    style TA fill:#3498db,color:#fff
    style GA fill:#3498db,color:#fff
    style PA fill:#3498db,color:#fff
    

Note

Why separate them? A structure that also implemented every algorithm on it would grow without bound, and each algorithm would be tied to one representation. As free functions, an algorithm is written once against an abstract interface (AbstractGraph, AbstractBinaryTree, AbstractGraphicalModel) and runs unchanged on every structure implementing it: dijkstra() works on both WeightedGraph and WeightedDirectedGraph.

Measuring Algorithms

Algorithms are compared by how their cost grows with the size \(n\) of their input, ignoring constant factors. The three standard notations are:

\[ \begin{align}\begin{aligned}f(n) = O(g(n)) \iff \exists c > 0,\ n_0,\ \forall n \ge n_0:\ f(n) \le c \, g(n)\\f(n) = \Omega(g(n)) \iff \exists c > 0,\ n_0,\ \forall n \ge n_0:\ f(n) \ge c \, g(n)\\f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))\end{aligned}\end{align} \]

\(O\) is an upper bound, \(\Omega\) a lower bound, \(\Theta\) a tight bound. For graphs, costs are expressed in the number of vertices \(V\) and edges \(E\); for trees, in the number of nodes \(n\) and the height \(h\).

Growth rates met in this guide

Growth	Name	Example
\(O(\log n)\)	logarithmic	search in a balanced tree
\(O(n)\)	linear	tree traversal, BFS, DFS
\(O(n \log n)\)	linearithmic	merge sort, Kruskal
\(O(n^2)\)	quadratic	quicksort worst case
\(O(d^w)\)	exponential in a parameter	variable elimination (\(w\) = induced width)

Contents

• Design Paradigms
  • Introduction
  • Divide and Conquer
  • Greedy Algorithms
  • Dynamic Programming
  • Summary
  • References
• Sorting
  • Introduction
  • The Lower Bound
  • Merge Sort
  • Quicksort
  • Choosing a Sort
  • References
• Tree Algorithms
  • Introduction
  • The Four Traversals
  • Balance
  • References
• Graph Algorithms
  • Introduction
  • Graph Traversals
  • Shortest Paths: Dijkstra
  • Minimum Spanning Trees: Kruskal
  • Summary
  • References
• Probabilistic Inference
  • Introduction
  • Running Example: the Alarm Network
  • Variable Elimination
  • Belief Propagation
  • Hidden Markov Models
  • Summary
  • References

Which page for which question

Question	Page
How are algorithms designed and proved?	Design Paradigms
How do I sort, and which sort should I choose?	Sorting
How do I walk or rebalance a binary tree?	Tree Algorithms
Shortest paths, spanning trees, reachability?	Graph Algorithms
Posterior probabilities, likelihoods, decoding?	Probabilistic Inference

For signatures and parameters, see the Algorithms (sds.algorithms).