Algorithm Design and Applications
Publisher: Wiley
Published: Oct 27, 2014
Number of pages: 816
ISBN-13: 9781118335918
Table of contents: title: Preface
pagenum: xi; label: 1
title: Algorithm Analysis
pagenum: 1; label: 1.1
title: Analyzing Algorithms
pagenum: 3; label: 1.2
title: A Quick Mathematical Review
pagenum: 19; label: 1.3
title: A Case Study in Algorithm Analysis
pagenum: 29; label: 1.4
title: Amortization
pagenum: 34; label: 1.5
title: Exercises
pagenum: 42; label: Part I
title: Data Structures; label: 2
title: Basic Data Structures
pagenum: 51; label: 2.1
title: Stacks and Queues
pagenum: 53; label: 2.2
title: Lists
pagenum: 60; label: 2.3
title: Trees
pagenum: 68; label: 2.4
title: Exercises
pagenum: 84; label: 3
title: Binary Search Trees
pagenum: 89; label: 3.1
title: Searches and Updates
pagenum: 91; label: 3.2
title: Range Queries
pagenum: 101; label: 3.3
title: Index-Based Searching
pagenum: 104; label: 3.4
title: Randomly Constructed Search Trees
pagenum: 107; label: 3.5
title: Exercises
pagenum: 110; label: 4
title: Balanced Binary Search Trees
pagenum: 115; label: 4.1
title: Ranks and Rotations
pagenum: 117; label: 4.2
title: AVL Trees
pagenum: 120; label: 4.3
title: Red-Black Trees
pagenum: 126; label: 4.4
title: Weak AVL Trees
pagenum: 130; label: 4.5
title: Splay Trees
pagenum: 139; label: 4.6
title: Exercises
pagenum: 149; label: 5
title: Priority Queues and Heaps
pagenum: 155; label: 5.1
title: Priority Queues
pagenum: 157; label: 5.2
title: PQ-Sort, Selection-Sort, and Insertion-Sort
pagenum: 158; label: 5.3
title: Heaps
pagenum: 163; label: 5.4
title: Heap-Sort
pagenum: 174; label: 5.5
title: Extending Priority Queues
pagenum: 179; label: 5.6
title: Exercises
pagenum: 182; label: 6
title: Hash Tables
pagenum: 187; label: 6.1
title: Maps
pagenum: 189; label: 6.2
title: Hash Functions
pagenum: 192; label: 6.3
title: Handling Collisions and Rehashing
pagenum: 198; label: 6.4
title: Cuckoo Hashing
pagenum: 206; label: 6.5
title: Universal Hashing
pagenum: 212; label: 6.6
title: Exercises
pagenum: 215; label: 7
title: Union-Find Structures
pagenum: 219; label: 7.1
title: Union-Find and Its Applications
pagenum: 221; label: 7.2
title: A List-Based Implementation
pagenum: 225; label: 7.3
title: A Tree-Based Implementation
pagenum: 228; label: 7.4
title: Exercises
pagenum: 236; label: Part II
title: Sorting and Selection; label: 8
title: Merge-Sort and Quick-Sort
pagenum: 241; label: 8.1
title: Merge-Sort
pagenum: 243; label: 8.2
title: Quick-Sort
pagenum: 250; label: 8.3
title: A Lower Bound on Comparison-Based Sorting
pagenum: 257; label: 8.4
title: Exercises
pagenum: 259; label: 9
title: Fast Sorting and Selection
pagenum: 265; label: 9.1
title: Bucket-Sort and Radix-Sort
pagenum: 267; label: 9.2
title: Selection
pagenum: 270; label: 9.3
title: Weighted Medians
pagenum: 276; label: 9.4
title: Exercises
pagenum: 279; label: Part III
title: Fundamental Techniques; label: 10
title: The Greedy Method
pagenum: 283; label: 10.1
title: The Fractional Knapsack Problem
pagenum: 286; label: 10.2
title: Task Scheduling
pagenum: 289; label: 10.3
title: Text Compression and Huffman Coding
pagenum: 292; label: 10.4
title: Exercises
pagenum: 298; label: 11
title: Divide-and-Conquer
pagenum: 303; label: 11.1
title: Recurrences and the Master Theorem
pagenum: 305; label: 11.2
title: Integer Multiplication
pagenum: 313; label: 11.3
title: Matrix Multiplication
pagenum: 315; label: 11.4
title: The Maxima-Set Problem
pagenum: 317; label: 11.5
title: Exercises
pagenum: 319; label: 12
title: Dynamic Programming
pagenum: 323; label: 12.1
title: Matrix Chain-Products
pagenum: 325; label: 12.2
title: The General Technique
pagenum: 329; label: 12.3
title: Telescope Scheduling
pagenum: 331; label: 12.4
title: Game Strategies
pagenum: 334; label: 12.5
title: The Longest Common Subsequence Problem
pagenum: 339; label: 12.6
title: The 0-1 Knapsack Problem
pagenum: 343; label: 12.7
title: Exercises
pagenum: 346; label: 13
title: Graphs and Traversals
pagenum: 353; label: 13.1
title: Graph Terminology and Representations
pagenum: 355; label: 13.2
title: Depth-First Search
pagenum: 365; label: 13.3
title: Breadth-First Search
pagenum: 370; label: 13.4
title: Directed Graphs
pagenum: 373; label: 13.5
title: Biconnected Components
pagenum: 386; label: 13.6
title: Exercises
pagenum: 392; label: Part IV
title: Graph Algorithms; label: 14
title: Shortest Paths
pagenum: 397; label: 14.1
title: Single-Source Shortest Paths
pagenum: 399; label: 14.2
title: Dijkstra's Algorithm
pagenum: 400; label: 14.3
title: The Bellman-Ford Algorithm
pagenum: 407; label: 14.4
title: Shortest Paths in Directed Acyclic Graphs
pagenum: 410; label: 14.5
title: All-Pairs Shortest Paths
pagenum: 412; label: 14.6
title: Exercises
pagenum: 418; label: 15
title: Minimum Spanning Trees
pagenum: 423; label: 15.1
title: Properties of Minimum Spanning Trees
pagenum: 425; label: 15.2
title: Kruskal's Algorithm
pagenum: 428; label: 15.3
title: The Prim-Jarník Algorithm
pagenum: 433; label: 15.4
title: Borůvka's Algorithm
pagenum: 436; label: 15.5
title: Exercises
pagenum: 439; label: 16
title: Network Flow and Matching
pagenum: 443; label: 16.1
title: Flows and Cuts
pagenum: 445; label: 16.2
title: Maximum Flow Algorithms
pagenum: 452; label: 16.3
title: Maximum Bipartite Matching
pagenum: 458; label: 16.4
title: Baseball Elimination
pagenum: 460; label: 16.5
title: Minimum-Cost Flow
pagenum: 462; label: 16.6
title: Exercises
pagenum: 469; label: Part V
title: Computational Intractability; label: 17
title: NP-Completeness
pagenum: 473; label: 17.1
title: P and NP
pagenum: 476; label: 17.2
title: NP-Completeness
pagenum: 483; label: 17.3
title: CNF-SAT and 3SAT
pagenum: 489; label: 17.4
title: VERTEX-COVER, CLIQUE, and SET-COVER
pagenum: 492; label: 17.5
title: SUBSET-SUM and KNAPSACK
pagenum: 496; label: 17.6
title: HAMILTONIAN-CYCLE and TSP
pagenum: 499; label: 17.7
title: Exercises
pagenum: 502; label: 18
title: Approximation Algorithms
pagenum: 507; label: 18.1
title: The Metric Traveling Salesperson Problem
pagenum: 511; label: 18.2
title: Approximations for Covering Problems
pagenum: 515; label: 18.3
title: Polynomial-Time Approximation Schemes
pagenum: 518; label: 18.4
title: Backtracking and Branch-and-Bound
pagenum: 521; label: 18.5
title: Exercises
pagenum: 525; label: Part VI
title: Additional Topics; label: 19
title: Randomized Algorithms
pagenum: 529; label: 19.1
title: Generating Random Permutations
pagenum: 531; label: 19.2
title: Stable Marriages and Coupon Collecting
pagenum: 534; label: 19.3
title: Minimum Cuts
pagenum: 539; label: 19.4
title: Finding Prime Numbers
pagenum: 546; label: 19.5
title: Chernoff Bounds
pagenum: 551; label: 19.6
title: Skip Lists
pagenum: 557; label: 19.7
title: Exercises
pagenum: 563; label: 20
title: B-Trees and External Memory
pagenum: 569; label: 20.1
title: External Memory
pagenum: 571; label: 20.2
title: (2,4) Trees and B-Trees
pagenum: 574; label: 20.3
title: External-Memory Sorting
pagenum: 590; label: 20.4
title: Online Caching Algorithms
pagenum: 593; label: 20.5
title: Exercises
pagenum: 600; label: 21
title: Multidimensional Searching
pagenum: 603; label: 21.1
title: Range Trees
pagenum: 605; label: 21.2
title: Priority Search Trees
pagenum: 609; label: 21.3
title: Quadtrees and k-d Trees
pagenum: 614; label: 21.4
title: Exercises
pagenum: 618; label: 22
title: Computational Geometry
pagenum: 623; label: 22.1
title: Operations on Geometric Objects
pagenum: 625; label: 22.2
title: Convex Hulls
pagenum: 630; label: 22.3
title: Segment Intersection
pagenum: 638; label: 22.4
title: Finding a Closest Pair of Points
pagenum: 642; label: 22.5
title: Exercises
pagenum: 646; label: 23
title: String Algorithms
pagenum: 651; label: 23.1
title: String Operations
pagenum: 653; label: 23.2
title: The Boyer-Moore Algorithm
pagenum: 656; label: 23.3
title: The Knuth-Morris-Pratt Algorithm
pagenum: 660; label: 23.4
title: Hash-Based Lexicon Matching
pagenum: 664; label: 23.5
title: Tries
pagenum: 669; label: 23.6
title: Exercises
pagenum: 680; label: 24
title: Cryptography
pagenum: 685; label: 24.1
title: Greatest Common Divisors (GCD)
pagenum: 687; label: 24.2
title: Modular Arithmetic
pagenum: 691; label: 24.3
title: Cryptographic Operations
pagenum: 699; label: 24.4
title: The RSA Cryptosystem
pagenum: 703; label: 24.5
title: The El Gamal Cryptosystem
pagenum: 706; label: 24.6
title: Exercises
pagenum: 708; label: 25
title: The Fast Fourier Transform
pagenum: 711; label: 25.1
title: Convolution
pagenum: 713; label: 25.2
title: Primitive Roots of Unity
pagenum: 715; label: 25.3
title: The Discrete Fourier Transform
pagenum: 717; label: 25.4
title: The Fast Fourier Transform Algorithm
pagenum: 721; label: 25.5
title: Exercises
pagenum: 727; label: 26
title: Linear Programming
pagenum: 731; label: 26.1
title: Formulating the Problem
pagenum: 734; label: 26.2
title: The Simplex Method
pagenum: 739; label: 26.3
title: Duality
pagenum: 746; label: 26.4
title: Applications of Linear Programming
pagenum: 750; label: 26.5
title: Exercises
pagenum: 753; label: A
title: Useful Mathematical Facts
pagenum: 761; title: Bibliography
pagenum: 765; title: Index
pagenum: 774