An edition of Data structures and algorithm analysis in C (1993)

Data structures and algorithm analysis in C

2nd ed.

by

  • ★★★ ★ 3.7 (3 ratings)
  • 39 Want to read
  • 7 Currently reading
  • 4 Have read
Cover of: Data structures and algorithm analysis in C by Mark Allen Weiss, Mark Allen Weiss
Preview Only

My Reading Lists:

Create a new list
Notes
  • ★★★ ★ 3.7 (3 ratings)
  • 39 Want to read
  • 7 Currently reading
  • 4 Have read
Notes

Check nearby libraries

Buy this book

Last edited by Drini
September 15, 2025 | History
Edit
An edition of Data structures and algorithm analysis in C (1993)

Data structures and algorithm analysis in C

2nd ed.

by

  • ★★★ ★ 3.7 (3 ratings)
  • 39 Want to read
  • 7 Currently reading
  • 4 Have read

xv, 511 p. : 24 cm

Publish Date
Publisher
Addison-Wesley, Addison Wesley
Language
English
Pages
511

Check nearby libraries

Buy this book

Previews available in: English

Subjects

Data structures (Computer science), Computer algorithms, C++ (Computer program language), C (Computer program language), C plus plus (computer program language), Algoritmus (számítógépes), Programozási nyelv, Data structures, Adatszerkezetek (számítógéptudomány), C++, Algorithms (Computer science), C (Computer program language), Computers & the internet, Programming
Edition Availability
Cover of: Data structures and algorithm analysis in C++
Data structures and algorithm analysis in C++
2005, Pearson Addison-Wesley
in English - 3rd ed.
Cover of: Data structures & algorithm analysis in C++
Data structures & algorithm analysis in C++
1999, Addison Wesley
in English - 2nd ed.
Cover of: Data structures and algorithm analysis in C
Data structures and algorithm analysis in C
1997, Addison-Wesley, Addison Wesley
in English - 2nd ed.
Cover of: Data structures and algorithm analysis in C
Data structures and algorithm analysis in C
1997, Addison-Wesley
in English - 2nd ed., international edition.
Cover of: Data structures and algorithm analysis in C++
Data structures and algorithm analysis in C++
1994, Benjamin/Cummings Pub. Co.
in English
Cover of: Data structures and algorithm analysis in C [plus plus]
Data structures and algorithm analysis in C [plus plus]
1994, Benjamin/Cummings
in English
Cover of: Data structures and algorithm analysis in C
Data structures and algorithm analysis in C
1993, Benjamin/Cummings Pub. Co.
in English

Add another edition?

Book Details

Table of Contents

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

Edition Notes

Includes bibliographical references and index.

Published in
Menlo Park, Calif

Classifications

Dewey Decimal Class
005.7/3
Library of Congress
QA76.73.C15 W463 1997, QA76.73.C15W463 1997

The Physical Object

Pagination
xv, 511 p. :
Number of pages
511

Edition Identifiers

Open Library
OL986206M
ISBN 10
0201498405
LCCN
96024281
OCLC/WorldCat
34772348
LibraryThing
311410
Goodreads
27851

Work Identifiers

Work ID
OL1958940W

Source records

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Loading indicator
Loading carousel
Loading indicator
Loading carousel

History

Download catalog record: RDF / JSON / OPDS | Wikipedia citation
September 15, 2025 Edited by Drini Add TOC from Tocky
July 9, 2025 Edited by MARC Bot import existing book
August 7, 2024 Edited by MARC Bot import existing book
December 19, 2023 Edited by ImportBot import existing book
April 1, 2008 Created by an anonymous user Imported from Scriblio MARC record