Lecture Notes for CS 512, Algorithm Design

7 October 1999

These are provisional lecture notes, expect changes.

  1. going from algorithm to order notation - many ways

    1. algorithm, mathematical model (that is, function), order approximation - knuth

      1. subsidiary model - computation model; ram, mix

    2. algorithm, order notation - structural analysis

  2. structural analysis - algorithm structure

    1. assign behavior to smaller units, then combine units following algorithm structure to find behavior of larger units.

    2. statements

      1. usually O(1), but know your data structures - eg a[i] vs. put_queue(q, i) vs. put_priority_queue(q, i)

    3. statement sequence - s1 ; s2

      1. s1 is O(f), s2 is O(g), so s1 ; s2 is O(f) + O(g)

      2. but what is O(f) + O(g)?

        1. treat O(f) as a set of functions, pick a representative function and apply the definition of big-oh.

        2. plus, max, constant

        3. example: i <- 1 ; heapify(h, i)

    4. loops - do b s od

      1. s gets executed some number of times - asymptotically bound the number of times

      2. O(f)*O(g) - what is that?

      3. implicit, and occasionally troublesome, assumption - the loop itself does constant work per iteration.

    5. if statement - if b s1 or b s2 fi

  3. fine points

    1. what is the input - what's n?

    2. making the assumptions - best, average, worst

    3. what's the output - what are we measuring; memory accesses, comparisons, swaps and so on

This page last modified on 7 October 1999.