------NETB223----[2014/2015]------------------ 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----[2014/2015]------------------ 02 7.3.4 Heap-Sort, 343 Implementing Heap-Sort In-Place, 343 7.3.5 Bottom-Up Heap Construction (*), 345 ------NETB223----[2014/2015]------------------ -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----[2014/2015]------------------ -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----[2014/2015]------------------ -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----[2014/2015]------------------ 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----[2014/2015]------------------ 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----[2014/2015]------------------ -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----[2014/2015]------------------ 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----[2014/2015]------------------ 10 Alpha-beta pruning http://en.wikipedia.org/wiki/Alpha-beta_search ------NETB223----[2014/2015]------------------ 11 11.2 Pattern Matching Algorithms, 538 11.2.1 Brute Force, 538 http://en.wikipedia.org/wiki/Brute-force_search ------NETB223----[2014/2015]------------------ -12 11.2 Pattern Matching Algorithms, 538 11.2.2 The Boyer-Moore Algorithm, 540 http://en.wikipedia.org/wiki/Boyer-Moore_algorithm ------NETB223----[2014/2015]------------------ -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----[2014/2015]------------------ -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----[2014/2015]------------------ -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----[2014/2015]------------------ -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----[2014/2015]------------------ -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----[2014/2015]------------------ -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----[2014/2015]------------------ -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----[2014/2015]------------------ 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----[2014/2015]------------------ 21 12.2 Data Structures for Graphs, 585 12.2.2 The Adjacency List Structure, 589 The Adjacency List, 589 Performance, 591 http://en.wikipedia.org/wiki/Graph_(data_structure) ------NETB223----[2014/2015]------------------ 22 12.2 Data Structures for Graphs, 585 12.2.3 The Adjacency Matrix Structure, 592 Performance, 594 http://en.wikipedia.org/wiki/Graph_theory#Matrix_structures ------NETB223----[2014/2015]------------------ -23 12.3 Graph Traversal, 595 12.3.1 Depth-First Search, 595 The Decorator Pattern, 599 Polymorphic Objects, 600 A Generic DFS Implementation in C++, 602 Using the Template Method Pattern for DFS, 602 http://en.wikipedia.org/wiki/Depth-first_search ------NETB223----[2014/2015]------------------ 24 12.3 Graph Traversal, 595 12.3.2 Breadth-First Search, 608 http://en.wikipedia.org/wiki/Breadth-first_search ------NETB223----[2014/2015]------------------ 25 12.4 Directed Graphs, 611 Comparing BFS and DFS for Directed and Undirected Graphs, 611 Reachability, 611 12.4.1 Traversing a Digraph, 613 Testing for Strong Connectivity, 615 Directed Breadth-First Search, 615 http://en.wikipedia.org/wiki/Breadth-first_search http://en.wikipedia.org/wiki/Digraph_(mathematics) ------NETB223----[2014/2015]------------------ 26 12.4 Directed Graphs, 611 12.4.2 Transitive Closure, 615 http://en.wikipedia.org/wiki/Digraph_(mathematics) http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm ------NETB223----[2014/2015]------------------ 27 12.4 Directed Graphs, 611 12.4.3 Directed Acyclic Graphs, 617 Testing if a Directed Graph is Acyclic, 622 http://en.wikipedia.org/wiki/Digraph_(mathematics) ------NETB223----[2014/2015]------------------ 28 12.6 Shortest Paths, 626 12.6.1 Dijkstra's Algorithm, 627 A Greedy Method for Finding Shortest Paths, 627 Edge Relaxation, 627 Why It Works, 630 The Running Time of Dijkstra's Algorithm, 632 An Alternative Implementation for Dijkstra's Algorithm, 633 Comparing the Two Implementations, 633 Programming Dijkstra's Algorithm in C++, 633 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ------NETB223----[2014/2015]------------------ 29 Bellman-Ford algorithm http://en.wikipedia.org/wiki/Bellman-Ford_algorithm ------NETB223----[2014/2015]------------------ 30 12.7 Minimum Spanning Trees, 637 Problem Definition, 637 A Crucial Fact about Minimum Spanning Trees, 638 12.7.1 Kruskal's Algorithm, 639 The Running Time of Kruskal's Algorithm, 642 http://en.wikipedia.org/wiki/Kruskal%27s_algorithm ------NETB223----[2014/2015]------------------ 31 Reverse-delete algorithm http://en.wikipedia.org/wiki/Reverse-Delete_algorithm ------NETB223----[2014/2015]------------------ -32 12.7 Minimum Spanning Trees, 637 12.7.2 The Prim-Jarnik Algorithm, 643 A Comparison of the Above MST Algorithms, 646 http://en.wikipedia.org/wiki/Prim-Jarnik_algorithm