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

Data structures and algorithm analysis in C++

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 13, 2025 | History
Edit
An edition of Data structures and algorithm analysis in C (1993)

Data structures and algorithm analysis in C++

by

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

xv, 511 p. : 24 cm

Publish Date
Publisher
Benjamin/Cummings Pub. Co.
Language
English
Pages
498

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
1.4. C++ at a Glance
Page 12
1.4.1. A String Class
Page 14
1.4.2. A Complex Number Class
Page 21
Summary
Page 25
Exercises
Page 25
References
Page 26
2. Algorithm Analysis
Page 29
2.1. Mathematical Background
Page 29
2.2. Model
Page 32
2.3. What to Analyze
Page 32
2.4. Running Time Calculations
Page 34
2.4.1. A Simple Example
Page 35
2.4.2. General Rules
Page 36
2.4.3. Solutions for the Maximum Subsequence Sum Problem
Page 38
2.4.4. Logarithms in the Running Time
Page 43
2.4.5. Checking Your Analysis
Page 48
2.4.6. A Grain of Salt
Page 48
Summary
Page 48
Exercises
Page 50
References
Page 54
3. Lists, Stacks, and Queues
Page 57
3.1. Abstract Data Types (ADTs)
Page 57
3.2. The List ADT
Page 58
3.2.1. Simple Array Implementation of Lists
Page 59
3.2.2. Linked Lists
Page 59
3.2.3. Programming Details
Page 60
3.2.4. Common Errors
Page 69
3.2.5. Doubly and Circularly Linked Lists
Page 71
3.2.6. Sorted Linked Lists, Inheritance, and Virtual Functions
Page 71
3.2.7. Examples
Page 73
3.2.8. Cursor Implementation of Linked Lists
Page 80
3.3. The Stack ADT
Page 88
3.3.1. Stack Model
Page 88
3.3.2. Implementation of Stacks
Page 89
3.3.3. Applications
Page 96
3.4. The Queue ADT
Page 104
3.4.1. Queue Model
Page 104
3.4.2. Array Implementation of Queues
Page 105
3.4.3. Applications of Queues
Page 107
Summary
Page 110
Exercises
Page 111
4. Trees
Page 115
4.1. Preliminaries
Page 115
4.1.1. Implementation of Trees
Page 116
4.1.2. Tree Traversals with an Application
Page 117
4.2. Binary Trees
Page 121
4.2.1. Implementation
Page 122
4.2.2. Expression Trees
Page 123
4.3. The Search Tree ADT: Binary Search Trees
Page 126
4.3.1. Make_Empty
Page 129
4.3.2. Find
Page 130
4.3.3. Find_Min and Find_Max
Page 130
4.3.4. Insert
Page 131
4.3.5. Remove
Page 133
4.3.6. Average-Case Analysis
Page 135
4.4. AVL Trees
Page 137
4.4.1. Single Rotation
Page 139
4.4.2. Double Rotation
Page 141
4.5. Splay Trees
Page 150
4.5.1. A Simple Idea (That Does Not Work)
Page 150
4.5.2. Splaying
Page 153
4.6. Tree Traversals (Revisited)
Page 164
4.7. B-Trees
Page 165
Summary
Page 170
Exercises
Page 171
References
Page 177
5. Hashing
Page 181
5.1. General Idea
Page 181
5.2. Hash Function
Page 182
5.3. Open Hashing (Separate Chaining)
Page 184
5.4. Closed Hashing (Open Addressing)
Page 189
5.4.1. Linear Probing
Page 189
5.4.2. Quadratic Probing
Page 191
5.4.3. Double Hashing
Page 193
5.5. Rehashing
Page 198
5.6. Extendible Hashing
Page 200
Summary
Page 204
Exercises
Page 206
References
Page 208
6. Priority Queues (Heaps)
Page 211
6.1. Model
Page 211
6.2. Simple Implementations
Page 212
6.3. Binary Heap
Page 213
6.3.1. Structure Property
Page 213
6.3.2. Heap Order Property
Page 215
6.3.3. Basic Heap Operations
Page 216
6.3.4. Other Heap Operations
Page 220
6.4. Applications of Priority Queues
Page 223
6.4.1. The Selection Problem
Page 224
6.4.2. Event Simulation
Page 225
6.5. d-Heaps
Page 226
6.6. Leftist Heaps
Page 227
6.6.1. Leftist Heap Property
Page 227
6.6.2. Leftist Heap Operations
Page 228
6.7. Skew Heaps
Page 235
6.8. Binomial Queues
Page 237
6.8.1. Binomial Queue Structure
Page 237
6.8.2. Binomial Queue Operations
Page 237
6.8.3. Implementation of Binomial Queues
Page 242
Summary
Page 246
Exercises
Page 247
References
Page 251
7. Sorting
Page 253
7.1. Preliminaries
Page 253
7.2. Insertion Sort
Page 254
7.2.1. The Algorithm
Page 254
7.2.2. Analysis of Insertion Sort
Page 254
7.3. A Lower Bound for Simple Sorting Algorithms
Page 255
7.4. Shellsort
Page 256
7.4.1. Worst-Case Analysis of Shellsort
Page 258
7.5. Heapsort
Page 260
7.6. Mergesort
Page 262
7.6.1. Analysis of Mergesort
Page 265
7.7. Quicksort
Page 267
7.7.1. Picking the Pivot
Page 268
7.7.2. Partitioning Strategy
Page 270
7.7.3. Small Files
Page 272
7.7.4. Actual Quicksort Routines
Page 272
7.7.5. Analysis of Quicksort
Page 275
7.7.6. A Linear-Expected-Time Algorithm for Selection
Page 278
7.8. Sorting Large Objects
Page 280
7.9. A General Lower Bound for Sorting
Page 280
7.9.1. Decision Trees
Page 280
7.10. Bucket Sort
Page 283
7.11. External Sorting
Page 283
7.11.1. Why We Need New Algorithms
Page 284
7.11.2. Model for External Sorting
Page 284
7.11.3. The Simple Algorithm
Page 284
7.11.4. Multiway Merge
Page 286
7.11.5. Polyphase Merge
Page 287
7.11.6. Replacement Selection
Page 288
Summary
Page 289
Exercises
Page 290
References
Page 293
8. The Disjoint Set ADT
Page 297
8.1. Equivalence Relations
Page 297
8.2. The Dynamic Equivalence Problem
Page 298
8.3. Basic Data Structure
Page 299
8.4. Smart Union Algorithms
Page 303
8.5. Path Compression
Page 306
8.6. Worst Case for Union-by-Rank and Path Compression
Page 307
8.6.1. Analysis of the Union/Find Algorithm
Page 308
8.7. An Application
Page 314
Summary
Page 314
Exercises
Page 315
References
Page 316
9. Graph Algorithms
Page 319
9.1. Definitions
Page 319
9.1.1. Representation of Graphs
Page 320
9.2. Topological Sort
Page 322
9.3. Shortest-Path Algorithms
Page 326
9.3.1. Unweighted Shortest Paths
Page 327
9.3.2. Dijkstra's Algorithm
Page 333
9.3.3. Graphs with Negative Edge Costs
Page 340
9.3.4. Acyclic Graphs
Page 341
9.3.5. All-Pairs Shortest Path
Page 344
9.4. Network Flow Problems
Page 345
9.4.1. A Simple Maximum-Flow Algorithm
Page 345
9.5. Minimum Spanning Tree
Page 350
9.5.1. Prim's Algorithm
Page 350
9.5.2. Kruskal's Algorithm
Page 354
9.6. Applications of Depth-First Search
Page 356
9.6.1. Undirected Graphs
Page 357
9.6.2. Biconnectivity
Page 359
9.6.3. Euler Circuits
Page 363
9.6.4. Directed Graphs
Page 366
9.6.5. Finding Strong Components
Page 368
9.7. Introduction to NP-Completeness
Page 369
9.7.1. Easy vs. Hard
Page 370
9.7.2. The Class NP
Page 371
9.7.3. NP-Complete Problems
Page 372
Summary
Page 374
Exercises
Page 374
References
Page 380
10. Algorithm Design Techniques
Page 383
10.1. Greedy Algorithms
Page 383
10.1.1. A Simple Scheduling Problem
Page 384
10.1.2. Huffman Codes
Page 387
10.1.3. Approximate Bin Packing
Page 393
10.2. Divide and Conquer
Page 401
10.2.1. Running Time of Divide and Conquer Algorithms
Page 402
10.2.2. Closest-Points Problem
Page 404
10.2.3. The Selection Problem
Page 409
10.2.4. Theoretical Improvements for Arithmetic Problems
Page 412
10.3. Dynamic Programming
Page 416
10.3.1. Using a Table Instead of Recursion
Page 416
10.3.2. Ordering Matrix Multiplications
Page 419
10.3.3. Optimal Binary Search Tree
Page 422
10.3.4. All-Pairs Shortest Path
Page 425
10.4. Randomized Algorithms
Page 428
10.4.1. Random Number Generators
Page 429
10.4.2. Skip Lists
Page 433
10.4.3. Primality Testing
Page 436
10.5. Backtracking Algorithms
Page 438
10.5.1. The Turnpike Reconstruction Problem
Page 439
10.5.2. Games
Page 444
Summary
Page 450
Exercises
Page 451
References
Page 458
11. Amortized Analysis
Page 463
11.1. An Unrelated Puzzle
Page 464
11.2. Binomial Queues
Page 464
11.3. Skew Heaps
Page 469
11.4. Fibonacci Heaps
Page 471
11.4.1. Cutting Nodes in Leftist Heaps
Page 472
11.4.2. Lazy Merging for Binomial Queues
Page 474
11.4.3. The Fibonacci Heap Operations
Page 478
11.4.4. Proof of the Time Bound
Page 479
11.5. Splay Trees
Page 481
Summary
Page 485
Exercises
Page 486
References
Page 487
Index
Page 489

Edition Notes

Includes bibliographical references and index.

Published in
Redwood City, Calif

Classifications

Dewey Decimal Class
005.13/3
Library of Congress
QA76.73.C153 W46 1994

The Physical Object

Pagination
xiv, 498 p. :
Number of pages
498

Edition Identifiers

Open Library
OL1425988M
ISBN 10
0805354433
LCCN
93037035
LibraryThing
9163518
Goodreads
2276945

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 13, 2025 Edited by Drini Add TOC from Tocky
December 20, 2023 Edited by ImportBot import existing book
November 17, 2020 Edited by MARC Bot import existing book
September 8, 2020 Edited by ImportBot import existing book
April 1, 2008 Created by an anonymous user Imported from Scriblio MARC record