Lecture Notes for Advanced Programming I

26 January 2006 • Programming Economics

Outline

• Algorithms and Programs

  • Algorithm Analysis

  • Measuring Algorithm Performance

  • Estimated Performance Analysis

• Asymptotic Estimates

• A Behavior Hierarchy

• Structural Analysis

  • Statements

  • Statement Sequence

  • Loops

  • If Statements

  • Subroutines

A Program

string read

while getline(cin, str)
  read += str

for i = 0 to read.size()
  if read[i] == '<'
    // process tag

• Read in a string, then process all tags.

Another Program

string read

while getline(cin, str)
  read += str
  for i = 0 to read.size()
    if read[i] == '<'
      // process tag
      read[i] = ' '

• Likewise: read in a string, then process all tags.

• Which program is better?

Making Choices

• There are lots of data structures and algorithms to choose from.

  • There are lots of data structures and algorithms of the same kind.

• How do you decide among them?

Algorithms and Programs

• Programs come from algorithms.

  • Algorithms are abstract programs.

• Algorithms are easier to work with than are programs.

  • Algorithms are less detailed than programs.

  • Focus on the solution, not the code.

• Good programs come from good algorithms.

  • Good programs never come from bad algorithms.

Algorithm Analysis

• There are many algorithms, all different.

• Which algorithm are suitable?

  • It depends on your criteria.

  • Memory use, speed, message count, ...

• Start with execution time.

  • Performance is related to other criteria.

    • It takes time to use a resource.

• Performance can be measured or estimated.

Measuring Performance

• Measure execution time.

• It's a definitive measure.

• Algorithms don't execute; they're not code.

  • It requires implementing the algorithm.

• Measurements are context dependent.

  • Determining context accurately is difficult.

• Comparing results is hard.

  • Contexts must match to be meaningful.

Estimating Performance

• If you don't know, guess (or estimate).

  • Ignore the details, go for the big picture.

  • Estimating is simpler than measuring.

• Estimates are more comparable then are measurements.

  • Estimating uses minimal context.

• Estimates are more durable than are measurements.

  • Not tied to hardware or software technology.

• Skillful professionals estimate well.

  • Estimation is a skill to develop.

Modeling Algorithms

• Model the algorithm as a function f(n).

  • f(n) is the estimated algorithm behavior for an input of size n.

  • What can n represent?

    • Whatever's important: bits, lines, records.

  • What can f(n) represent?

    • Whatever's important: behavior in time or space, messages, errors, dollars.

• Algorithm details are reduced to a function.

• Understand what the input and output represent.

Sorting Model Example

• Model a sorting algorithm with the function f(n) where

  • n is the number of elements being sorted.

  • f(n) is the time it takes to sort n elements.

Database Model Example

• Model a distributed-database algorithm with the function f(n) where

  • n is the number of machines over which the database is distributed.

  • f(n) is the number of messages it takes to perform a transaction.

Estimating Functions

• After turning an algorithm into f(n), estimate f(n)'s behavior.

  • There are many ways to estimate f(n)'s behavior.

• An upper bound on f(n)'s behavior is useful.

  • It represents potential worst-case behavior.

  • Other bounds are possible, but harder to find.

Upper Bounds

• Suppose that, for most values of n, f(n) ≤ g(n).

  • g(n) is known as an upper bound to f(n).

• It's an asymptotic estimate because n grows without bound.

• An alternative representation for f(n)'s upper bound is O(g)

  • That is, f(n) = O(g).

• This is only part of the story; for full details, attend CS 512.

Asymptotic Estimate Properties

• Larger estimates swallow up smaller estimates.

  • O(f) + O(g) is O(max(f, g)).

• The product of estimates is the estimate of the product.

  • O(f)*O(g) = O(fg).

Tight Estimates

• Suppose f = O(g) and f = O(h).

  • If g = O(h), then g is a tighter estimate of f than is h.

    

• The tighter of two estimates is the better one.

A Behavior Hierarchy

• A hierarchy of function behavior.

  Constant	O(1)	array index
  Log	O(log n)	binary search
  Linear	O(n)	linear search
  Log-linear	O(n log n)	heapsort
  Quadratic, square	O(n2)	bubble sort

• Higher in the hierarchy is better (asymptotically faster).

Constant Behavior

Logarithmic Behavior

• This is repeated division behavior.

Linear Behavior

• This is "touch every element" behavior.

Log-Linear Behavior

• This is sorting behavior.

• Repeatedly divide for every element.

