Z......Page
Preface 6......Page 0006
--- full adder, 1......Page 0012
product, 2......Page 0013
--- loop fusion, 3......Page 0014
division (integer), 6......Page 0017
--- recursive, 7......Page 0018
Ofman, Y., 9......Page 0020
1.6 Algorithm Engineering 11......Page 0022
1.7 The Programs 13......Page 0024
1.8 Proofs of Lemma 1.5 and Theorem 1.7 16......Page 0027
GMP, 17......Page 0028
Toom, A., 18......Page 0029
2 Introduction 19......Page 0030
--- worst case, 20......Page 0031
von Neumann, J., 23......Page 0034
undefined value (?), 26......Page 0037
sieve of Eratosthenes, 31......Page 0042
2.5 An Example – Binary Search 34......Page 0045
--- running time, 36......Page 0047
--- global, 41......Page 0052
2.8 Randomized Algorithms 45......Page 0056
target node, 49......Page 0060
traversal, 53......Page 0064
Meyer, B., 56......Page 0067
random source, 57......Page 0068
tablet, 59......Page 0070
removing from a sequence, 60......Page 0071
--- size, 66......Page 0077
--- operation sequence, 71......Page 0082
--- top, 74......Page 0085
space efficiency, 77......Page 0088
vector (in C++), 78......Page 0089
--- vector, 79......Page 0090
Perl, 81......Page 0091
--- remove, 83......Page 0093
--- unbounded, 85......Page 0095
Peterson, W. W., 90......Page 0100
--- perfect, 92......Page 0102
--- slim, 95......Page 0105
Ziviani, N., 97......Page 0107
telephone book, 99......Page 0109
5.1 Simple Sorters 101......Page 0111
--- almost sorted inputs, 103......Page 0113
--- sorting tree, 106......Page 0116
--- element uniqueness, 108......Page 0118
statistics, 114......Page 0124
stable algorithm, 116......Page 0126
--- external, 118......Page 0128
5.8 Implementation Notes 122......Page 0132
Singler, J., 124......Page 0134
--- deleteMin, 127......Page 0136
Williams, J. W. J., 129......Page 0138
--- item, 133......Page 0142
--- external, 139......Page 0148
--- memory management, 141......Page 0150
--- priority_queue, 142......Page 0151
--- remove, 145......Page 0153
--- perfect balance, 147......Page 0155
--- rotation, 149......Page 0157
--- range searching, 156......Page 0164
--- removing a range, 158......Page 0166
--- augmentation, 160......Page 0168
7.6 Implementation Notes 162......Page 0170
set, 164......Page 0172
numbering, 167......Page 0175
--- static, 168......Page 0176
--- sparse, 170......Page 0178
Zlotowski, O., 171......Page 0179
--- interval graph, 172......Page 0180
Tamassia, R., 174......Page 0182
--- traversal, 175......Page 0183
--- layer, 176......Page 0184
--- marked, 178......Page 0186
--- graph traversal, 188......Page 0196
Vishkin, U., 189......Page 0197
single-source, 191......Page 0198
--- unit edge cost, 192......Page 0199
--- DAG, 195......Page 0202
--- public transportation, 196......Page 0203
10.4 *Average-Case Analysis of Dijkstra’s Algorithm 199......Page 0206
--- invariant, 201......Page 0208
--- Bellman–Ford algorithm, 206......Page 0213
--- all-pairs with negative costs, 207......Page 0214
Sivadasan, N., 209......Page 0216
10.9 Implementation Notes 213......Page 0220
--- parallel, 214......Page 0221
--- design, 217......Page 0223
maximum-cost spanning tree, 218......Page 0224
Prim, R. C., 219......Page 0225
Kruskal, J., 221......Page 0227
union–find, 222......Page 0228
Sibeyn, J., 225......Page 0231
--- Steiner tree, 228......Page 0234
Shapiro, H. D., 231......Page 0237
universe (U ), 233......Page 0239
--- linear program (LP), 234......Page 0240
set covering, 239......Page 0245
--- dynamic programming, 243......Page 0249
Thompson, K., 246......Page 0252
--- branch-and-cut, 249......Page 0255
survival of the fittest, 259......Page 0265
12.7 Implementation Notes 261......Page 0267
Vanderbei, R. J., 262......Page 0268
A.1 Mathematical Symbols 263......Page 0269
--- antisymmetric, 264......Page 0270
sample space, 266......Page 0272
tail bound, 269......Page 0275
References 273......Page 0279
Index 285......Page 0290
--- 15......Page 26
, 248......Page 254
Thomas, R., 255......Page 0261
Westbrook, J., 232......Page 0238
Ackermann function (inverse), 224......Page 0230
XOR (?), 24......Page 35
tuple, 27......Page 38
van Emde Boas layout, 165......Page 0173
--- external sorting, 120......Page 0130
--- school method, 1......Page 12
--- result checking, 6......Page 17
unbounded array, 60......Page 71
, 135......Page 144
, 158......Page 166
, 203......Page 210
--- token, 68......Page 0079
--- deamortization, 70......Page 0081
--- universality of potential method, 73......Page 0084
shortest-queue algorithm, 241......Page 0247
, 41......Page 52
, 84......Page 94
, 103......Page 113
Stirling’s approximation, 107......Page 117
, 109......Page 119
streaming algorithm, 115......Page 125
--- MSD, 117......Page 127
, 124......Page 134
, 148......Page 156
, 199......Page 206
--- ALD (average linear Dijkstra), 205......Page 212
, 245......Page 251
, 37......Page 48
, 104......Page 114
, 45......Page 56
splitter, 121......Page 131
recurrence relation, 9......Page 20
, 16......Page 27
, 12......Page 23
--- 4......Page 15
--- insertion, 36......Page 47
--- worst case, 109......Page 0119
, 86......Page 96
, 87......Page 97
, 89......Page 99
selection, 101......Page 111
, 171......Page 179
, 174......Page 182
--- black-box solvers, 234......Page 240
, 261......Page 267
termination, 33......Page 44
tree, 51......Page 62
-edge-connected components, 187......Page 195
, 46......Page 57
, 100......Page 110
modulo, 7......Page 18
, 34......Page 45
--- siftDown, 131......Page 0140
--- random numbers, 117......Page 0127
--- multiway merge, 119......Page 0129
, 108......Page 118
median, 114......Page 124
principle of optimality, 243......Page 249
Vocking, B., 245......Page 0251
, 246......Page 252
--- uniqueness, 193......Page 0200
recombination, 259......Page 265
, 262......Page 268
, 239......Page 245
, 257......Page 263
--- street network, 51......Page 0062
-approximation (round), 240......Page 246
--- local search, 249......Page 255
--- hill climbing, 250......Page 0256
relaxation, 256, see also under......Page 0262
geometry, 252......Page 0258
--- fixed-K annealing, 258......Page 0264
--- lookup table, 203......Page 0210
Vitter, J. S., 120......Page 130
, 232......Page 238
, 92......Page 102
Winkel, S., 125......Page 135
, 165,......Page 173
, 226......Page 232
--- Markov’s, 48......Page 59
, 85......Page 95
, 53......Page 64
strings, 113......Page 123
, 131......Page 140
, 178......Page 186
, 198......Page 205
Wolsey, L., 248......Page 0254
total order, 99......Page 109
, 172......Page 180
--- 5......Page 16
, 10......Page 21
asymptotic, 11......Page 22
Thorup, M., 95......Page 105
, 111......Page 121
, 123......Page 133
, 163......Page 171
--- 209......Page 216
alignment, 8......Page 19
triple, 27......Page 0038
--- root, 52......Page 0063
unary operation, 24......Page 0035
Zagha, M., 125......Page 0135
--- Held–Karp lower bound, 230......Page 0236
--- bottleneck, 217......Page 223
--- greedy algorithm, 240......Page 0246
Schevon, C., 257......Page 0263
Wickremsinghe, R., 123......Page 0133
variable, 26......Page 37
, 59......Page 70
hash function, 82......Page 0092
, 75......Page 86
, 201......Page 208
small subproblems, 111......Page 0121
precondition, 32......Page 0043
while, 28......Page 0039
--- best case, 20......Page 31
machine model, 21......Page 32
SIMD, 25......Page 36
Sipser, M., 54......Page 0065
thread, 25......Page 0036
McCreight, E. M., 163......Page 0171
--- transit node routing, 212......Page 0219
--- remove, 128......Page 0137
--- use of, 146......Page 154
, 242......Page 248
--- 270......Page 0276
Vuillemin, J., 137......Page 0146
exponential search, 35......Page 0046
satisfiable, 242......Page 0248
Siek, J. G., 173......Page 0181
, 162......Page 170
, 128......Page 137
, 141......Page 150
Zwick, U., 143......Page 152
--- thin heap, 143......Page 0152
oversampling, 121......Page 0131
--- LEDA, 17......Page 28
template programming, 31......Page 42
, 57......Page 68
--- iterator, 78......Page 89
, 96......Page 106
, 142......Page 151
, 164......Page 172
, 173......Page 181
, 214......Page 221
, 231......Page 237
subroutine, 29......Page 0040
--- 2......Page 13
--- decreaseKey, 138......Page 0147
certifying algorithm, 33......Page 0044
--- 166......Page 174
, 122......Page 132
, 269......Page 275
sweep-line algorithm, 146......Page 0154
, 106......Page 116
--- 3......Page 14
, 58......Page 69
hashing, 81......Page 91
, 200......Page 207
, 265......Page 271
polytope, 251......Page 0257
diet problem, 235......Page 0241
weakly antisymmetric, 265......Page 0271
Java, 18......Page 29
triangle inequality, 230......Page 236
cooling schedule, 254......Page 0260
mating, 260......Page 0266
--- simple, 50......Page 0061
--- strongly connected components, 50......Page 61
Wegener, I., 54......Page 65
, 147......Page 155
, 29......Page 40
, 225......Page 231
Tarjan, R. E., 79......Page 90
Tower of Hanoi, 75......Page 0086
--- expected height, 148......Page 0156
Dijkstra, E., 196......Page 203
--- cycle property, 219......Page 225
van Emde Boas, P., 166......Page 0174
, 175,......Page 183
, 179......Page 187
, 181......Page 189
multigraph, 167......Page 175
--- semiexternal Kruskal algorithm, 226......Page 0232
NodeArray, 168......Page 176
-coloring, 256......Page 262
, 266......Page 272
--- building heap, 132......Page 0141
--- external-memory, 76......Page 0087
, 118......Page 128
Ziegelmann, M., 215......Page 0222
--- two-pointer items, 135......Page 0144
, 74......Page 85
--- representative, 177......Page 185
Flajolet, P., 40......Page 0051
, 56......Page 67
maximum flow, 237......Page 0243
, 97......Page 107
--- hash_set, 96......Page 0106
Schultes, D., 212......Page 219
Sedgewick, R., 40......Page 51
, 241......Page 247
--- reached, 176......Page 184
, 192......Page 199
--- biconnected components, 188......Page 196
, 189......Page 197
--- bidirected, 49......Page 60
, 170......Page 178
, 55......Page 66
-coloring, 255......Page 261
, 169......Page 177
--- cut property, 218......Page 224
, 206......Page 213
--- depth, 52......Page 63
--- topological sorting, 180......Page 188
, 221......Page 227
--- range, 100......Page 0110
--- random, 208......Page 215
shrunken graph, 182......Page 0190
, 228......Page 234
--- certificate, 187......Page 0195
--- 181......Page 0189
--- open, 183......Page 0191
, 195......Page 202
--- transitive closure, 177......Page 0185
, 83......Page 93
, 90......Page 100
--- unbounded, 91......Page 0101
--- universal family, 86......Page 0096
--- simple linear, 89......Page 0099
--- abundance, 88......Page 0098
--- using scalar products, 87......Page 0097
--- unrealistic analysis, 84......Page 0094
key, 82......Page 92
--- siftUp, 130......Page 0139
move-to-front, 44......Page 0055
Wilhelm, R., 58......Page 0069
--- product, 268......Page 0274
, 110......Page 120
, 268......Page 274
machine word, 23......Page 34
verification, 32......Page 43
, 182......Page 190
--- naive, 129......Page 138
, 133......Page 142
, 149......Page 157
, 159......Page 167
, 202......Page 209
, 222......Page 228
small inputs, 102......Page 112
--- minimum, 127......Page 136
--- use of, 191......Page 198
--- rounding, 238......Page 0244
, 238......Page 244
, 247......Page 253
--- lower-order term, 22......Page 0033
--- random, 42......Page 53
, 252......Page 258
--- constrained, 215......Page 222
--- integer (ILP), 236......Page 242
--- as a linear program, 236......Page 0242
, 267......Page 273
--- blocked, 76......Page 87
--- list, 105......Page 0115
--- circular, 136......Page 145
, 64......Page 75
, 65......Page 76
--- locate, 145......Page 153
--- splice, 61......Page 72
--- move item, 61......Page 0072
sentinel, 63......Page 74
--- insert, 62......Page 73
--- swapping sublists, 64......Page 0075
, 28......Page 39
--- minimum, 107......Page 0117
Markov, A., 48......Page 0059
, 229......Page 235
Pareto-optimal, 244......Page 250
, 264,......Page 270
--- invariant, 202......Page 0209
multikey quicksort, 113......Page 0123
--- refined, 12......Page 0023
--- ordering relation (?), 179......Page 0187
, 207......Page 214
, 211......Page 218
, 197......Page 204
Noshita, K., 200......Page 0207
--- ?(·), 21......Page 0032
online algorithm, 44......Page 55
, 233......Page 239
Ullmann, Z., 244......Page 0250
pipelining, 4......Page 0015
polynomial, 22......Page 33
--- representation, 136......Page 0145
, 130......Page 139
--- base b, 204......Page 0211
random number, 46......Page 0057
, 260......Page 266
--- exponential, 35......Page 46
reduction, 55......Page 0066
Zelikowski, A., 229......Page 0235
, 151......Page 159
--- linear, 43......Page 0054
, 224......Page 230
streaming, 115......Page 0125
--- goal-directed search, 211......Page 0218
--- tentative distance, 194......Page 0201
--- linear average time, 205......Page 0212
split (node), 152......Page 0160
--- remove, 153......Page 0161
splitting, 157......Page 0165
--- locate, 150......Page 0158
--- insert, 151......Page 0159
--- merging, 161......Page 0169
, 156......Page 164
--- red–black tree, 155......Page 163
--- weight-balanced tree, 160......Page 168
--- dynamic, 102......Page 0112
, 132......Page 141
, 105......Page 115
, 116......Page 126
--- run formation, 119......Page 129
, 270......Page 276
STL, 13......Page 24
--- estimation by integral, 271......Page 0277
--- geometric, 38......Page 49
--- harmonic, 43......Page 54
, 88......Page 98
, 250......Page 256
, 66......Page 77
union by rank, 223......Page 0229
, 235......Page 241
