TABLE OF CONTENTS xvii CHAPTER SEVEN:PERMUTATIONS 345 7.1 Basic Properties of Permutations 347 7.2 Algorithms on Permutations 355 7.3 Representations of Permutations 358 7.4 Enumeration Problems 366 7.5 Analyzing Properties of Permutations with CGFs 372 7.6 Inversions and Insertion Sorts 384 7.7 Left-to-Right Minima and Selection Sort 393 7.8 Cycles and In Situ Permutation 401 7.9 Extremal Parameters 406 CHAPTER EIGHT:STRINGS AND TRIES 415 8.1 String Searching 416 8.2 Combinatorial Properties of Bitstrings 420 8.3 Regular Expressions 432 8.4 Finite-State Automata and the Knuth-Morris-Pratt 437 Algorithm 8.5 Context-Free Grammars 441 8.6 Tries 448 8.7 Trie Algorithms 453 8.8 Combinatorial Properties of Tries 459 8.9 Larger Alphabets 465 CHAPTER NINE:WORDS AND MAPPINGS 473 9.1 Hashing with Separate Chaining 474 9.2 The Balls-and-Urns Model and Properties of Words 476 9.3 Birthday Paradox and Coupon Collector Problem 485 9.4 Occupancy Restrictions and Extremal Parameters 495 9.5 Occupancy Distributions 501 9.6 Open Addressing Hashing 509 9.7 Mappings 519 9.8 Integer Factorization and Mappings 532 List of Theorems 543 List of Tables 545 List of Figures 547 Index 551 www.it-ebooks.infoT ō Ŏ Ř ő ś Œ C ś Ś Š ő Ś Š ş xvii CŔōŜŠőŞ SőŢőŚ: PőŞřšŠōŠ ඦş 345 7.1 Basic Properties of Permutations 347 7.2 Algorithms on Permutations 355 7.3 Representations of Permutations 358 7.4 Enumeration Problems 366 7.5 Analyzing Properties of Permutations with CGFs 372 7.6 Inversions and Insertion Sorts 384 7.7 Left-to-Right Minima and Selection Sort 393 7.8 Cycles and In Situ Permutation 401 7.9 Extremal Parameters 406 CŔōŜŠőŞ E ŕœŔŠ: SŠŞ ŕŚœş ōŚŐ TŞ ŕőş 415 8.1 String Searching 416 8.2 Combinatorial Properties of Bitstrings 420 8.3 Regular Expressions 432 8.4 Finite-State Automata and the Knuth-Morris-Pratt 437 Algorithm 8.5 Context-Free Grammars 441 8.6 Tries 448 8.7 Trie Algorithms 453 8.8 Combinatorial Properties of Tries 459 8.9 Larger Alphabets 465 CŔōŜŠőŞ N ŕŚő: WśŞŐş ōŚŐ MōŜŜ ŕŚœş 473 9.1 Hashing with Separate Chaining 474 9.2 Ļe Balls-and-Urns Model and Properties of Words 476 9.3 Birthday Paradox and Coupon Collector Problem 485 9.4 Occupancy Restrictions and Extremal Parameters 495 9.5 Occupancy Distributions 501 9.6 Open Addressing Hashing 509 9.7 Mappings 519 9.8 Integer Factorization and Mappings 532 List of Ļeorems 543 List of Tables 545 List of Figures 547 Index 551 www.it-ebooks.info