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

        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