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.

- e.g. Kruskal's
MST
alg' needs "short" edges 1st, so
use a
- Try alternative representations
of data & of data structures.

- "Balance" work.

- Holding partial results in D[ , ] matrix gives the
O(n
^{2})-time^{[*]}dynamic programming algorithm.

- Can do better, e.g.

O( n . d )-time worst-case ,O( n + d ^{2})-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 . . .

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

- O( d
^{2})

- Worst case: O( n * d )

- Average case: O( n + d
^{2})

- Best case: O( n ) --when strings equal

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,

- total time is proportional to
m + n / m

differentiate w.r.t. m :

- 1 - n / m
^{2}

set to zero to find minimum time:

- n / m
^{2}= 1

- m
^{2}= n,i.e. m = sqrt( n )

index size and block size should be *equal*.

- 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
^{2})-time

[why____________________?]

- good estimates => O(n . log(n))-time

© L . A l l i s o n |

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

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

If T(n) =
a_{d}n^{d} +
a_{d-1}n^{d-1} +
. . . + . . . a_{0} 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
- ---> c --T(n) is [__________]

- ---> 0 --T(n) is [__________]

- ---> ∞ --T(n) is [__________]

- oscillate.
Also see Weiss p17 .

- ---> c --T(n) is [__________]

(e.g. an algorithm believed O(d**3)-time)

- 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!

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