Stephens, R: Essential Algorithms

153Sub O(N log N) Algorithms 156Countingsort 156Bucketsort 157Summary 159Exercises 160Chapter 7 Searching 163Linear Search 164Binary Search 165Interpolation Search 166Summary 167Exercises 168Chapter 8 Hash Tables 169Hash Table Fundamentals 170Chaining 171Open Addressing 172Removing Items 174Liner Probing 174Quadratic Probing 176Pseudorandom Probing 178Double Hashing 178Ordered Hashing 179Summary 181Exercises 182Chapter 9 Recursion 185Basic Algorithms 186Factorial 186Fibonacci Numbers 188Tower of Hanoi 189Graphical Algorithms 193Koch Curves 193Hilbert Curve 196Sierpin¿ ski Curve 197Gaskets 200Backtracking Algorithms 201Eight Queens Problem 203Knight's Tour 206Selections and Permutations 209Selections with Loops 210Selections with Duplicates 211Selections Without Duplicates 213Permutations with Duplicates 214Permutations Without Duplicates 215Recursion Removal 216Tail Recursion Removal 216Storing Intermediate Values 218General Recursion Removal 220Summary 222Exercises 223Chapter 10 Trees 227Tree Terminology 227Binary Tree Properties 231Tree Representations 234Building Trees in General 234Building Complete Trees 236Tree Traversal 237Preorder Traversal 238Inorder Traversal 240Postorder Traversal 242Depth-first Traversal 243Traversal Run Times 244Sorted Trees 245Adding Nodes 245Finding Nodes 247Deleting Nodes 248Threaded Trees 250Building Threaded Trees 251Using Threaded Trees 254Specialized Tree Algorithms 256The Animal Game 256Expression Evaluation 258Quadtrees 260Tries 266Summary 270Exercises 271Chapter 11 Balanced Trees 277AVL Trees 278Adding Values 278Deleting Values 2812-3 Trees 282Adding Values 283Deleting Values 284B-Trees 287Adding Values 288Deleting Values 289Balanced Tree Variations 291Top-down B-trees 291B+trees 291Summary 293Exercises 293Chapter 12 Decision Trees 297Searching Game Trees 298Minimax 298Initial Moves and Responses 302Game Tree Heuristics 303Searching General Decision Trees 305Optimization Problems 306Exhaustive Search 307Branch and Bound 309Decision Tree Heuristics 310Other Decision Tree Problems 316Summary 322Exercises 322Chapter 13 Basic Network Algorithms 325Network Terminology 325Network Representations 328Traversals 331Depth-first Traversal 331Breadth-first Traversal 334Connectivity Testing 335Spanning Trees 337Minimal Spanning Trees 338Finding Paths 339Finding Any Path 339Label-Setting Shortest Paths 340Label-Correcting Shortest Paths 344All-Pairs Shortest Paths 345Summary 350Exercises 351Chapter 14 More Network Algorithms 355Topological Sorting 355Cycle Detection 359Map Coloring 359Two-coloring 360Three-coloring 362Four-coloring 362Five-coloring 363Other Map-coloring Algorithms 367Maximal Flow 368Work Assignment 370Minimal Flow Cut 372Summary 374Exercises 375Chapter 15 String Algorithms 377Matching Parentheses 378Evaluating Arithmetic Expressions 379Building Parse Trees 380Pattern Matching 381DFAs 381Building DFAs for Regular Expressions 383NFAs 386String Searching 387Calculating Edit Distance 391Summary 394Exercises 394Chapter 16 Cryptography 397Terminology 398Transposition Ciphers 399Row/column Transposition 399Column Transposition 401Route Ciphers 403Substitution Ciphers 404Caesar Substitution 404Vigenère Cipher 405Simple Substitution 407One-Time Pads 408Block Ciphers 408Substitution-Permutation Networks 409Feistel Ciphers 410Public-Key Encryption and RSA 412Euler's Totient Function 413Multiplicative Inverses 413An RSA Example 414Practical Considerations 414Other Uses for Cryptography 415Summary 416Exercises 417Chapter 17 Complexity Theory 419Notation 420Complexity Classes 421Reductions 4243SAT 425Bipartite Matching 426NP-Hardness 426Detection, Reporting, and Optimization Problems 427Detection