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.

• http://c2.com

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.

        PROBLEM LEFTMOST INDEX OF MINIMUM

        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)

        ALGORITHM TWO-PASS LEFTMOST INDEX OF MINIMUM

        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