Design Techniques: Introduction

Here, some strategies to (try to) improve and analyse an algorithm:

• Do not repeat work.
  
  
• Do only what is necessary
  • e.g. Kruskal's MST alg' needs "short" edges 1st, so use a priority Q rather than sorting all edges - improves constant.
  
  
• Try alternative representations of data & of data structures.
  
  
• "Balance" work.

Example, edit distance

• Holding partial results in D[ , ] matrix gives the O(n² )-time^[*]  dynamic programming algorithm.
  
  
• Can do better, e.g.
  
  
  • O( n . d )-time worst-case,   O( n + d² )-time average-case
    
    
  • where d = distance(string1, string2)
    
    
  • Ukkonen (1983)   and Miller & Myers (1988)   see Bib' if interested
    
    
  • Very fast when [___________________]
    
    
• Note that diagonals of the   D[,]   matrix are non-decreasing . . .

base case:
  U[0, 0] = 0

general case:
  U[dg, c] = max(

    U[dg+1, c-1],

    U[dg,     c-1] + 1,

    U[dg-1, c-1] + 1 ) ;

  while S1[ U[dg, c] ] = S2[ U[dg, c] - dg ] do
    U[ dg, c ] ++
  end_while

Complexity of Ukkonen's algorithm

Space

• O( d² )
  
  

Time

• Worst case:   O( n * d )
  
  
• Average case:   O( n + d² )
  
  
• Best case:   O( n ) --when strings equal
  
  

A Balanced Outlook

I1| I2| I3| ... Im|
  |   |   |       |
  |   |   |       |
  |   |   |       ---------------------|
  |   |   |                            |
  |   |   -----------|                 |
  |   |              |                 |
  |   -----|         |                 |
  |        |         |                 |
  |        |         |                 |
  v        v         v                 v
  e1 e2 e3 ....  ......   .....        en

• file of `n' element,   index of `m' elements
  
  
• How to choose m ?

Assuming that fetch and search, (a) on index and (b) on block pointed to, are proportional to size (with the same constant) :

• total time is proportional to m + n / m
  
  

differentiate w.r.t. m :

• 1 - n / m²
  
  

set to zero to find minimum time:

• n / m² = 1
  
  
• m² = n,     i.e.   m = sqrt( n )

index size and block size should be equal.

Balance in Divide and Conquer

• try to divide into two equal amounts of work
  
  
• e.g. merge-sort always O(n . log(n))-time
  
  [why____________________?]
  
  
• quick-sort, depends on estimates of median
  
  
  • good estimates => O(n . log(n))-time
    
    
  • poor estimates => O(n²)-time
    
    [why____________________?]

Greed is Good (sometimes):

• when we must make a number of choices for a complete solution
  
  
• greedy strategy is to make a "local" choice based on current information, without back-tracking.
  
  

• Dijkstra's single source shortest paths algorithm
  
  
• Prim's minimum spanning tree algorithm
  
  
• Kruskal's minimum spanning tree algorithm.
  
  

Sometimes gives a "good" solution to a (combinatorial) problem even if not guaranteed optimal (-- heuristic).

Estimating Complexity

When complexity is hard to analyse, can do empirical tests.

If T(n) = a_dn^d + a_d-1n^d-1 + . . . + . . . a₀ then:

• log( T(n) ) ~ log( a . n^d ),   as n--->∞
  
  

  lecturer: plot log(T(n)) v. log(n); class: take notes

• = log(a) + d . log( n )
  
  
• the intercept is [________]
  
  
• the slope is [________]
  
  

. . . estimating complexity.   If you believe or suspect that T(n) is THETA(f(n)) then:

• time, count, instrument, and . . .
  
  
• plot T(n)/f(n) v. n as n--->∞
  
  
• ratio can
  1. ---> c     --T(n) is [__________]
     
     
  2. ---> 0     --T(n) is [__________]
     
     
  3. ---> ∞     --T(n) is [__________]
     
     
  4. oscillate.     Also see Weiss p17.

Design Techniques:   Summary

• Don't repeat work (store for re-use).
  
  
• Look for alternative representations.
  
  
• Balance work in sub-tasks.
  
  
• Try known Paradigms, i.e. general problem solving strategies, e.g.
  • divide and conquer,
  • dynamic programming,
  • greedy strategy.

These are general principles; they have exceptions!