COMPUTER SCIENCE COMPUTER SCIENCE

S E D G E W I C K / W A Y N E S E D G E W I C K / W A Y N E
PA R T I I : A L G O R I T H M S , T H E O R Y, A N D M A C H I N E S PA R T I I : A L G O R I T H M S , T H E O R Y, A N D M A C H I N E S

11. Searching and Sorting

Computer Science

11. Sorting and • A typical client

Computer Searching
• Binary search

ScienceAn Interdisciplinary Approach

• Insertion sort
• Mergesort
Section 4.2
ROBERT SEDGEWICK
K E V I N WAY N E • Longest repeated substring
[Link]

[Link]

A typical client: Whitelist filter Search client: Whitelist filter

A blacklist is a list of entities to be rejected for service. Examples: Overdrawn account % more [Link]
Spammers public class WhiteFilter alice@home
{ bob@office
A whitelist is a list of entities to be accepted for service. Examples: Account in good standing public static int search(String key, String[] a) carl@beach
dave@boat
Friends and relatives // Search method (stay tuned).
public static void main(String[] args) % more [Link]
Whitelist filter bob@office
{
• Read a list of strings from a whitelist file. In in = new In(args[0]);
carl@beach
marvin@spam
• Read strings from StdIn and write to StdOut only String[] words = [Link](); bob@office
bob@office
those in the whitelist. while (![Link]()) mallory@spam
{ dave@boat
String key = [Link](); eve@airport
Example. Email spam filter if (search(key, words) != -1) alice@home
(message contents omitted) bob@office ✓
carl@beach ✓ [Link](key);
bob@office % java WhiteFilter [Link] < [Link]
marvin@spam } bob@office
carl@beach
alice@home bob@office ✓ bob@office
} carl@beach
whitelist bob@office StdIn bob@office ✓ StdOut bob@office
} bob@office
carl@beach mallory@spam bob@office
dave@boat
dave@boat dave@boat ✓ alice@home
dave@boat
eve@airport alice@home
...
alice@home ✓
...
3 4
Alice and Bob Strawman implementation: Sequential search (first try)

i a[i]
Sequential search
0 alice oscar?
Hey, Alice. I think I'm going to
start an Internet company.
• Check each array entry 0, 1, 2, 3, ... 1 bob
Me too. I'm thinking about for match with search string.
having 1 thousand customers next 2 carlos
month and 1 million next year.
• If match found, return index of matching string.
3 carol
• If not, return 1.
We're hoping to grow even 4 craig
faster than that. 5 dave
public static int search(String key, String[] a)
Good luck! { 6 erin
BTW, you're going to need a for (int i = 0; i < [Link]; i++) 7 eve
whitelist filter. Alice
Bob if (a[i] == key) return i;
8 frank
return -1;
Yes, I know. I'm going to a
hackathon to knock it out.
} ✘Compares references, not strings! 9 mallory
10 oscar
I'm going to take a 11 peggy
few CS courses first.
12 trent
@#$%$#@@%#!!
13 walter
14 wendy
5 6

Strawman implementation: Sequential search Mathematical analysis of whitelist filter using sequential search

i a[i] whitelist dobqi transactions xwnzb

Sequential search Model xwnzb lnuqv
0 alice oscar?
• Check each array entry 0, 1, 2, 3, ... 1 bob
• N strings on the whitelist. dqwak lnuqv
for match with search string. • cN transactions for constant c. lnuqv czpwx
2 carlos czpwx czpwx
• If match found, return index of matching string. • String length not long.
3 carol bshla dqwak
• If not, return 1. idhld idhld
4 craig
utfyw dobqi
5 dave
public static int search(String key, String[] a) hafah dobqi
Analysis
{ 6 erin tsirv tsirv
for (int i = 0; i < [Link]; i++) 7 eve
• A random search hit checks about half of the N dqwak
if (a[i].compareTo(key) == 0) return i; strings on the whitelist, on average. dobqi
8 frank
return -1;
mallory
• A random search miss checks all of the N idhld
} 9
strings on the whitelist, on average. dqwak
Match found.
10 oscar dobqi
• Expected order of growth of running time: N 2.
Return 10 11 peggy lnuqv
xwnzb
Still, this was even easier 12 trent
than I thought! idhld
13 walter
bshla
14 wendy xwnzb
7 8
Random representative inputs for searching and sorting Test client for sequential search

