------NETB223----[2012/2013]------------------ 01 4.6 Sample Case Study Application, 190 The Stock Span Problem, 190 4.6.1 A Quadratic-Time Algorithm, 191 4.6.2 A Linear-Time Algorithm, 192 Summarizing the Running Time, 193 4.6.3 C++ Implementation, 195 ------NETB223----[2012/2013]------------------ 02 7.3.4 Heap-Sort, 343 Implementing Heap-Sort In-Place, 343 7.3.5 Bottom-Up Heap Construction (*), 345 ------NETB223----[2012/2013]------------------ 03 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 ------NETB223----[2012/2013]------------------ 04 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 ------NETB223----[2012/2013]------------------ 05 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----[2012/2013]------------------ 06 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 ------NETB223----[2012/2013]------------------ 07 10.5 Bucket-Sort and Radix-Sort, 517 10.5.1 Bucket-Sort, 517 Stable Sorting, 518 10.5.2 Radix-Sort, 518 http://en.wikipedia.org/wiki/Bucket_sort http://en.wikipedia.org/wiki/Radix_sort ------NETB223----[2012/2013]------------------ 08 10.6 Comparison of Sorting Algorithms, 520 Insertion-Sort, 520 Merge-Sort, 520 Quick-Sort, 521 Heap-Sort, 521 Bucket-Sort and Radix-Sort, 521 http://en.wikipedia.org/wiki/Sorting_algorithm ------NETB223----[2012/2013]------------------ 09 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 ------NETB223----[2012/2013]------------------ 10 Alpha-beta pruning http://en.wikipedia.org/wiki/Alpha-beta_search ------NETB223----[2012/2013]------------------ 11 11.2 Pattern Matching Algorithms, 538 11.2.1 Brute Force, 538 http://en.wikipedia.org/wiki/Brute-force_search ------NETB223----[2012/2013]------------------ 12 11.2 Pattern Matching Algorithms, 538 11.2.2 The Boyer-Moore Algorithm, 540 http://en.wikipedia.org/wiki/Boyer-Moore_algorithm ------NETB223----[2012/2013]------------------ 13 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 ------NETB223----[2012/2013]------------------ 14 11.3 Tries, 550 11.3.1 Standard Tries, 550 http://www.ii.uib.no/~michal/und/i120/2002/telle/pdf/Tries.pdf ------NETB223----[2012/2013]------------------ 15 11.3 Tries, 550 11.3.2 Compressed Tries, 554 http://www.ii.uib.no/~michal/und/i120/2002/telle/pdf/Tries.pdf ------NETB223----[2012/2013]------------------ 16 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----[2012/2013]------------------ 17 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 ------NETB223----[2012/2013]------------------ 18 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----[2012/2013]------------------ 19 12.1 The Graph Abstract Data Type, 577 12.1.1 Graph Functions, 582 General Functions, 583 Functions Dealing with Directed Edges, 583 Functions for Updating Graphs, 584 http://en.wikipedia.org/wiki/Graph_(data_structure) ------NETB223----[2012/2013]------------------ 20 12.2 Data Structures for Graphs, 585 12.2.1 The Edge List Structure, 585 Vertex Objects, 585 Edge Objects, 586 The Edge List, 586 Performance, 588 http://en.wikipedia.org/wiki/Graph_(data_structure) ------NETB223----[2012/2013]------------------