## 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.

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