Generate N random strings of length L from a given alphabet Print time required for 10N searches in a whitelist of length N

public class Generator public class TestSS

{ % java Generator 10 3 abc {
bab public static int search(String key, String[] a) a-z = abcdefghijklmnopqrstuvwxyz
public static String randomString(int L, String alpha)
{ bab {
% java Generator 15 8 0123456789
char[] a = new char[L]; bbb for (int i = 0; i < [Link]; i++) % java Generator 10000 10 a-z | java TestSS
62855405
for (int i = 0; i < L; i++) cac if ( a[i].compareTo(key) == 0 ) return i; 3 seconds
83179069
{ aba return -1;
79061047
int t = [Link]([Link]()); abb }
27258805
a[i] = [Link](t); bab public static void main(String[] args) generate 10,000 print time for
54441080
} ccb { ten-letter words 100,000 searches
76592141
return new String(a); cbc String[] words = [Link](); (lowercase)
95956542
} bab int N = [Link];
19442316
public static void main(String[] args) double start = [Link]()/1000.0;
75032539
{ for (int i = 0; i < 10*N; i++)
10528640
int N = [Link](args[0]);
good chance {
of duplicates 42496398
int L = [Link](args[1]); String key = words[[Link](N)]; random successful search
34226197
String alpha = args[2]; if (search(key, words) == -1) (no output)
10320073
for (int i = 0; i < N; i++) [Link](key);
80072566
[Link](randomString(L, alpha)); }
87979201
} double now = [Link]()/1000.0;
} [Link]([Link](now-start) + " seconds");
}
% java Generator 1 60 actg not much chance }
tctatagggtcgtttgcgaagcctacacaaaagtagttgttggacaacgattgacaaaca of duplicates
9 10

Empirical tests of sequential search COMPUTER SCIENCE

S E D G E W I C K / W A Y N E
PA R T I : P R O G R A M M I N G I N J AVA
TN transactions
(seconds) TN/TN/2 per second
N

% java Generator 10000 ...

10,000 3 3,333 3 seconds
Image sources
% java Generator 20000 ... [Link]
Whitelist filter scenario 20,000 9 2,222 9 seconds
[Link]
% java Generator 40000 ...
• Whitelist of size N. 40,000 35 3.9 1,143 35 seconds

• 10N transactions. 80,000 149 4.3 536

% java Generator
149 seconds
80000 ...

... ... = 10 a-z | java TestSS

1.28 million 38,500 4 34

more than 1.28 million transactions

10.5 hours at a rate of 34 per second
and dropping

Hmmm. That doesn't

seem too good.

Validates hypothesis that order of growth is N 2 . Does NOT scale.

11 [Link]
 COMPUTER SCIENCE Binary search
S E D G E W I C K / W A Y N E
PA R T I I : A L G O R I T H M S , T H E O R Y, A N D M A C H I N E S
i a[i]
Binary search
0 alice
• Keep the array in sorted order (stay tuned).
1 bob
• Examine the middle key.
2 carlos
• If it matches, return its index.
3 carol
• If it is larger, search the half with lower indices.
11. Sorting and Searching • If it is smaller, search the half with upper indices.
4

5
craig
dave
6 erin
• A typical client public static int search(String key, String[] a) 7 eve oscar?
{
• Binary search for (int i = 0; i < [Link]; i++) 8 frank
if ( a[i].compareTo(key) == 0 ) return i;
• Insertion sort return -1;
9 mallory

Match found.
10 oscar
• Mergesort }
Return 10 11 peggy
• Longest repeated substring 12 trent
13 walter
14 wendy
[Link] 14

Binary search arithmetic Binary search: Java implementation

