[Subject home],
[FAQ],
[progress],
Bib',
Alg's,
C ,
Java- L.A.,
Friday, 03-May-2024 09:13:49 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.
using final "rows",
find optimal cut,
s2 = s2a ++ s2b
recursively solve
s1a : s2a and
s1b : s2b
Base Case
| s1 | = 0, or
| s1 | = 1 -- both easy
[lecturer: briefly; class: study at home!]
function Hirschberg(int p1, int p2, int q1, int q2)
/* align s1[p1..p2) with s2[q1..q2). Strings are global! */
{ int mid, i, s2mid, sum best;
if( p2 <= p1 )
a base case ... s1 is empty, match '' : s2
else if( q2 <= q1 )
a base case ... s2 is empty, match s1 : ''
else if( p2-1 == p1 ) /* s1 is 1 character & s2 is not empty */
a base case ... find best match for s1[p1] in s2[]
else /* p2>p1+1, s1 has at least 2 chars, divide s1 & conquer */
{ mid = (p1+p2) / 2;
fwdDPA(p1, mid, q1, q2, fwd); /* fwd[] is one row */
revDPA(mid, p2, q1, q2, rev); /* rev[] is one row */
s2mid = q1;
best = huge_number;
for( i=q1; i<=q2; i++ ) /* seek cheapest split of s2 */
{ sum = fwd[mid % 2][i] + rev[mid % 2][i];
if( sum < best ) { best=sum; s2mid=i; }
}
Hirschberg(p1,mid, q1,s2mid); /* divide & */
Hirschberg(mid,p2, s2mid,q2); /* conquer! */
}
}/*align*/
Space Complexity
Can compute row ``i'' of D[ , ] from row ``i-1''
So Hirschberg uses just O( | s2 | ) - space
Time Complexity
is O( n2 × ( 1 + 1/2 + 1/4 + . . . )),
is O( n2 )
because [______________]