Elementary Algorithms - L.Xinyu.pdf

(6960 KB) Pobierz
Elementary Algorithms
Larry LIU Xinyu
May 27, 2015
1
Larry LIU Xinyu
Version: 0.6180339887498949
Email: liuxinyu95@gmail.com
1
2
Contents
I
Preface
0.1
0.2
Why?
. . . . . . . . . . . . . . . . . . . . . . . . . . .
The smallest free ID problem, the power of algorithms
0.2.1 Improvement 1
. . . . . . . . . . . . . . . . . .
0.2.2 Improvement 2, Divide and Conquer
. . . . . .
0.2.3 Expressiveness vs. Performance
. . . . . . . . .
The number puzzle, power of data structure
. . . . . .
0.3.1 The brute-force solution
. . . . . . . . . . . . .
0.3.2 Improvement 1
. . . . . . . . . . . . . . . . . .
0.3.3 Improvement 2
. . . . . . . . . . . . . . . . . .
Notes and short summary
. . . . . . . . . . . . . . . .
Structure of the contents
. . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
13
13
14
15
16
18
18
18
21
24
24
0.3
0.4
0.5
II
Trees
structure
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
29
31
31
32
35
36
38
39
40
40
42
46
49
49
50
52
53
55
56
1 Binary search tree, the ‘hello world’ data
1.1 Introduction
. . . . . . . . . . . . . . . . .
1.2 Data Layout
. . . . . . . . . . . . . . . . .
1.3 Insertion
. . . . . . . . . . . . . . . . . . .
1.4 Traversing
. . . . . . . . . . . . . . . . . .
1.5 Querying a binary search tree
. . . . . . .
1.5.1 Looking up
. . . . . . . . . . . . .
1.5.2 Minimum and maximum
. . . . . .
1.5.3 Successor and predecessor
. . . . .
1.6 Deletion
. . . . . . . . . . . . . . . . . . .
1.7 Randomly build binary search tree
. . . .
2 The
2.1
2.2
2.3
2.4
2.5
2.6
evolution of insertion sort
Introduction
. . . . . . . . . . . . . . . .
Insertion
. . . . . . . . . . . . . . . . . .
Improvement 1
. . . . . . . . . . . . . .
Improvement 2
. . . . . . . . . . . . . .
Final improvement by binary search tree
Short summary
. . . . . . . . . . . . . .
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
3 Red-black tree, not so complex as it was thought
3.1 Introduction
. . . . . . . . . . . . . . . . . . . . . .
3.1.1 Exploit the binary search tree
. . . . . . . .
3.1.2 How to ensure the balance of the tree
. . .
3.1.3 Tree rotation
. . . . . . . . . . . . . . . . .
3.2 Definition of red-black tree
. . . . . . . . . . . . .
3.3 Insertion
. . . . . . . . . . . . . . . . . . . . . . . .
3.4 Deletion
. . . . . . . . . . . . . . . . . . . . . . . .
3.5 Imperative red-black tree algorithm
. . . . . . .
3.6 More words
. . . . . . . . . . . . . . . . . . . . . .
4 AVL tree
4.1 Introduction
. . . . . . . . . . . . . . . . . . .
4.1.1 How to measure the balance of a tree?
4.2 Definition of AVL tree
. . . . . . . . . . . . .
4.3 Insertion
. . . . . . . . . . . . . . . . . . . . .
4.3.1 Balancing adjustment
. . . . . . . . .
4.3.2 Pattern Matching
. . . . . . . . . . . .
4.4 Deletion
. . . . . . . . . . . . . . . . . . . . .
4.5 Imperative AVL tree algorithm
. . . . . . .
4.6 Chapter note
. . . . . . . . . . . . . . . . . .
CONTENTS
59
59
59
60
62
64
65
68
76
79
83
83
83
83
86
88
92
94
94
98
101
101
102
103
103
105
106
106
108
113
115
115
115
118
119
119
120
125
126
127
131
136
139
139
140
141
142
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 Radix tree, Trie and Patricia
5.1 Introduction
. . . . . . . . . . . . . . . . . . . .
5.2 Integer Trie
. . . . . . . . . . . . . . . . . . . .
5.2.1 Definition of integer Trie
. . . . . . . . .
5.2.2 Insertion
. . . . . . . . . . . . . . . . . .
5.2.3 Look up
. . . . . . . . . . . . . . . . . .
5.3 Integer Patricia
. . . . . . . . . . . . . . . . . .
5.3.1 Definition
. . . . . . . . . . . . . . . . .
5.3.2 Insertion
. . . . . . . . . . . . . . . . . .
5.3.3 Look up
. . . . . . . . . . . . . . . . . .
5.4 Alphabetic Trie
. . . . . . . . . . . . . . . . . .
5.4.1 Definition
. . . . . . . . . . . . . . . . .
5.4.2 Insertion
. . . . . . . . . . . . . . . . . .
5.4.3 Look up
. . . . . . . . . . . . . . . . . .
5.5 Alphabetic Patricia
. . . . . . . . . . . . . . . .
5.5.1 Definition
. . . . . . . . . . . . . . . . .
5.5.2 Insertion
. . . . . . . . . . . . . . . . . .
5.5.3 Look up
. . . . . . . . . . . . . . . . . .
5.6 Trie and Patricia applications
. . . . . . . . . .
5.6.1 E-dictionary and word auto-completion
5.6.2 T9 input method
. . . . . . . . . . . . .
5.7 Summary
. . . . . . . . . . . . . . . . . . . . .
6 Suffix Tree
6.1 Introduction
. . . . . . . . . . . . . .
6.2 Suffix trie
. . . . . . . . . . . . . . .
6.2.1 Node transfer and suffix link
6.2.2 On-line construction
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
CONTENTS
6.3
6.4
Suffix
6.3.1
Suffix
6.4.1
6.4.2
6.4.3
6.4.4
6.4.5
Notes
Tree
. . . . . . . . . . . . . . . . . . .
On-line construction
. . . . . . . . .
tree applications
. . . . . . . . . . . .
String/Pattern searching
. . . . . . .
Find the longest repeated sub-string
Find the longest common sub-string
Find the longest palindrome
. . . . .
Others
. . . . . . . . . . . . . . . . .
and short summary
. . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
147
147
156
156
158
159
161
162
162
165
165
167
167
174
174
182
188
189
6.5
7 B-Trees
7.1 Introduction
. . . . . . . . . . . . .
7.2 Insertion
. . . . . . . . . . . . . . .
7.2.1 Splitting
. . . . . . . . . . .
7.3 Deletion
. . . . . . . . . . . . . . .
7.3.1 Merge before delete method
7.3.2 Delete and fix method
. . .
7.4 Searching
. . . . . . . . . . . . . .
7.5 Notes and short summary
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
III
Heaps
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
193
195
195
195
196
197
198
200
207
209
210
211
212
213
214
215
216
222
222
227
227
229
230
231
232
233
233
8 Binary Heaps
8.1 Introduction
. . . . . . . . . . . . . . . . . . . . . . . .
8.2 Implicit binary heap by array
. . . . . . . . . . . . . .
8.2.1 Definition
. . . . . . . . . . . . . . . . . . . . .
8.2.2 Heapify
. . . . . . . . . . . . . . . . . . . . . .
8.2.3 Build a heap
. . . . . . . . . . . . . . . . . . .
8.2.4 Basic heap operations
. . . . . . . . . . . . . .
8.2.5 Heap sort
. . . . . . . . . . . . . . . . . . . . .
8.3 Leftist heap and Skew heap, the explicit binary heaps
8.3.1 Definition
. . . . . . . . . . . . . . . . . . . . .
8.3.2 Merge
. . . . . . . . . . . . . . . . . . . . . . .
8.3.3 Basic heap operations
. . . . . . . . . . . . . .
8.3.4 Heap sort by Leftist Heap
. . . . . . . . . . . .
8.3.5 Skew heaps
. . . . . . . . . . . . . . . . . . . .
8.4 Splay heap
. . . . . . . . . . . . . . . . . . . . . . . .
8.4.1 Definition
. . . . . . . . . . . . . . . . . . . . .
8.4.2 Heap sort
. . . . . . . . . . . . . . . . . . . . .
8.5 Notes and short summary
. . . . . . . . . . . . . . . .
9 From grape to the world cup, the evolution of selection
9.1 Introduction
. . . . . . . . . . . . . . . . . . . . . . . . . .
9.2 Finding the minimum
. . . . . . . . . . . . . . . . . . . .
9.2.1 Labeling
. . . . . . . . . . . . . . . . . . . . . . . .
9.2.2 Grouping
. . . . . . . . . . . . . . . . . . . . . . .
9.2.3 performance of the basic selection sorting
. . . . .
9.3 Minor Improvement
. . . . . . . . . . . . . . . . . . . . .
9.3.1 Parameterize the comparator
. . . . . . . . . . . .
sort
. . .
. . .
. . .
. . .
. . .
. . .
. . .
.
.
.
.
.
.
.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin