[Subject home],
[FAQ],
[progress],
Bib',
Alg's,
C ,
Java- L.A.,
Wednesday, 08-May-2024 14:05:28 AEST 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:
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.
Holding partial results in D[ , ] matrix gives the
O(n2 )-time[*]
dynamic programming algorithm.
Can do better, e.g.
O( n . d )-time worst-case,
O( n + d2 )-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 . . .
. . . 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
O( d2 )
Time
Worst case: O( n * d )
Average case: O( n + d2 )
Best case: O( n ) --when strings equal
where n is string length, d is edit distance.
Because [________________].