# 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

• Data-structure-driven

• Direct constructions

• Solver
• Transformer
• Sequence of steps
• Deconstruction heuristics

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

• Data structure transformations
• Parallel representations

• 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
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