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