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

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

            To sort s:
                for each permutation t of s
                    if t satisifies the definition of sorted
                        return t

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


  • 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