Notation. a[lo,hi) means a[lo], a[lo+1] ... a[hi-1] (does not include a[hi]).
public static int search(String key, String[] a)
{ return search(key, a, 0, [Link]); }
Search in a[lo,hi) mid = lo + (hi-lo)/2 Lower half: a[lo,mid) Upper half: a[mid+1,hi)
lo lo lo lo public static int search(String key, String[] a, int lo, int hi) lo
{
if (hi <= lo) return -1; mid
int mid = lo + (hi - lo) / 2;
mid mid mid int cmp = a[mid].compareTo(key); hi
mid+1 if (cmp > 0) return search(key, a, lo, mid);
else if (cmp < 0) return search(key, a, mid+1, hi);
else return mid;
}

hi hi hi hi

Tricky! Needs study... Still, this was easier than

I thought!

15 16
Recursion trace for binary search Mathematical analysis of binary search
i a[i]
Exact analysis for search miss for N = 2n 1 N n
public static int search(String key, String[] a) search("oscar") 0 alice
{ return search(key, a, 0, [Link]); } return search(... 10
0, 15); • Note that n = lg(N+1) ~ lgN. 15 4
1 bob
• Subarray size for 1st call is 2n 1.
7 3
public static int search(String key, String[] a, search("oscar", a, 0, 15) 2 carlos
int lo, int hi) mid = 7;
3 carol
• Subarray size for 2nd call is 2n 1 1. lgN
{ > "eve" 3 2
if (hi <= lo) return -1; 4 craig
• Subarray size for 3rd call is 2n 2 1.
return search(...
10 8, 15);
int mid = lo + (hi - lo) / 2;
5 dave • ... 1 1
int cmp = a[mid].compareTo(key); search("oscar", a, 8, 15)
if (cmp > 0) return search(key, a, lo, mid); mid = 11; 6 erin • Subarray size for nth call is 1.
Every search miss is a top-to-bottom path in this tree.
else if (cmp < 0) return search(key, a, mid+1, hi); < "peggy" 7 eve • Total # compares (one per call): n ~ lgN.
else return mid; return search(...
10 8, 10);
} 8 frank
search("oscar", a, 8, 11) Interested in
9 mallory Proposition. Binary search uses ~lg N compares for a search miss.
mid = 9; details? Take a
10 oscar
> "mallory" course in
return search(...
10 10, 11); 11 peggy
Proof. An (easy) exercise in discrete math. algorithms.

12 trent OK!
search("oscar", a, 10, 11)
mid = 10; 13 walter
Proposition. Binary search uses ~lg N compares for a random search hit.
== "oscar"
14 wendy
return 10; Proof. A slightly more difficult exercise in discrete math.
17 18

Empirical tests of binary search COMPUTER SCIENCE

S E D G E W I C K / W A Y N E
PA R T I : P R O G R A M M I N G I N J AVA
TN transactions
N TN/TN/2 per second % java Generator 100000 ...
Whitelist filter scenario (seconds)
1 seconds
• Whitelist of size N. 100,000 1
% java Generator 200000 ...
3 seconds
• 10N transactions. % java Generator 400000 ...
200,000 3 6 seconds
% java Generator 800000 ...
400,000 6 2 67,000 14 seconds
% java Generator 1600000 ...
800,000 14 2.35 57,000 33 seconds

1,600,000 33 2.33 48,000 ... = 10 a-z | java TestBS

a-z = abcdefghijklmnopqrstuvwxyz

10.28 million 264 2 48,000 nearly 50,000 transactions

per second, and holding

Great! But how do I get

Validates hypothesis that order of growth is NlogN. the list into sorted order at
the beginning?

Will scale.

19 [Link]
 COMPUTER SCIENCE Sorting: Rearrange N items to put them in ascending order
S E D G E W I C K / W A Y N E
PA R T I I : A L G O R I T H M S , T H E O R Y, A N D M A C H I N E S 0 wendy 0 alice
Applications
1 alice 1 bob
• Binary search
2 dave 2 carlos
• Statistics
3 walter 3 carol
• Databases
4 carlos 4 craig
• Data compression

