CART

(0) items

Data Structures and Algorithm Analysis in C++,9780201361223
This item qualifies for
FREE SHIPPING!
FREE SHIPPING OVER $59!

Your order must be $59 or more, you must select US Postal Service Shipping as your shipping preference, and the "Group my items into as few shipments as possible" option when you place your order.

Bulk sales, PO's, Marketplace Items, eBooks, Apparel, and DVDs not included.

Data Structures and Algorithm Analysis in C++

by
Edition:
3rd
ISBN13:

9780201361223

ISBN10:
0201361221
Format:
Hardcover
Pub. Date:
1/1/2007
Publisher(s):
Addison Wesley

Related Products


  • Data Structures and Algorithm Analysis in C++
    Data Structures and Algorithm Analysis in C++
  • Data Structures and Algorithm Analysis in C++
    Data Structures and Algorithm Analysis in C++
  • Data Structures And Algorithm Analysis in C++
    Data Structures And Algorithm Analysis in C++





Summary

In this text, readers are able to look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from several years to less than a second. Class templates are used to describe generic data structures and first-class versions of vector and string classes are used. Included is an appendix on a Standard Template Library (STL). This text is for readers who want to learn good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency. Readers should have some knowledge of intermediate programming, including topics as object-based programming and recursion, and some background in discrete math.

Table of Contents