Quadratic Behavior

• This is double loop behavior.

A Family Portrait

• Let n = 100.

  f f(n) C C log n 6.6 n 100 n log n 664.4 n2 10,000		Improving asymptotic behavior is important. Move to the next lowest level of asymptotic behavior.

• Don't fiddle with the code, fiddle with the algorithm.

Structural Analysis

• Algorithms have a regular structure.

  • Statements, sequences, loops, and choice.

• Use program structure to derive asymptotic estimates.

  • Assign behavior to smaller units.

  • Combine units following algorithm structure to find behavior of larger units.

  • Repeat until the whole algorithm's been combined into a single estimate.

A Running Example

• Bubble sort.

  i = 0
  while i < n
    j = i + 1
    while j < n
      if a[i] > a[h]
        swap(a[i], a[j])
      j++
    i++
  

Statements

• Usually O(1), but know your data structures.

• Estimate the simple statements.

  i = 0 while i < n j = i + 1 while j < n if a[i] > a[h] swap(a[i], a[j]) j++ i++

  O(1) while i < n O(1) while j < n if a[i] > a[h] O(1) O(1) O(1)

if statement

• if b s1 else s2

• Execute either s₁ or s₂, but which one?

  • Because we're overestimating, use the larger of the estimates.

• Don't forget b's cost.

  • O(f_b) + O(max(f₁, f₂))

Example if Estimates

• To continue:

  O(1) while i < n O(1) while j < n if a[i] > a[h] O(1) O(1) O(1)

  O(1) while i < n O(1) while j < n O(1) + O(1) = O(1) O(1) O(1)

Statement Sequence

• s₁ ; s₂

• s₁ is O(f), s₂ is O(g), so s₁; s₂ is O(f) + O(g)

• What is O(f) + O(g)?

  • Take the larger of the two.

    • O(f) + O(g) is O(max(f, g))

Example Sequence Estimates

• Continued:

  O(1) while i < n O(1) while j < n O(1) O(1) O(1)

  O(1) while i < n O(1) while j < n O(1) + O(1) = O(max(1, 1)) = O(1) O(1)

Loops

• while b do s

• s has asymptotic estimate O(f).

• s gets executed some number of times.

  • Asymptotically bound the number of times as O(g).

• The estimate is O(f)*O(g).

  • O(f)*O(g) is equivalent to O(fg)

Loop Overhead

• The loop itself does constant work per iteration.

  • Ignore it.

  • This includes the cost of evaluating b.

• An implicit, and occasionally troublesome, assumption.

  • But, it allows us to deal with for loops in the same way.

Loop Estimate Example

• Continued:

  O(1) while i < n O(1) while j < n O(1) O(1)

  O(1) while i < n O(1) O(n)*(O(1) + O(1)) = O(n)*O(max(1, 1)) = O(n)*O(1) = O(n*1) = O(n) O(1)

Finishing Up.

• Estimate the loop-body statement sequence.

  O(1) while i < n O(1) O(n) O(1)

  O(1) while i < n O(1) + O(n) + O(1) = O(max(1, n, 1) = O(n)

Finishing Up..

• Estimate the loop.

  O(1) while i < n O(n)

  O(1) O(n)*O(n) = O(n*n) = O(n2)

Finishing Up...

• Estimate the statement sequence.

  O(1) O(n2)

  O(1) + O(n2) = O(max(1, n2)) = O(n2)

• Done: O(n²)

• The structure of the algorithm determines the next step.

Subroutines

• Non-recursive subroutines are treated like a statement.

  • Guess at or know the estimate for a call.

  • swap(a, b) = O(1).

• Recursive calls are tougher.

  • Solved with recurrence relations.

  • Later for that.

Things to Watch

• Keep an eye on the constants.

• Estimate the right things.

• Look at the right inputs.

Estimate Inputs

• Look at the right inputs.

  • Focus on what's driving the algorithm.

  • Worrying about execution time on communication-bound computations.

Estimate Outputs

• Estimate the right things.

  • What's important: an expensive algorithm, or the number of times it's called?

Understand the Estimate

• Keep an eye on the constants.

  • Asymptotically identical algorithms may be (usually are) different.

  • For small n, constants are more important - linear search is usually good enough.

Points to Remember

• Develop algorithms, not programs.

• Use performance criteria to select algorithms.

• Use asymptotic estimates for performance.

• Estimate performance using structural analysis.

• Understand what the estimates are saying.

This page last modified on 27 January 2006.

This work is covered by a Creative Commons License.