11. Sorting and Searching

5 carol 5 dave
• Bioinformatics
6 erin 6 erin
• Computer graphics
7 oscar 7 eve
• Scientific computing
• A typical client 8 peggy 8 frank
• ...
• Binary search • [Too numerous to list]
9 trudy 9 oscar

eve peggy
• Insertion sort
10 10

11 trent 11 trent
• Mergesort 12 bob 12 trudy

• Longest repeated substring 13 craig 13 victor

14 frank 14 walter

15 victor 15 wendy
[Link] 22

Pop quiz 0 on sorting Insertion sort algorithm

0 wendy
Q. What’s the most efficient way to sort 1 million 32-bit integers?
Insertion sort 1 alice
• Move down through the array. 2 dave
• Each item bubbles up above the larger ones above it. 3 walter
• Everything above the current item is in order. 4 carlos
• Everything below the current item is untouched. 5 carol

6 erin

7 oscar

Like bubble sort, but not bubble sort. 8 peggy

We don't teach bubble sort any more because this is simpler and faster. 9 trudy

10 eve

11 trent

12 bob

13 craig

14 frank

15 victor
23 24
Insertion sort trace Insertion sort: Java implementation

0 wendy alice alice alice alice alice alice alice alice alice alice alice alice alice alice alice
public class Insertion
1 alice wendy dave dave carlos carlos carlos carlos carlos carlos carlos carlos bob bob bob bob {
% more [Link]
2 dave dave wendy walter dave carol carol carol carol carol carol carol carlos carlos carlos carlos public static void sort(String[] a) wendy
{ alice
3 walter walter walter wendy walter dave dave dave dave dave dave dave carol carol carol carol int N = [Link]; dave % java Insertion < [Link]
4 carlos carlos carlos carlos wendy walter erin erin erin erin erin erin dave craig craig craig for (int i = 1; i < N; i++) walter alice
for (int j = i; j > 0; j--) carlos bob
5 carol carol carol carol carol wendy walter oscar oscar oscar eve eve erin dave dave dave if (a[j-1].compareTo(a[j]) > 0) carol carlos
exch(a, j-1, j); erin carol
6 erin erin erin erin erin erin wendy walter peggy peggy oscar oscar eve erin erin erin oscar
else break; craig
7 oscar oscar oscar oscar oscar oscar oscar wendy walter trudy peggy peggy oscar eve eve eve peggy
} dave
trudy erin
8 peggy peggy peggy peggy peggy peggy peggy peggy wendy walter trudy trent peggy oscar frank frank eve eve
private static void exch(String[] a, int i, int j) trent frank
9 trudy trudy trudy trudy trudy trudy trudy trudy trudy wendy walter trudy trent peggy oscar oscar { String t = a[i]; a[i] = a[j]; a[j] = t; } bob oscar
craig
10 eve eve eve eve eve eve eve eve eve eve wendy walter trudy trent peggy peggy peggy
public static void main(String[] args) frank trent
11 trent trent trent trent trent trent trent trent trent trent trent wendy walter trudy trent trent { victor trudy
String[] a = [Link](); victor
12 bob bob bob bob bob bob bob bob bob bob bob bob wendy walter trudy trudy
sort(a); walter
13 craig craig craig craig craig craig craig craig craig craig craig craig craig wendy walter victor for (int i = 0; i < [Link]; i++) wendy
[Link](a[i]);
14 frank frank frank frank frank frank frank frank frank frank frank frank frank frank wendy walter
}
15 victor victor victor victor victor victor victor victor victor victor victor victor victor victor victor wendy }
25 26

Empirical tests of insertion sort A rule of thumb

TN Moore's law. The number of transistors in an integrated circuit doubles about every 2 years.
N TN/TN/2 % java Generator 20000 ...
Sort random strings (seconds)
1 seconds
• Array of length N. 20,000 1
% java Generator 40000 ...
4 seconds
• 10-character strings. % java Generator 80000 ...
Implications
40,000 4 35 seconds

