## Reading and Writing Algorithms

# Reading and Writing Algorithms

**Bart Massey**

### Problem Solving

Algorithms

Trial-and-error

Analysis

Reference

### Problem Description

- Class, Problem, Instance
- Class: A collection of problems with something in common
- Examples: "Sorting", "Superlinear"

- Problem: A parameterized collection of instances
- Instance: Something that demands a particular answer

- Class: A collection of problems with something in common

```
SEQUENCE SORTING
Instance: A sequence s of elements drawn from a set S. A
total order q: SxS->B s.t. q is true when its arguments
are "in order".
Problem: Find a sequence t drawn from S s.t.
t in perm(s) and
forall i, j in 1..|S| . i < j => q (t[i], t[j])
ALGORITHM DUMBSORT
To sort s:
for each permutation t of s
if t satisifies the definition of sorted
return t
ALGORITHM SELECTION SORT
To sort s:
t <- empty
while s is not empty
let i be the index of a minimum element of s
append s[i] to t
delete s[i] from s
```

(Sorting is n log n)

- A sequence of n elements has n! combinations
- n! is in O(n**n)
- lg n**n = n lg n

Radix Sort (Bucket Sort) "is O(n)"

### Pseudocode

Right level of detail

Too much detail:

- Doesn't communicate
- Hard to write
- Hard to analyze

Last modified: Tuesday, 15 April 2014, 3:43 PM