Data structures and algorithm analysis in C
By: Mark Allen Weiss.
Edition: 2nd ed.
Publisher: Addison-Wesley; Addison Wesley
Published: 1997
Place of publication: Menlo Park, Calif
Language: eng
Number of pages: 511
Subjects: C (Computer program language); Data structures (Computer science); Computer algorithms.
Description: xv, 511 p. : 24 cm
Notes: Includes bibliographical references and index.
Table of contents: label: 1
title: Introduction
pagenum: 1; label: 1.1
title: What's the Book About?
pagenum: 1; label: 1.2
title: Mathematics Review
pagenum: 3; label: 1.2.1
title: Exponents
pagenum: 3; label: 1.2.2
title: Logarithms
pagenum: 3; label: 1.2.3
title: Series
pagenum: 4; label: 1.2.4
title: Modular Arithmetic
pagenum: 5; label: 1.2.5
title: The P Word
pagenum: 6; label: 1.3
title: A Brief Introduction to Recursion
pagenum: 8; title: Summary
pagenum: 12; title: Exercises
pagenum: 12; title: References
pagenum: 13; label: 2
title: Algorithm Analysis
pagenum: 15; label: 2.1
title: Mathematical Background
pagenum: 15; label: 2.2
title: Model
pagenum: 18; label: 2.3
title: What to Analyze
pagenum: 18; label: 2.4
title: Running Time Calculations
pagenum: 20; label: 2.4.1
title: A Simple Example
pagenum: 21; label: 2.4.2
title: General Rules
pagenum: 21; label: 2.4.3
title: Solutions for the Maximum Subsequence Sum Problem
pagenum: 24; label: 2.4.4
title: Logarithms in the Running Time
pagenum: 28; label: 2.4.5
title: Checking Your Analysis
pagenum: 33; label: 2.4.6
title: A Grain of Salt
pagenum: 33; title: Summary
pagenum: 34; title: Exercises
pagenum: 35; title: References
pagenum: 39; label: 3
title: Lists, Stacks, and Queues
pagenum: 41; label: 3.1
title: Abstract Data Types (ADTs)
pagenum: 41; label: 3.2
title: The List ADT
pagenum: 42; label: 3.2.1
title: Simple Array Implementation of Lists
pagenum: 43; label: 3.2.2
title: Linked Lists
pagenum: 43; label: 3.2.3
title: Programming Details
pagenum: 44; label: 3.2.4
title: Common Errors
pagenum: 49; label: 3.2.5
title: Doubly Linked Lists
pagenum: 51; label: 3.2.6
title: Circularly Linked Lists
pagenum: 52; label: 3.2.7
title: Examples
pagenum: 52; label: 3.2.8
title: Cursor Implementation of Linked Lists
pagenum: 57; label: 3.3
title: The Stack ADT
pagenum: 62; label: 3.3.1
title: Stack Model
pagenum: 62; label: 3.3.2
title: Implementation of Stacks
pagenum: 63; label: 3.3.3
title: Applications
pagenum: 71; label: 3.4
title: The Queue ADT
pagenum: 79; label: 3.4.1
title: Queue Model
pagenum: 79; label: 3.4.2
title: Array Implementation of Queues
pagenum: 79; label: 3.4.3
title: Applications of Queues
pagenum: 84; title: Summary
pagenum: 85; title: Exercises
pagenum: 85; label: 4
title: Trees
pagenum: 89; label: 4.1
title: Preliminaries
pagenum: 89; label: 4.1.1
title: Implementation of Trees
pagenum: 90; label: 4.1.2
title: Tree Traversals with an Application
pagenum: 91; label: 4.2
title: Binary Trees
pagenum: 95; label: 4.2.1
title: Implementation
pagenum: 96; label: 4.2.2
title: Expression Trees
pagenum: 97; label: 4.3
title: The Search Tree ADT — Binary Search Trees
pagenum: 100; label: 4.3.1
title: MakeEmpty
pagenum: 101; label: 4.3.2
title: Find
pagenum: 101; label: 4.3.3
title: FindMin and FindMax
pagenum: 103; label: 4.3.4
title: Insert
pagenum: 104; label: 4.3.5
title: Delete
pagenum: 105; label: 4.3.6
title: Average-Case Analysis
pagenum: 107; label: 4.4
title: AVL Trees
pagenum: 110; label: 4.4.1
title: Single Rotation
pagenum: 112; label: 4.4.2
title: Double Rotation
pagenum: 115; label: 4.5
title: Splay Trees
pagenum: 123; label: 4.5.1
title: A Simple Idea (That Does Not Work)
pagenum: 124; label: 4.5.2
title: Splaying
pagenum: 126; label: 4.6
title: Tree Traversals (Revisited)
pagenum: 132; label: 4.7
title: B-Trees
pagenum: 133; title: Summary
pagenum: 138; title: Exercises
pagenum: 139; title: References
pagenum: 146; label: 5
title: Hashing
pagenum: 149; label: 5.1
title: General Idea
pagenum: 149; label: 5.2
title: Hash Function
pagenum: 150; label: 5.3
title: Separate Chaining
pagenum: 152; label: 5.4
title: Open Addressing
pagenum: 157; label: 5.4.1
title: Linear Probing
pagenum: 157; label: 5.4.2
title: Quadratic Probing
pagenum: 160; label: 5.4.3
title: Double Hashing
pagenum: 164; label: 5.5
title: Rehashing
pagenum: 165; label: 5.6
title: Extendible Hashing
pagenum: 168; title: Summary
pagenum: 171; title: Exercises
pagenum: 172; title: References
pagenum: 175; label: 6
title: Priority Queues (Heaps)
pagenum: 177; label: 6.1
title: Model
pagenum: 177; label: 6.2
title: Simple Implementations
pagenum: 178; label: 6.3
title: Binary Heap
pagenum: 179; label: 6.3.1
title: Structure Property
pagenum: 179; label: 6.3.2
title: Heap Order Property
pagenum: 180; label: 6.3.3
title: Basic Heap Operations
pagenum: 182; label: 6.3.4
title: Other Heap Operations
pagenum: 186; label: 6.4
title: Applications of Priority Queues
pagenum: 189; label: 6.4.1
title: The Selection Problem
pagenum: 189; label: 6.4.2
title: Event Simulation
pagenum: 191; label: 6.5
title: d-Heaps
pagenum: 192; label: 6.6
title: Leftist Heaps
pagenum: 193; label: 6.6.1
title: Leftist Heap Property
pagenum: 193; label: 6.6.2
title: Leftist Heap Operations
pagenum: 194; label: 6.7
title: Skew Heaps
pagenum: 200; label: 6.8
title: Binomial Queues
pagenum: 202; label: 6.8.1
title: Binomial Queue Structure
pagenum: 202; label: 6.8.2
title: Binomial Queue Operations
pagenum: 204; label: 6.8.3
title: Implementation of Binomial Queues
pagenum: 205; title: Summary
pagenum: 212; title: Exercises
pagenum: 212; title: References
pagenum: 216; label: 7
title: Sorting
pagenum: 219; label: 7.1
title: Preliminaries
pagenum: 219; label: 7.2
title: Insertion Sort
pagenum: 220; label: 7.2.1
title: The Algorithm
pagenum: 220; label: 7.2.2
title: Analysis of Insertion Sort
pagenum: 221; label: 7.3
title: A Lower Bound for Simple Sorting Algorithms
pagenum: 221; label: 7.4
title: Shellsort
pagenum: 222; label: 7.4.1
title: Worst-Case Analysis of Shellsort
pagenum: 224; label: 7.5
title: Heapsort
pagenum: 226; label: 7.5.1
title: Analysis of Heapsort
pagenum: 228; label: 7.6
title: Mergesort
pagenum: 230; label: 7.6.1
title: Analysis of Mergesort
pagenum: 232; label: 7.7
title: Quicksort
pagenum: 235; label: 7.7.1
title: Picking the Pivot
pagenum: 236; label: 7.7.2
title: Partitioning Strategy
pagenum: 237; label: 7.7.3
title: Small Arrays
pagenum: 240; label: 7.7.4
title: Actual Quicksort Routines
pagenum: 240; label: 7.7.5
title: Analysis of Quicksort
pagenum: 241; label: 7.7.6
title: A Linear-Expected-Time Algorithm for Selection
pagenum: 245; label: 7.8
title: Sorting Large Structures
pagenum: 247; label: 7.9
title: A General Lower Bound for Sorting
pagenum: 247; label: 7.9.1
title: Decision Trees
pagenum: 247; label: 7.10
title: Bucket Sort
pagenum: 250; label: 7.11
title: External Sorting
pagenum: 250; label: 7.11.1
title: Why We Need New Algorithms
pagenum: 251; label: 7.11.2
title: Model for External Sorting
pagenum: 251; label: 7.11.3
title: The Simple Algorithm
pagenum: 251; label: 7.11.4
title: Multiway Merge
pagenum: 253; label: 7.11.5
title: Polyphase Merge
pagenum: 254; label: 7.11.6
title: Replacement Selection
pagenum: 255; title: Summary
pagenum: 256; title: Exercises
pagenum: 257; title: References
pagenum: 261; label: 8
title: The Disjoint Set ADT
pagenum: 263; label: 8.1
title: Equivalence Relations
pagenum: 263; label: 8.2
title: The Dynamic Equivalence Problem
pagenum: 264; label: 8.3
title: Basic Data Structure
pagenum: 265; label: 8.4
title: Smart Union Algorithms
pagenum: 269; label: 8.5
title: Path Compression
pagenum: 271; label: 8.6
title: Worst Case for Union-by-Rank and Path Compression
pagenum: 273; label: 8.6.1
title: Analysis of the Union/Find Algorithm
pagenum: 273; label: 8.7
title: An Application
pagenum: 279; title: Summary
pagenum: 279; title: Exercises
pagenum: 280; title: References
pagenum: 281; label: 9
title: Graph Algorithms
pagenum: 283; label: 9.1
title: Definitions
pagenum: 283; label: 9.1.1
title: Representation of Graphs
pagenum: 284; label: 9.2
title: Topological Sort
pagenum: 286; label: 9.3
title: Shortest-Path Algorithms
pagenum: 290; label: 9.3.1
title: Unweighted Shortest Paths
pagenum: 291; label: 9.3.2
title: Dijkstra's Algorithm
pagenum: 295; label: 9.3.3
title: Graphs with Negative Edge Costs
pagenum: 304; label: 9.3.4
title: Acyclic Graphs
pagenum: 305; label: 9.3.5
title: All-Pairs Shortest Path
pagenum: 308; label: 9.4
title: Network Flow Problems
pagenum: 308; label: 9.4.1
title: A Simple Maximum-Flow Algorithm
pagenum: 309; label: 9.5
title: Minimum Spanning Tree
pagenum: 313; label: 9.5.1
title: Prim's Algorithm
pagenum: 314; label: 9.5.2
title: Kruskal's Algorithm
pagenum: 316; label: 9.6
title: Applications of Depth-First Search
pagenum: 319; label: 9.6.1
title: Undirected Graphs
pagenum: 320; label: 9.6.2
title: Biconnectivity
pagenum: 322; label: 9.6.3
title: Euler Circuits
pagenum: 326; label: 9.6.4
title: Directed Graphs
pagenum: 329; label: 9.6.5
title: Finding Strong Components
pagenum: 331; label: 9.7
title: Introduction to NP-Completeness
pagenum: 332; label: 9.7.1
title: Easy vs. Hard
pagenum: 333; label: 9.7.2
title: The Class NP
pagenum: 334; label: 9.7.3
title: NP-Complete Problems
pagenum: 335; title: Summary
pagenum: 337; title: Exercises
pagenum: 337; title: References
pagenum: 343; label: 10
title: Algorithm Design Techniques
pagenum: 347; label: 10.1
title: Greedy Algorithms
pagenum: 347; label: 10.1.1
title: A Simple Scheduling Problem
pagenum: 348; label: 10.1.2
title: Huffman Codes
pagenum: 351; label: 10.1.3
title: Approximate Bin Packing
pagenum: 357; label: 10.2
title: Divide and Conquer
pagenum: 365; label: 10.2.1
title: Running Time of Divide and Conquer Algorithms
pagenum: 366; label: 10.2.2
title: Closest-Points Problem
pagenum: 368; label: 10.2.3
title: The Selection Problem
pagenum: 373; label: 10.2.4
title: Theoretical Improvements for Arithmetic Problems
pagenum: 376; label: 10.3
title: Dynamic Programming
pagenum: 380; label: 10.3.1
title: Using a Table Instead of Recursion
pagenum: 380; label: 10.3.2
title: Ordering Matrix Multiplications
pagenum: 383; label: 10.3.3
title: Optimal Binary Search Tree
pagenum: 387; label: 10.3.4
title: All-Pairs Shortest Path
pagenum: 390; label: 10.4
title: Randomized Algorithms
pagenum: 392; label: 10.4.1
title: Random Number Generators
pagenum: 394; label: 10.4.2
title: Skip Lists
pagenum: 397; label: 10.4.3
title: Primality Testing
pagenum: 399; label: 10.5
title: Backtracking Algorithms
pagenum: 401; label: 10.5.1
title: The Turnpike Reconstruction Problem
pagenum: 403; label: 10.5.2
title: Games
pagenum: 407; title: Summary
pagenum: 413; title: Exercises
pagenum: 415; title: References
pagenum: 422; label: 11
title: Amortized Analysis
pagenum: 427; label: 11.1
title: An Unrelated Puzzle
pagenum: 428; label: 11.2
title: Binomial Queues
pagenum: 428; label: 11.3
title: Skew Heaps
pagenum: 433; label: 11.4
title: Fibonacci Heaps
pagenum: 435; label: 11.4.1
title: Cutting Nodes in Leftist Heaps
pagenum: 436; label: 11.4.2
title: Lazy Merging for Binomial Queues
pagenum: 439; label: 11.4.3
title: The Fibonacci Heap Operations
pagenum: 442; label: 11.4.4
title: Proof of the Time Bound
pagenum: 443; label: 11.5
title: Splay Trees
pagenum: 445; title: Summary
pagenum: 449; title: Exercises
pagenum: 450; title: References
pagenum: 451; label: 12
title: Advanced Data Structures and Implementation
pagenum: 453; label: 12.1
title: Top-Down Splay Trees
pagenum: 453; label: 12.2
title: Red Black Trees
pagenum: 457; label: 12.2.1
title: Bottom-Up Insertion
pagenum: 462; label: 12.2.2
title: Top-Down Red Black Trees
pagenum: 463; label: 12.2.3
title: Top-Down Deletion
pagenum: 465; label: 12.3
title: Deterministic Skip Lists
pagenum: 469; label: 12.4
title: AA-Trees
pagenum: 476; label: 12.5
title: Treaps
pagenum: 482; label: 12.6
title: k-d Trees
pagenum: 485; label: 12.7
title: Pairing Heaps
pagenum: 488; title: Summary
pagenum: 494; title: Exercises
pagenum: 495; title: References
pagenum: 497; title: Index
pagenum: 501