------NETB223----[2013/2014]------------------ 00 7.3.4 Heap-Sort, 343 Implementing Heap-Sort In-Place, 343 7.3.5 Bottom-Up Heap Construction (*), 345 **** 8.3.5 Heap-Sort 8.3.6 Bottom-Up Heap Construction ------NETB223----[2013/2014]------------------ 01 7.4 The Locator Design Pattern, 349 Tracking Elements as they Move, 349 Defining the Locator Pattern, 349 Using Locators with Data Structures, 350 Locator Member Functions, 350 7.4.1 Locator-Based Priority Queue Functions (*), 351 Extending the Priority Queue ADT, 351 7.4.2 Implementing Locator-Based Priority Queues (*), 353 *** 8.4 Adaptable Priority Queues 8.4.1 A List-Based Implementation 8.4.2 Location-Aware Entries ------NETB223----[2013/2014]------------------ 02 8.4 Skip Lists, 394 8.4.1 Searching, 396 8.4.2 Update Operations, 397 Insertion, 397 Removal, 399 Maintaining the Top-most Level, 400 http://en.wikipedia.org/wiki/Skip_lists **** 9.4 Skip Lists 9.4.1 Search and Update Operations in a Skip List 9.4.2 A Probabilistic Analysis of Skip Lists**** ------NETB223----[2013/2014]------------------ 03 http://en.wikipedia.org/wiki/Splay_tree **** 10.3 Splay Trees 10.3.1 Splaying 10.3.2 When to Splay 10.3.3 Amortized Analysis of Splaying**** ------NETB223----[2013/2014]------------------ 04 9.6 Locator-Based Search Trees (*), 468 9.7 External Searching (*), 470 9.7.1 $(a,b)$ Trees, 471 Update Operations, 472 9.7.2 B-Trees, 474 ------NETB223----[2013/2014]------------------ 05 10.2 The Set ADT, 498 10.2.1 A Simple Set Implementation, 499 Sets in STL, 499 Using a Sorted Sequence to Implement a Set, 499 Generic Merging as a Template Method Pattern, 500 Using Inheritence to Derive Set Operations, 502 Performance of Generic Merging, 502 **** 11.4.1 The Set ADT 11.4.2 Mergable Sets and the Template Method Pattern ------NETB223----[2013/2014]------------------ 06 http://en.wikipedia.org/wiki/Disjoint-set_data_structure **** 11.4.3 Partitions with Union-Find Operations ------NETB223----[2013/2014]------------------ 07 10.7 Selection, 522 10.7.1 Prune-and-Search, 522 10.7.2 Randomized Quick-Select, 523 http://en.wikipedia.org/wiki/Quick_select **** 11.5 Selection 11.5.1 Prune-and-Search 11.5.2 Randomized Quick-Select 11.5.3 Analyzing Randomized Quick-Select*** ------NETB223----[2013/2014]------------------ 08 11.2 Pattern Matching Algorithms, 538 11.2.1 Brute Force, 538 http://en.wikipedia.org/wiki/Brute-force_search **** 12.3 Pattern Matching Algorithms 12.3.1 Brute Force ------NETB223----[2013/2014]------------------ 09 11.2 Pattern Matching Algorithms, 538 11.2.2 The Boyer-Moore Algorithm, 540 http://en.wikipedia.org/wiki/Boyer-Moore_algorithm **** 12.3.2 The Boyer-Moore Algorithm ------NETB223----[2013/2014]------------------ 10 11.2 Pattern Matching Algorithms, 538 11.2.3 The Knuth-Morris-Pratt Algorithm, 545 The Failure Function, 545 Performance, 547 Constructing the KMP Failure Function, 548 http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm **** 12.3.3 The Knuth-Morris-Pratt Algorithm ------NETB223----[2013/2014]------------------ 11 11.3 Tries, 550 11.3.1 Standard Tries, 550 http://www.ii.uib.no/~michal/und/i120/2002/telle/pdf/Tries.pdf **** 12.5 Tries 12.5.1 Standard Tries ------NETB223----[2013/2014]------------------ 12 11.3 Tries, 550 11.3.2 Compressed Tries, 554 http://www.ii.uib.no/~michal/und/i120/2002/telle/pdf/Tries.pdf ------NETB223----[2013/2014]------------------ 13 11.3 Tries, 550 11.3.3 Suffix Tries, 556 Saving Space, 556 Construction, 556 Using a Suffix Trie, 557 Performance, 559 http://www.ii.uib.no/~michal/und/i120/2002/telle/pdf/Tries.pdf ------NETB223----[2013/2014]------------------ 14 11.4 Text Compression, 561 11.4.1 The Huffman Coding Algorithm, 562 11.4.2 The Greedy Method, 563 http://en.wikipedia.org/wiki/Huffman_coding **** 12.5.2 Compressed Tries ------NETB223----[2013/2014]------------------ 15 11.5 Text Similarity Testing, 564 11.5.1 The Longest Common Subsequence Problem, 564 Problem Definition, 564 11.5.2 Dynamic Programming, 565 11.5.3 Applying Dynamic Programming to the LCS Problem, 565 The LCS Algorithm, 567 Performance, 567 http://en.wikipedia.org/wiki/Dynamic_Programming ------NETB223----[2013/2014]------------------