Chapter 1 Introduction
1(40)
1.1. What's the Book About?
1(2)
1.2. Mathematics Review
3(4)
1.2.1. Exponents
3(1)
1.2.2. Logarithms
3(1)
1.2.3. Series
4(1)
1.2.4. Modular Arithmetic
5(1)
1.2.5. The P Word
5(2)
1.3. A Brief Introduction to Recursion
7(4)
1.4. C++ Classes
11(8)
1.4.1. Basic class Syntax
12(1)
1.4.2. Extra Constructor Syntax and Accessors
13(2)
1.4.3. Separation of Interface and Implementation
15(3)
1.4.4. vector and string
18(1)
1.5. C++ Details
19(11)
1.5.1. Pointers
19(2)
1.5.2. Parameter Passing
21(1)
1.5.3. Return Passing
22(1)
1.5.4. Reference Variables
23(1)
1.5.5. The Big Three: Destructor, Copy Constructor, operator=
23(5)
1.5.6. The World of C
28(2)
1.6. Templates
30(6)
1.6.1. Function Templates
30(2)
1.6.2. Class Templates
32(2)
1.6.3. Object, Comparable, and an Example
34(2)
1.7. Using Matrices
36(1)
1.7.1. The Data Members, Constructor, and Basic Accessors
36(1)
1.7.2. Operator[]
36(1)
1.7.3. Destructor, Copy Assignment, Copy Constructor
37(1)
Summary
37(1)
Exercises
37(2)
References
39(2)
Chapter 2 Algorithm Analysis
41(28)
2.1. Mathematical Background
41(3)
2.2. Model
44(1)
2.3. What to Analyze
44(3)
2.4. Running Time Calculations
47(14)
2.4.1. A Simple Example
47(1)
2.4.2. General Rules
48(2)
2.4.3. Solutions for the Maximum Subsequence Sum Problem
50(6)
2.4.4. Logarithms in the Running Time
56(3)
2.4.5. Checking Your Analysis
59(2)
2.4.6. A Grain of Salt
61(1)
Summary
61(1)
Exercises
62(5)
References
67(2)
Chapter 3 Lists, Stacks, and Queues
69(52)
3.1. Abstract Data Types (ADTs)
69(1)
3.2. The List ADT
70(23)
3.2.1. Simple Array Implementation of Lists
70(1)
3.2.2. Linked Lists
71(1)
3.2.3. Programming Details
72(6)
3.2.4. Memory Reclamation and the Big Three
78(1)
3.2.5. Doubly Linked Lists
79(1)
3.2.6. Circular Linked Lists
80(1)
3.2.7. Examples
81(5)
3.2.8. Cursor Implementation of Linked Lists
86(7)
3.3. The Stack ADT
93(17)
3.3.1. Stack Model
93(1)
3.3.2. Implementation of Stacks
93(1)
3.3.3. Applications
100(10)
3.4. The Queue ADT
110(5)
3.4.1. Queue Model
110(1)
3.4.2. Array Implementation of Queues
110(4)
3.4.3. Applications of Queues
114(1)
Summary
115(1)
Exercises
116(5)
Chapter 4 Trees
121(60)
4.1. Preliminaries
121(6)
4.1.1. Implementation of Trees
122(1)
4.1.2. Tree Traversals with and Application
123(4)
4.2. Binary Trees
127(4)
4.2.1. Implementation
127(1)
4.2.2. An Example: Expression Trees
128(3)
4.3. The Search Tree ADT-Binary Search Trees
131(12)
4.3.1. find
134(1)
4.3.2. findMin and findMax
134(2)
4.3.3. insert
136(1)
4.3.4. remove
137(2)
4.3.5. Destructor and Copy Assignment Operator
139(1)
4.3.6. Average-Case Analysis
140(3)
4.4. AVL Trees
143(12)
4.4.1. Single Rotation
145(3)
4.4.2. Double Rotation
148(7)
4.5. Splay Trees
155(8)
4.5.1. A Simple Idea (That Does Not Work)
155(2)
4.5.2. Splaying
157(6)
4.6. Tree Traversals (Revisited)
163(2)
4.7. B-Trees
165(5)
Summary
170(1)
Exercises
170(7)
References
177(4)
Chapter 5 Hashing
181(30)
5.1. General Idea
181(1)
5.2. Hash Function
182(2)
5.3. Separate Chaining
184(4)
5.4. Open Addressing
188(9)
5.4.1. Linear Probing
189(2)
5.4.2. Quadratic Probing
191(5)
5.4.3. Double Hashing
196(1)
5.5. Rehashing
197(3)
5.6. Extendible Hashing
200(3)
Summary
203(1)
Exercises
204(3)
References
207(4)
Chapter 6 Priority Queues (Heaps)
211(42)
6.1. Model
211(1)
6.2. Simple Implementations
212(1)
6.3. Binary Heap
213(10)
6.3.1. Structure Property
213(1)
6.3.2. Heap-Order Property
214(1)
6.3.3. Basic Heap Operations
215(4)
6.3.4. Other Heap Operations
219(4)
6.4. Applications of Priority Queues
223(2)
6.4.1. The Selection Problem
223(1)
6.4.2. Event Simulation
224(1)
6.5. d-Heaps
225(1)
6.6. Leftist Heaps
226(7)
6.6.1. Leftist Heap Property
226(1)
6.6.2. Leftist Heap Operations
227(6)
6.7. Skew Heaps
233(3)
6.8. Binomial Queues
236(10)
6.8.1. Binomial Queue Structure
236(1)
6.8.2. Binomial Queue Operations
237(3)
6.8.3. Implementation of Binomial Queues
240(6)
Summary
246(1)
Exercises
246(5)
References
251(2)
Chapter 7 Sorting
253(50)
7.1. Preliminaries
253(1)
7.2. Insertion Sort
254(1)
7.2.1. The Algorithm
254(1)
7.2.2. Analysis of Insertion Sort
254(1)
7.3. A Lower Bound for Simple Sorting Algorithms
255(1)
7.4. Shellsort
256(4)
7.4.1. Worst-Case Analysis of Shellsort
257(3)
7.5. Heapsort
260(4)
7.5.1. Analysis of Heapsort
263(1)
7.6. Mergesort
264(5)
7.6.1. Analysis of Mergesort
266(3)
7.7. Quicksort
269(12)
7.7.1. Picking the Pivot
271(1)
7.7.2. Partitioning Strategy
271(3)
7.7.3. Small Arrays
274(1)
7.7.4. Actual Quicksort Routines
274(1)
7.7.5. Analysis of Quicksort
275(4)
7.7.6. A Linear-Expected-Time Algorithm for Selection
279(2)
7.8. Indirect Sorting
281(5)
7.8.1. vector [Comparable *] Does Not Work
283(1)
7.8.2. Smart Pointer Class
283(1)
7.8.3. Overloading operator (XXX)
284(1)
7.8.4. Dereferencing a Pointer with *
284(1)
7.8.5. Overloading the Type Conversion Operator
284(1)
7.8.6. Implicit Type Conversions Are Everywhere
285(1)
7.8.7. Dual-Direction Implicit Conversions Can Cause Ambiguities
285(1)
7.8.8. Pointer Subtraction Is Legal
286(1)
7.9. A General Lower Bound for Sorting
286(2)
7.9.1. Decision Trees
286(2)
7.10. Bucket Sort
288(1)
7.11. External Sorting
289(5)
7.11.1. Why We Need New Algorithms
289(1)
7.11.2. Model for External Sorting
289(1)
7.11.3. The Simple Algorithm
290(1)
7.11.4. Multiway Merge
291(1)
7.11.5. Polyphase Merge
292(1)
7.11.6. Replacement Selection
293(1)
Summary
294(1)
Exercises
295(5)
References
300(3)
Chapter 8 The Disjoint Set ADT
303(24)
8.1. Equivalence Relations
303(1)
8.2. The Dynamic Equivalence Problem
304(2)
8.3. Basic Data Structure
306(3)
8.4. Smart Union Algorithms
309(3)
8.5. Path Compression
312(1)
8.6. Worst Case for Union-by-Rank and Path Compression
313(7)
8.6.1. Analysis of the Union/Find Algorithm
314(6)
8.7. An Application
320(2)
Summary
322(1)
Exercises
322(2)
References
324(3)
Chapter 9 Graph Algorithms
327(64)
9.1. Definitions
327(3)
9.1.1. Representation of Graphs
328(2)
9.2. Topological Sort
330(3)
9.3. Shortest-Path Algorithms
333(18)
9.3.1. Unweighted Shortest Paths
335(4)
9.3.2. Dijkstra's Algorithm
339(8)
9.3.3. Graphs with Negative Edge Costs
347(1)
9.3.4. Acyclic Graphs
348(3)
9.3.5. All-Pairs Shortest Path
351(1)
9.4. Network Flow Problems
351(5)
9.4.1. A Simple Maximum-Flow Algorithm
352(4)
9.5. Minimum Spanning Tree
356(6)
9.5.1. Prim's Algorithm
356(4)
9.5.2. Kruskal's Algorithm
360(2)
9.6. Applications of Depth-First Search
362(12)
9.6.1. Undirected Graphs
362(1)
9.6.2. Biconnectivity
363(5)
9.6.3. Euler Circuits
368(3)
9.6.4. Directed Graphs
371(2)
9.6.5. Finding Strong Components
373(1)
9.7. Introduction to NP-Completeness
374(5)
9.7.1. Easy vs. Hard
375(1)
9.7.2. The Class NP
376(1)
9.7.3. NP-Complete Problems
377(2)
Summary
379(1)
Exercises
379(7)
References
386(5)
Chapter 10 Algorithm Design Techniques
391(78)
10.1. Greedy Algorithms
391(18)
10.1.1. A Simple Scheduling Problem
392(3)
10.1.2. Huffman Codes
395(6)
10.1.3. Approximate Bin Packing
401(8)
10.2. Divide and Conquer
409(14)
10.2.1. Running Time of Divide and Conquer Algorithms
410(2)
10.2.2. Closest-Points Problem
412(4)
10.2.3. The Selection Problem
416(3)
10.2.4. Theoretical Improvements for Arithmetic Problems
419(4)
10.3. Dynamic Programming
423(11)
10.3.1. Using a Table Instead of Recursion
423(2)
10.3.2. Ordering Matrix Multiplications
425(4)
10.3.3. Optimal Binary Search Tree
429(3)
10.3.4. All-Pairs Shortest Path
432(2)
10.4. Randomized Algorithms
434(10)
10.4.1. Random Number Generators
436(4)
10.4.2. Skip Lists
440(2)
10.4.3. Primality Testing
442(2)
10.5. Backtracking Algorithms
444(11)
10.5.1. The Turnpike Reconstruction Problem
445(4)
10.5.2. Games
449(6)
Summary
455(1)
Exercises
455(9)
References
464(5)
Chapter 11 Amortized Analysis
469(26)
11.1. An Unrelated Puzzle
470(1)
11.2. Binomial Queues
470(5)
11.3. Skew Heaps
475(2)
11.4. Fibonacci Heaps
477(10)
11.4.1. Cutting Nodes in Leftist Heaps
478(3)
11.4.2. Lazy Merging for Binomial Queues
481(3)
11.4.3. The Fibonacci Heap Operations
484(1)
11.4.4. Proof of the Time Bound
485(2)
11.5. Splay Trees
487(4)
Summary
491(1)
Exercises
491(2)
References
493(2)
Chapter 12 Advanced Data Structures and Implementation
495(48)
12.1. Top-Down Splay Trees
495(8)
12.2. Red-Black Trees
503(9)
12.2.1. Bottom-Up Insertion
503(2)
12.2.2. Top-Down Red-Black Trees
505(1)
12.2.3. Top-Down Deletion
506(6)
12.3. Deterministic Skip Lists
512(6)
12.4. AA-Trees
518(6)
12.5. Treaps
524(3)
12.6. k-d Trees
527(3)
12.7. Pairing Heaps
530(6)
Summary
536(1)
Exercises
536(4)
References
540(3)
Appendix A The Standard Template Library
543(24)
A.1. Introduction
543(1)
A.2. Basic STL Concepts
544(3)
A.2.1. Header Files and the using Directive
544(1)
A.2.2. Containers
544(1)
A.2.3. iterator
545(1)
A.2.4. Pairs
546(1)
A.2.5. Function Objects
546(1)
A.3. Unordered Sequences: vector and list
547(3)
A.3.1. vector versus list
547(2)
A.3.2. Stacks and Queues
549(1)
A.4. Sets
550(1)
A.5. Maps
551(1)
A.6. Example: Generating a Concordance
552(5)
A.6.1. STL Version
552(2)
A.6.2. Version without Using the STL
554(3)
A.7. Example: Shortest-Path Calculation
557(9)
A.7.1. STL Implementation
557(3)
A.7.2. Version without Using the STL
560(6)
A.8. Other STL Features
566(1)
Appendix B vector and string Classes
567(10)
B.1. First-Class versus Second-Class Objects
567(1)
B.2. vector Class
567(3)
B.3. String Class
570(7)
Index 577

