[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 04:37:06 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

Design Techniques: Introduction

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

Example, edit distance

. . . continued.   D[,] & U[,] (D's contours) are equivalent, i.e. alternative representations

NB. Ukkonen's alg' is not examinable, although the design ideas are.

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

Iterate over diagonal `dg' within iterating over cost `c'.   NB. | dg | <= c.   Watch out for boundary conditions. Edit distance = min' c such that U[ |S1| - |S2|,  c ] = |S1|

Complexity of Ukkonen's algorithm

Space

Time

where n is string length, d is edit distance.   Because [________________].

A Balanced Outlook

Example: Indexed sequential file
I1| I2| I3| ... Im|
  |   |   |       |
  |   |   |       |
  |   |   |       ---------------------|
  |   |   |                            |
  |   |   -----------|                 |
  |   |              |                 |
  |   -----|         |                 |
  |        |         |                 |
  |        |         |                 |
  v        v         v                 v
  e1 e2 e3 ....  ......   .....        en

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

differentiate w.r.t. m :

set to zero to find minimum time:

index size and block size should be equal.

Balance in Divide and Conquer

©
L
.
A
l
l
i
s
o
n

Greed is Good (sometimes):

Sometimes gives optimal solution, e.g.

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) = adnd + ad-1nd-1 + . . . + . . . a0 then:

NB. Must cover a large range of `n'.   e.g. 1000*n exceeds n2 unless [__________].

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

NB. Must cover a large range of `n'. e.g. . . .
(e.g. an algorithm believed O(d**3)-time)
3-string edit distance by Powell 1999 in the style of Ukkonen

Design Techniques:   Summary

These are general principles; they have exceptions!

Prepare: Exam.
 There are old exam papers under "past years" on the unit's [home-page].
© L.Allison, Sunday, 28-Nov-2021 04:37:06 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/24design.shtml
Computer Science, Software Engineering, Science (Computer Science).