[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 05:15:36 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.

## Hirschberg:   Introduction

• Saw string edit distance and alignment in

• O(n2) -time and -space

• But Hirschberg showed how to do it in

• O(n2)-time and

• just O(n)-space

• using divide and conquer . . .

### Basic Idea for aligning 2 strings, s1[ ] and s2[ ]

• cut s1[ ] in half at mid-point,   s1 = s1a ++ s1b

• must be some s2a and s2b s.t.

1. s2 = s2a ++ s2b   and

2. D( s1, s2 ) = D( s1a, s2a ) + D( s1b, s2b )

• find this cut-point in distance matrix

• solve the 2 smaller problems recursively
example . . .
 - A C G T A C G T A C G T fwd - 0 1 2 ... A 1 0 C 2 0 1 T ... 1 A 1 C 1 C ... 2 ...
NB. Have only shown "important" values - L.Allison 2000.

### General Case,   | s1 | > 1

• s1a = 1st half of s1,   s1b = 2nd half,   s1 = s1a ++ s1b

• run DPA forward on s1a and all of s2

• run DPA backwards in s1b and all of s2

• 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 [______________]
 s2a s2b s1a s1a : s2a s1b s1b : s2b
NB. | s1a | = | s1b | +/- 1
continued...
. . . next level in recursion   (1/4 area) . . .
 s2aa s2ab s2ba s2bb s1aa s1aa : s2aa s1ab s1ab : s2ab s1ba s1ba : s2ba s1bb s1bb : s2bb
--L.Allison,2000.

## Hirschberg: Summary

• saw another example of divide and conquer, c.f.
• merge sort
• quick sort

• Here we traded time ( x 2 ) for space O( n2 ) ----> O( n )

• [lecturer: use demo; class: take notes!]

### Prepare

• ( Dictionary | Lookup ) - Tables
© L.Allison, Sunday, 28-Nov-2021 05:15:36 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/08hirsch.shtml
Computer Science, Software Engineering, Science (Computer Science).