80,000 35 9
% java Generator 160000 ... • Memory size doubles every two years.
225 seconds
% java Generator 320000 ... • Processor speed doubles every two years.
160,000 225 6.4 1019 seconds
Gordon Moore
320,000 1019 4.5 ... = 10 a-z | java Insertion Founder of Intel
1929 –
a-z = abcdefghijklmnopqrstuvwxyz
...
computer instructions per second words of memory
1.28 million 14400 4 4 hours
PDP-9 tens of thousands tens of thousands
Sedgewick's rule of thumb. It
And 4x64/24 = 10+ days to
sort 10 million? Sounds bad. VAX 11-780 millions millions
Confirms hypothesis that order of growth is N 2. takes a few seconds to access
every word in a computer. CRAY 1 tens of millions tens of millions
will NOT scale Do you have
anything better?
MacBook Air billions billions
27 28
 Scalability COMPUTER SCIENCE
S E D G E W I C K / W A Y N E

An algorithm scales if its running time doubles when the problem size doubles. PA R T I : P R O G R A M M I N G I N J AVA

2x faster computer with 2x memory using an alg that scales? Image sources

• Can solve problems we're solving now in half the time. order of [Link]
scales?
growth
• Can solve a 2x-sized problem in the same time it took to
solve an x-sized problem. N ✓
• Progress.
N log N ✓
2x faster computer with 2x memory using quadratic alg? N2 ✗
• Can solve problems we're solving now in half the time.
• Takes twice as long solve a 2x-sized problem as it took to N3 ✗
solve an x-sized problem.
• Frustration.

Bottom line. Need algorithms that scale to keep pace with Moore's law.

29 [Link]

COMPUTER SCIENCE Mergesort algorithm

S E D G E W I C K / W A Y N E
PA R T I I : A L G O R I T H M S , T H E O R Y, A N D M A C H I N E S
Divide wendy Sort alice Merge
Mergesort halves
alice carlos
• Divide array into two halves.
dave carol
• Recursively sort each half.
walter dave
• Merge two halves to make carlos erin
sorted whole.
11. Sorting and Searching carol
erin
oscar
walter
oscar wendy
• A typical client peggy bob
John von Neumann
• Binary search • Pioneered computing (stay tuned).
trudy craig
eve eve
• Insertion sort • Early focus on numerical calculations.
trent frank
• Invented mergesort as a test to see
• Mergesort how his machine would measure up bob peggy
on other tasks.
• Longest repeated substring John von Neumann
1903–1957
craig trent
frank trudy
victor victor
[Link] 32
Merge: Java implementation Mergesort: Java implementation

Abstract inplace merge i alice lo k Mergesort

