Introduction xxix Chapter 1 Algorithm Basics 1 Approach 2 Algorithms and Data Structures 2 Pseudocode 3 Algorithm Features 6 Big O Notation 7 Rule 1 8 Rule 2 8 Rule 3 9 Rule 4 9 Rule 5 10 Common Run Time Functions 11 1 11 Log N 11 Sqrt N 14 N 14 N log N 15 N 2 15 2N 15 N! 16 Visualizing Functions 16 Practical Considerations 18 Summary 19 Exercises 20 Chapter 2 Numerical Algorithms 23 Randomizing Data 23 Generating Random Values 23 Generating Values 24 Ensuring Fairness 26 Getting Fairness from Biased Sources 28 Randomizing Arrays 29 Generating Nonuniform Distributions 30 Making Random Walks 31 Making Self-Avoiding Walks 33 Making Complete Self-Avoiding Walks 34 Finding Greatest Common Divisors 36 Calculating Greatest Common Divisors 36 Extending Greatest Common Divisors 38 Performing Exponentiation 40 Working with Prime Numbers 42 Finding Prime Factors 42 Finding Primes 44 Testing for Primality 45 Performing Numerical Integration 47 The Rectangle Rule 48 The Trapezoid Rule 49 Adaptive Quadrature 50 Monte Carlo Integration 54 Finding Zeros 55 Gaussian Elimination 57 Forward Elimination 58 Back Substitution 60 The Algorithm 61 Least Squares Fits 62 Linear Least Squares 62 Polynomial Least Squares 64 Summary 67 Exercises 68 Chapter 3 Linked Lists 71 Basic Concepts 71 Singly Linked Lists 72 Iterating Over the List 73 Finding Cells 73 Using Sentinels 74 Adding Cells at the Beginning 75 Adding Cells at the End 76 Inserting Cells After Other Cells 77 Deleting Cells 78 Doubly Linked Lists 79 Sorted Linked Lists 81 Self-Organizing Linked Lists 82 Move to Front (MTF) 83 Swap 83 Count 84 Hybrid Methods 84 Pseudocode 85 Linked-List Algorithms 86 Copying Lists 86 Sorting with Insertionsort 87 Sorting with Selectionsort 88 Multithreaded Linked Lists 90 Linked Lists with Loops 91 Marking Cells 92 Using Hash Tables 93 List Retracing 94 List Reversal 95 Tortoise and Hare 98 Loops in Doubly Linked Lists 100 Summary 100 Exercises 101 Chapter 4 Arrays 103 Basic Concepts 103 One-Dimensional Arrays 106 Finding Items 106 Finding Minimum, Maximum, and Average 107 Finding Median 108 Finding Mode 109 Inserting Items 112 Removing Items 113 Nonzero Lower Bounds 114 Two Dimensions 114 Higher Dimensions 115 Triangular Arrays 118 Sparse Arrays 121 Find a Row or Column 123 Get a Value 124 Set a Value 125 Delete a Value 127 Matrices 129 Summary 131 Exercises 132 Chapter 5 Stacks and Queues 135 Stacks 135 Linked-List Stacks 136 Array Stacks 138 Double Stacks 139 Stack Algorithms 141 Reversing an Array 141 Train Sorting 142 Tower of Hanoi 143 Stack Insertionsort 145 Stack Selectionsort 146 Queues 147 Linked-List Queues 148 Array Queues 148 Specialized Queues 151 Priority Queues 151 Deques 152 Binomial Heaps 152 Binomial Trees 152 Binomial Heaps 154 Merging Trees 155 Merging Heaps 156 Merging Tree Lists 156 Merging Trees 158 Enqueue 161 Dequeue 162 Runtime 163 Summary 163 Exercises 164 Chapter 6 Sorting 167 O(N2 ) Algorithms 168 Insertionsort in Arrays 168 Selectionsort in Arrays 170 Bubblesort 171 O(NlogN) Algorithms 174 Heapsort 175 Storing Complete Binary Trees 175 Defining Heaps 176 Implementing Heapsort 180 Quicksort 181 Analyzing Quicksort''s Run Time 182 Picking a Dividing Item 184 Implementing Quicksort with Stacks 185 Implementing Quicksort in Place 185 Using Quicksort 188 Mergesort 189 Sub O(NlogN) Algorithms 192 Countingsort 192 Pigeonhole Sort 193 Bucketsort 195 Summary 197 Exercises 198 Chapter 7 Searching 201 Linear Search 202 Binary Search 203 Interpolation Search 204 Majority Voting 205 Summary 207 Exercises 208 Chapter 8 Hash Tables 209 Hash Table Fundamentals 210 Chaining 211 Open Addressing 213 Removing Items 214 Linear Probing 215 Quadratic Probing 217 Pseudorandom Probing 219 Double Hashing 219 Ordered Hashing 219 Summary 222 Exercises 222 Chapter 9 Recursion 227 Basic Algorithms 228 Factorial 228 Fibonacci Numbers 230 Rod-Cutting 232 Brute Force 233 Recursion 233 Tower of Hanoi 235 Graphical Algorithms 238 Koch Curves 239 Hilbert Curve 241 Sierpi?ski Curve 243 Gaskets 246 The Skyline Problem 247 Lists 248 Divide and Conquer 249 Backtracking Algorithms 252 Eight Queens Problem 254 Knight''s Tour 257 Selections and Permutations 260 Selections with Loops 261 Selections with Duplicates 262 Selections without Duplicates 264 Permutations with Duplicates 265 Permutations without Duplicates 266 Round-Robin Scheduling 267 Odd Number of Teams 268 Even Number of Teams 270 Implementation 271 Recursion Removal 273 Tail Recursion Removal 274 Dynamic Programming 275 Bottom-Up Programming 277 General Recursion Removal 277 Summary 280 Exercises 281 Chapter 10 Trees 285 Tree Terminology 285 Binary Tree Properties 289 Tree Representations 292 Building Trees in General 292 Building Complete Trees 295 Tree Traversal 296 Preorder Traversal 297 Inorder Traversal 299 Postorder Traversal 300 Breadth-First Traversal 301 Traversal Uses 302 Traversal Run Times 303 Sorted Trees 303 Adding Nodes 303 Finding Nodes 306 Deleting Nodes 306 Lowest Common Ancestors 309 Sorted Trees 309 Parent Pointers 310 Parents and Depths 311 General Trees 312 Euler Tours 314 All Pairs 316 Threaded Trees 317 Building Threaded Trees 318 Using Threaded Trees 320 Specialized Tree Algorithms 322 The Animal Game 322 Expression Evaluation 324 Interval Trees 326 Building the Tree 328 Intersecting with Points 329 Intersecting with Intervals 330 Quadtrees 332 Adding Items 335 Finding Items 336 Tries 337 Adding Items 339 Finding Items 341 Summary 342 Exercises 342 Chapter 11 Balanced Trees 349 AVL Trees 350 Adding Values 350 Deleting Values 353 2-3 Trees 354 Adding Values 355 Deleting Values 356 B-Trees 359 Adding Values 360 Deleting Values 361 Balanced Tree Variations 362 Top-down B-trees 363 B+trees 363 Summary 365 Exercises 365 Chapter 12 Decision Trees 367 Searching Game Trees 368 Minimax 369 Initial Moves and Responses 373 Game Tree Heuristics 374 Searching General Decision Trees 375 Optimization Problems 376 Exhaustive Search 377 Branch and Bound 379 Decision Tree Heuristics 381 Random Search 381 Improving Paths 382 Simulated Annealing 384 Hill Climbing 385 Sorted Hill Climbing 386 Other Decision Tree Problems 387 Generalized Partition Problem 387 Subset Sum 388 Bin Packing 388 Cutting Stock 389 Knapsack 390 Traveling Salesman Problem 391 Satisfiability 391 Swarm Intelligence 392 Ant Colony Optimization 393 General Optimization 393 Traveling Salesman 393 Bees Algorithm 394 Swarm Simulation 394 Boids 395 Pseudoclassical Mechanics 396 Goals and Obstacles 397 Summary 397 Exercises 398 Chapter 13 Basic Network Algorithms 403 Network Terminology 403 Network Representations 407 Traversals 409 Depth-First Traversal 410 Breadth-First Traversal 412 Connectivity Testing 413 Spanning Trees 416 Minimal Spanning Trees 417 Euclidean Minimum Spanning Trees 418 Building Mazes 419 Strongly Connected Components 420 Kosaraju''s Algorithm 421 Algorithm Discussion 422 Finding Paths 425 Finding Any Path 425 Label-Setting Shortest Paths 426 Label-Correcting Shortest Paths 430 All-Pairs Shortest Paths 431 Transitivity 436 Transitive Closure 437 Transitive Reduction 438 Acyclic Networks 439 General Networks 440 Shortest Path Modifications 441 Shape Points 441 Early Stopping 442 Bidirectional Search 442 Best-First Search 442 Turn Penalties and Prohibitions 443 Geometric Calculations 443 Expanded Node Networks 444 Interchange Networks 445 Summary 447 Exercises 447 Chapter 14 More Network Algorithms 451 Topological Sorting.