Excerpts

Purpose/Goals The second edition of Data Structures and Algorithms Analysis in C++ describes data structures, methods of organizing large amounts of data, and algorithm analysis, the estimation of the running time of algorithms. As computers become faster and faster, the need for programs that can handle large amounts of input becomes more acute. Paradoxically, this requires more careful attention to efficiency, since inefficiencies in programs become most obvious when input sizes are large. By analyzing an algorithm before it Is actually coded, students can decide if a particular solution will be feasible. For example, in this text students look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from 16 years to less than a second. Therefore, no algorithm or data structure is presented without an explanation of its running time. In some cases, minute details that affect the running time of the implementation are explored. Once a solution method is determined, a program must still be written. As computers have become more powerful, the problems they must solve have become larger and more complex, requiring development of more intricate programs. The goal of this text is to teach students good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency. This book is suitable for either an advanced data structures (CS7) course or a first-year graduate course in algorithm analysis. Students should have some knowledge of intermediate programming, including such topics as pointers, recursion, and object-based programming, and some background in discrete math. Approach Although the material in this text is largely language independent, programming requires the use of a specific language. As the title implies, we have chosen C++ for this book. C++ has emerged as the leading systems programming language. In addition to fixing many of the syntactic flaws of C, C++ provides direct constructs (theclassandtemplate) to implement generic data structures as abstract data types. The most difficult part of writing the book was deciding on the amount of C++ to include. Use too many features of C++, and one gets an incomprehensible text; use too few and you have little more than a C text that supports classes. The approach we take is to present the material in anobject-based approach.As such, unlike the first edition, there is no use of inheritance in the text. We use class templates to describe generic data structures. We generally avoid esoteric C++ features, and use the vector and string classes that are now part of the C++ standard. Using these first-class versions, instead of the second-class counterparts that were used in the first edition, simplifies much of the code. Because not all compilers are current, we provide a vector and string class in Appendix B; this is the class that is actually used in the online code. Chapter 1 provides a review of the C++ features that are used throughout the text. Complete versions of the data structures, in both C++ and Java, are available on the Internet. We use similar coding conventions to make the parallels between the two languages more evident. The code has been tested on UNIX systems using g++ (2.7.2 and 2.8.1) and SunPro 4.0 and on Windows95 systems using Visual C++ 5.0 and 6.0, Borland C++ 5.0, and Codewarrior Pro Release 2. Overview Chapter 1 contains review material on discrete math and recursion. I believe the only way to be comfortable with recursion is to see good uses over and over. Therefore, recursion is prevalent in this text, with examples in every chapter except Chapter 5. Chapter I also includes material that serves as a review of basic C++. Included is a discussion of templates and important constructs in C++ c


Please wait while the item is added to your cart...