private static String[] aux;
•public
Merge a[lo,
static mid)
void with a[mid,
merge(String[] hi).
a, int lo, int
carlos • Divide array into two halves. % more [Link]

•mid,
Useint hi)
auxiliary array for result. carol • Recursively sort each half. wendy
{ alice
• Copy backa[lo,
// Merge when merge
mid) with is complete.
a[mid, hi) into aux[0, dave • Merge two halves to make sorted whole. dave % java Merge < [Link]
hi-lo). walter
erin alice
int i = lo, j = mid, N = hi - lo; carlos bob
for (int k = 0; k < N; k++) oscar public class Merge carol carlos
{ { erin carol
if (i == mid) aux[k] = a[j++]; walter private static String[] aux; oscar craig
else if (j == hi) aux[k] = a[i++]; public static void merge(String[] a, int lo, int mid, int hi) peggy
wendy { // See previous slide. }
dave
else if (a[j].compareTo(a[i]) < 0) aux[k] = trudy erin
a[j++]; j bob mid public static void sort(String[] a) eve eve
{ trent
else aux[k] = aux = new String[[Link]]; // Allocate just once! frank
craig bob
a[i++]; sort(a, 0, [Link]); oscar
} eve } craig peggy
// Copy back into a[lo, hi) public static void sort(String[] a, int lo, int hi) frank trent
for (int k = 0; k < N; k++) frank { // Sort a[lo, hi). victor trudy
a[lo + k] = aux[k]; int N = hi - lo; victor
peggy
} if (N <= 1) return; walter
trent int mid = lo + N/2; wendy
sort(a, lo, mid);
trudy sort(a, mid, hi);
merge(a, lo, mid, hi);
victor
}
hi 33 ... same test client as for Insertion 34

Mergesort trace Mergesort analysis

lgN
Mergesort wendy
alice wendy
alice wendy
alice wendy
alice wendy Cost model. Count data moves.
• Divide array into two halves. alice
bob alice
carlos alice
dave alice
wendy alice
# of times a string moves
alice alice alice alice wendy
bob carlos dave wendy alice
• Recursively sort each half. dave
carlos dave
carol dave
walter dave
dave dave from one array to another
carlos carol walter dave
dave
• Merge two halves to make walter
carol walter
dave walter
wendy walter
walter walter
Exact analysis for N = 2n . carol dave wendy walter walter
sorted whole. carlos
craig carlos
erin carlos
carlos carlos
carlos carlos craig erin carlos carlos carlos
• Note that n = lgN.
carol
dave carol
oscar carol
carol carol
carol carol dave oscar carol carol carol
• 1 subarray of size 2n .
erin walter erin erin erin
erin
erin erin
walter erin
erin erin
erin erin
• 2 subarrays of size 2n 1. eve wendy oscar oscar oscar
oscar oscar oscar oscar oscar
eve wendy oscar oscar • 4 subarrays of size 2n 2. frank bob eve peggy peggy
peggy
frank peggy
bob peggy
eve peggy
peggy peggy • ... oscar craig peggy trudy trudy
trudy
oscar trudy
craig trudy
peggy trudy
trudy trudy • 2n subarrays of size 1. peggy eve trent eve eve
trent frank trudy trent trent
eve
peggy eve
eve eve
trent eve
eve eve • Total # data moves: 2N lgN.
trudy peggy bob bob bob
trent
trent trent
frank trent
trudy trent
trent trent
victor trent craig craig craig
bob
trudy bob
peggy bob
bob bob
bob bob walter trudy frank frank frank
Interested in
craig
victor craig
trent craig
craig craig
craig craig wendy victor victor victor victor
details? Take a
frank frank frank frank frank course in 1 subarray 2 subarrays 4 subarrays 8 subarrays 16 subarrays
walter trudy frank frank of size N of size N/2 of size N/4 of size N/8 of size N/16
victor victor victor victor victor algorithms.
wendy victor victor victor 2N data moves 2N data moves 2N data moves 2N data moves
35 36
 Empirical tests of mergesort COMPUTER SCIENCE
S E D G E W I C K / W A Y N E
PA R T I : P R O G R A M M I N G I N J AVA
TN
N TN/TN/2 % java Generator 1000000 ...
Sort random strings (seconds)
1 seconds
• Array of length N. 1 million 1
% java Generator 2000000 ...
2 seconds
• 10-character strings. % java Generator 4000000 ...
2 million 2 5 seconds
% java Generator 8000000 ...
4 million 5 2.5 10 seconds
% java Generator 16000000 ...
8 million 10 2 20 seconds

16 million 20 2.5 ... = 10 a-z | java Merge

a-z = abcdefghijklmnopqrstuvwxyz
...

1.02 billion 1280 2

20
minutes OK! Let's get started...

Confirms hypothesis that order of growth is N log N

WILL scale 37 [Link]

COMPUTER SCIENCE Detecting repeats in a string

S E D G E W I C K / W A Y N E
PA R T I I : A L G O R I T H M S , T H E O R Y, A N D M A C H I N E S
Longest repeated substring
• Given: A string s.
• Task: Find the longest substring in s that appears at least twice.

11. Sorting and Searching Example 1. a a c a a g t t t a c a a g c

• A typical client
Example 2. a a c a a g t t t a c a a g t t t a c a a g c t a g c
• Binary search
• Insertion sort 3 . 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
Example 3 (first 100 digits of π). 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7
• Mergesort
1 6 9 3 9 9 3 7 5 1 0 5 8 2 0 9 7 4 9 4
• Longest repeated substring
4 5 9 2 3 0 7 8 1 6 4 0 6 2 8 6 2 0 8 9
9 8 6 2 8 0 3 4 8 2 5 3 4 2 1 1 7 0 6 9
[Link] 40
LRS example: repetitive structure in music LRS applications

Analysts seek repeated sequences in real-world data because they are causal.

3.141592653589793238462643383279502884
Example 1: Digits of π 19716939937510582097494459230781640628
62089986280348253421170679821480865132
Mary had a little lamb • Q. Are they “random” ? 82306647093844609550582231725359408128
48111745028410270193852110555964462294
• A. No, but we can’t tell the difference. 89549303819644288109756659334461284756
48233786783165271201909145648566923460
• Ex. Length of LRS in first 10 million digits is 14. 34861045432664821339360726024914127372
45870066063155881748815209209628292540

Example 2: Cryptography 11001001001111011011100101101011100110

00101111110100100001001101001011110011
• Find LRS. 00100111111101110000010101100010000111
01010011010000111100100110011101111111
01010000010000100010100101010001100000
• Check for “known” message header information. 10111100010010011010110111100011010011
01110011110101111001000100111010101110
• Break code. 10000010100100010001101010101110000000
Für Elise 10110000010011100010111011010010101100

Example 3: DNA tgactaatccagtatccagggcaaattaggttacccac

gtgattacgagaggttccgccgctaatcgggtgcgtcc
• Find LRS gaaacgtatgccctcttctgctcgatgtgattggccgg
cctgtgtcatgccggcacttaaacgatcaaatagtgaa
aatcaaaatcgccggtctgtgagcctagcggatgcaag
• Look somewhere else for causal mechanisms atgggcgtacatgcccagcccaccttcggaccgagctg
cgcgtagggccgtagtgctaaagtctgagaatacccca
• Ex. Chromosome 11 has 7.1 million nucleotides gtcgttcgttgaggcgcacgtctatgcataatttatgg
aggtcagtgctcttcagaggttgcagtttactctattc
41 42

Warmup: Longest common prefix LRS: Brute-force implementation

Longest common prefix public class LRS

{
• Given: Two strings string s and t. public static String lcp(String s)
{ // See previous slide. }
• Task: Find the longest substring that appears at the beginning of both % more [Link]
aacaagtttacaagc
public static String lrs(String s)
{ % java LRSbrute
int N = [Link](); acaag
String lrs = "";
Example. a a c a a g t t t a c a a g c for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
{
a a c a a g t t t a c a a g t t t a c a a g c t a g c String x = lcp([Link](i, N), [Link](j, N));
if ([Link]() > [Link]()) lrs = x;
}
return lrs;
}
Implementation (easy) public static void main(String[] args) Analysis
{
private static String lcp(String s, String t) String s= [Link](); • ~N 2/2 calls on lcp().
{ [Link](lrs(s));
int N = [Link]([Link](), [Link]()); }
• Obviously does not scale.
for (int i = 0; i < N; i++) }
if ([Link](i) != [Link](i))
return [Link](0, i);
return [Link](0, N);
}
43 44
LRS: An efficient solution that uses sorting LRS: Suffix array implementation
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
a a c a a g t t t a c a a g c public static String lrs(String s) % more [Link]
{ aacaagtttacaagc
int N = [Link]();
1. Form suffix strings 2. Sort suffix strings
String[] suffixes = new String[N]; % java LRS
0 a a c a a g t t t a c a a g c 0 a a c a a g t t t a c a a g c Form suffix acaag
strings for (int i = 0; i < N; i++)
1 a c a a g t t t a c a a g c 11 a a g c suffixes[i] = [Link](i, N);
2 c a a g t t t a c a a g c 3 a a g t t t a c a a g c
3 a a g t t t a c a a g c 9 a c a a g c Sort suffix [Link](suffixes);
strings Analysis
4 a g t t t a c a a g c 1 a c a a g t t t a c a a g c
String lrs = ""; • N calls on substring().
5 g t t t a c a a g c 12 a g c for (int i = 0; i < N-1; i++)
Find longest
6 t t t a c a a g c 4 a g t t t a c a a g c LCP among { • N calls on lcp().
7 t t a c a a g c 14 c adjacent String x = lcp(suffixes[i], suffixes[i+1]);
entries. if ([Link]() > [Link]()) lrs = x;
• Potentially scales.
8 t a c a a g c 10 c a a g c
}
9 a c a a g c 2 c a a g t t t a c a a g c
return lrs;
10 c a a g c 13 g c }
11 a a g c 5 g t t t a c a a g c
12 a g c 8 t a c a a g c
13 g c 7 t t a c a a g c
14 c 6 t t t a c a a g c

3. Find longest LCP among adjacent entries.

45 46

LRS: Empirical analysis (1995-2012) LRS: Empirical analysis (since 2012)

% java Generator 1 1000000 actg | java LRS

Model 2 seconds Model
% java Generator 1 10000000 actg | java LRS
• Alphabet: actg. 21 seconds • Alphabet: actg.
• N-character random strings. • N-character random strings.

Doubling x10
% java Generator 1 10000 actg | java LRS
N TN TN/TN/2 N TN TN/TN/10 Exception in thread "main" [Link]: Java heap space
at [Link]([Link])
2,000,000 3 1,000,000 2 at [Link].<init>([Link])
at [Link]([Link])
4,000,000 7 2.3 10,000,000 21 10 at [Link]([Link])
at [Link]([Link])

8,000,000 16 2.3

16,000,000 39 2.4

Confirms hypothesis that the order of growth is N log N (for the sort).

Bottom line. Scales with the size of the input and enables new research and development. Change in the system breaks a working program (not good).
47 48
Explanation: Two alternatives for implementing substrings Fixing the LRS implementation

1. Refer to original string (1995-2102). String genome = "aacaagtttacaagc";

Implement our own constant-time suffix operation.
• No need to copy characters. String s = [Link](1, 5);
String t = [Link](9, 13); • Imitate old substring() implementation.
• Constant time and space.
• Need compareTo() to enable sort.
x genome t s
• (Details in Algorithms)
Good thing I took
... a a c a a g t t t a c a a g c x 15 x+9 4 x+1 4 ...
that algorithms
course!
memory length
address % java Generator 1 1000000 actg | java LRSfixed
2 seconds
% java Generator 1 10000000 actg | java LRSfixed
21 seconds
2. Copy the characters to make a new string (since 2012).
• Allows potential to free up memory when the original string is no longer needed.
• Linear time and space (in the length of the substring).

x genome y t z s Lesson. Trust the algorithm, not the system.

... a a c a g t t t a c a a g c x 15 a c a a y 4 a c a a z 4 ...
Bottom line. New research and development can continue.
49 50

Final note on LRS implementation Summary

Binary search. Efficient algorithm to search a sorted array.

Long repeats Mergesort. Efficient algorithm to sort an array.
• More precise analysis reveals that running time Applications. Many, many, many things are enabled by fast sort and search.
is quadratic in the length of the longest repeat.
Example: Chromosome 11
• Model has no long repeats. has a repeat of length
• Real data may have long repeats. 12,567.

• Linear time algorithm (guarantee) is known. Hey, Bob. Our IPO is next week!

I think I'll take a few CS courses.

51 52
 COMPUTER SCIENCE COMPUTER SCIENCE
S E D G E W I C K / W A Y N E S E D G E W I C K / W A Y N E
PA R T I : P R O G R A M M I N G I N J AVA PA R T I I : A L G O R I T H M S , T H E O R Y, A N D M A C H I N E S

Image sources

[Link]

Computer Science
11. Sorting and
Computer Searching
ScienceAn Interdisciplinary Approach

ROBERT SEDGEWICK

Section 4.2 K E V I N WAY N E

[Link]

[Link]