Algorithm Design Patterns

Algorithm Design Patterns

Bart Massey

Algorithm Design Patterns

  • Just as there are design patterns for programs, there are design patterns for algorithms.

  • Today we will discuss a bunch of rules, tricks and heuristics for finding efficient algorithms.


General Classes of AP

  • Follow the question

  • Data-structure-driven

  • Direct constructions

    • Solver
    • Transformer
    • Sequence of steps
  • Deconstruction heuristics

    • Top-down
    • Bottom-up
    • Recursive
  • Complicated compositions

    • Data structure transformations
    • Parallel representations

Follow the Question

  • Sometimes the question answers itself. For example, find the index of the leftmost minimum element in an array.

        Given: An array a of total-ordered elements.

        Find: The leftmost index i in a s.t. a[i] is
              minimal among all elements of a (that is,
              for all e in a, e[min] <= e)


        To find the minimum value in an array a:
            e[min] <- a[0]
            for e in a
                if e[min] > e
                    e[min] = e

        To find the leftmost index of a minimum value of zero-based array a:
            e[min] <- minimum value in a
            for i in 0..|a|-1
                if a[i] = e[min]
                    return i

Data Structure Driven

  • Sometimes once you've picked a data structure, the problem solves itself. For example, sort using a heap.

Direct constructions

  • Sometimes you need to just solve the problem. For example, Gaussian elimination.

  • Sometimes you need to just transform an input to an output. For example, given a sequence of sequences of numbers, emit the sequence of averages.

  • Sometimes you just need to take a bunch of steps in a row. For example, given an array of numbers, find adjacent elements of the array with median distance.

Top-down Algorithms

  • Often described as "divide-and-conquer": a workhorse.
    • Not always as useful as you might think: for example, D&C find-min
    • Usually recursive

Bottom-up Algorithms

  • Build up sub-solutions
    • Dynamic Programming
    • Various recursive algorithms, for example on trees

Considerations For Recursion

  • Must have a base case and an inductive case

  • Sometimes iterating is just simpler

  • Need measure of forward progress

Complicated Compositions

  • Sometimes change in representation is the point

  • Sometimes you need to work in parallel representations, for example adjacency list and adjacency matrix of graph

The Well-Known

  • Certain data structures and algorithms come up over and over again.
    • Sequences and Sets, Graphs, Priority Queues, etc
    • Sorting, Indexed Searching, Compostion, Decomposition, etc
Last modified: Tuesday, 15 April 2014, 3:48 PM