 Shopping Bag ( 0 items )

All (17) from $1.99

Used (17) from $1.99
Ships from: Toledo, OH
Usually ships in 12 business days
Ships from: North Adams, MI
Usually ships in 12 business days
Ships from: GoringBySea, United Kingdom
Usually ships in 12 business days
Ships from: Chatham, NJ
Usually ships in 12 business days
Ships from: Chatham, NJ
Usually ships in 12 business days
Ships from: Chatham, NJ
Usually ships in 12 business days
Ships from: Berlin, Germany
Usually ships in 12 business days
From a prominent expert in algorithm efficiency, this book discusses the use of modern data structures with a keen eye for issues of performance and running time. Abundant examples demonstrate the power and breadth of the C language in the hands of an experienced C programmer. The concepts behind data structures are illustrated with many diagrams and illustrations.
This book 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 firstyear graduate course in algorithm analysis. Students should have some knowledge of intermediate programming, including such topics as pointers and recursion, and some background in discrete math.
I believe it isimportant for students to learn how to program for themselves, not how to copy programs from a book. On the other hand, it is virtually impossible to discuss realistic programming issues without including sample code. For this reason, the book usually provides about onehalf to threequarters of an implementation, and the student is encouraged to supply the rest. Chapter 12, which is new to this edition, discusses additional data structures with an emphasis on implementation details.
The algorithms in this book are presented in ANSI C, which, despite some flaws, is arguably the most popular systems programming language. The use of C instead of Pascal allows the use of dynamically allocated arrays (see, for instance, rehashing in Chapter 5). It also produces simplified code in several places, usually because the and (&&) operations is shortcircuited.
Most criticisms of C center on the fact that it is easy to write code that is barely readable. Some of the more standard tricks, such as the simultaneous assignment and testing against 0 via
if (x=y)
are generally not used in the text, since the loss of clarity is compensated by only a few keystrokes and no increased speed. I believe that this books demonstrates that unreadable code can be avoided by exercising reasonable care.
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 2 deals with algorithm analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an indepth explanation of logarithms running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divideandconquer programs are introduced, but some of the analysis (solving recurrence relations) is implicitly delayed until Chapter 7, where it is performed in detail.
Chapter 3 covers lists, stacks, and queues. The emphasis here is on coding these data structures using ADTs, fast implementation of these data structures, and an exposition of some of their uses. There are almost no programs (just routines), but the exercises contain plenty of ideas for programming assignments.
Chapter 4 covers trees, with an emphasis on search trees, including external search trees (Btrees). The UNIX file system and expression trees are used as examples. AVL trees and splay trees are introduced but not analyzed. Seventyfive percent of the code is written, leaving similar cases to be completed by the student. More careful treatment of search tree implementation details is found in Chapter 12. Additional coverage of trees, such as file compression and game trees, is deferred until Chapter 10. Data structures for an external medium are considered as the final topic in several chapters.
Chapter 5 is relatively short chapter concerning hash tables. Some analysis is performed, and extendible hashing is covered at the end of the chapter.
Chapter 6 is about priority queues. Binary heaps are covered, and there is additional material on some of the theoretically interesting implementations of priority queues. The Fibonacci heap is discussed in Chapter 11, and the pairing heap is discussed in Chapter 12.
Chapter 7 covers sorting. It is very specific with respect to coding details and analysis. All the important generalpurpose sorting algorithms are covered and compared. Four algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. The analysis of the averagecase running time of heapsort is new to this edition. External sorting is covered at the end of the chapter.
Chapter 8 discusses the disjoint set algorithm with proof of the running time. This is a short and specific chapter that can be skipped if Kruskal's algorithm is not discussed.
Chapter 9 covers graph algorithms. Algorithms on graphs are interesting, not only because they frequently occur in practice but also because their running time is so heavily dependent on the proper use of data structures. Virtually all of the standard algorithms are presented along with appropriate data structures, pseudocode, and analysis of running time. To place these problems in a proper context, a short discussion on complexity theory (including NPcompleteness and undecidability) is provided.
Chapter 10 covers algorithm design by examining common problemsolving techniques. This chapter is heavily fortified with examples. Pseudocode is used in these later chapters so that the student's appreciation of an example algorithm is not obscured by implementation details.
Chapter 11 deals with amortized analysis. Three data structures from Chapters 4 and 6 and the Fibonacci heap, introduced in this chapter, are analyzed.
Chapter 12 is new to this edition. It covers search tree algorithms, the kd tree, and the pairing heap. This chapter departs from the rest of the text by providing complete and careful implementations for the search trees and pairing heap. The material is structured so that the instructor can integrate sections into discussions from other chapters. For example, the topdown red black tree in Chapter 12 can be discussed under AVL trees (in Chapter 4).
Chapters 19 provide enough material for most onesemester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 711. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of NPcompleteness in Chapter 9 is far too brief to be used in such a course. Garey and Johnson's book on NPcompleteness can be used to augment this text.
Exercises, provided at the end of each chapter, match the order in which material is presented. The last exercises may address the chapter as a whole rather than a specific section. Difficult exercises are marked with an asterisk, and more challenging exercises have two asterisks.
A solutions manual containing solutions to almost all the exercises is available to instructors from the AddisonWesley Publishing Company.
References are placed at the end of each chapter. Generally the references either are historical, representing the original source of the material, or they represent extensions and improvements to the results given in the text. Some references represent solutions to exercises.
The example program code in this book is available via anonymous ftp at aw.com. It is also accessible through the World Wide Web; the URL is ...
1  Introduction  1 
1.1  What's the Book About?  1 
1.2  Mathematics Review  3 
1.3  A Brief Introduction to Recursion  8 
2  Algorithm Analysis  15 
2.1  Mathematical Background  15 
2.2  Model  18 
2.3  What to Analyze  18 
2.4  Running Time Calculations  21 
3  Lists, Stacks, and Queues  41 
3.1  Abstract Data Types (ADTs)  41 
3.2  The List ADT  42 
3.3  The Stack ADT  61 
3.4  The Queue ADT  77 
4  Trees  87 
4.1  Preliminaries  87 
4.2  Binary Trees  93 
4.3  The Search Tree ADT  Binary Search Trees  98 
4.4  AVL Trees  107 
4.5  Splay Trees  117 
4.6  Tree Traversals (Revisited)  131 
4.7  BTrees  133 
5  Hashing  149 
5.1  General Idea  149 
5.2  Hash Function  150 
5.3  Open Hashing (Separate Chaining)  152 
5.4  Closed Hashing (Open Addressing)  157 
5.5  Rehashing  165 
5.6  Extendible Hashing  168 
6  Priority Queues (Heaps)  177 
6.1  Model  177 
6.2  Simple Implementations  178 
6.3  Binary Heap  179 
6.4  Applications of Priority Queues  189 
6.5  dHeaps  192 
6.6  Leftist Heaps  193 
6.7  Skew Heaps  200 
6.8  Binomial Queues  202 
7  Sorting  217 
7.1  Preliminaries  217 
7.2  Insertion Sort  218 
7.3  A Lower Bound for Simple Sorting Algorithms  219 
7.4  Shellsort  220 
7.5  Heapsort  224 
7.6  Mergesort  226 
7.7  Quicksort  232 
7.8  Sorting Large Structures  244 
7.9  A General Lower Bound for Sorting  244 
7.10  Bucket Sort  247 
7.11  External Sorting  247 
8  The Disjoint Set ADT  261 
8.1  Equivalence Relations  261 
8.2  The Dynamic Equivalence Problem  262 
8.3  Basic Data Structure  263 
8.4  Smart Union Algorithms  266 
8.5  Path Compression  268 
8.6  Worst Case for UnionbyRank and Path Compression  271 
8.7  An Application  277 
9  Graph Algorithms  281 
9.1  Definitions  281 
9.2  Topological Sort  284 
9.3  ShortestPath Algorithms  288 
9.4  Network Flow Problems  306 
9.5  Minimum Spanning Tree  311 
9.6  Applications of DepthFirst Search  317 
9.7  Introduction to NPCompleteness  330 
10  Algorithm Design Techniques  345 
10.1  Greedy Algorithms  345 
10.2  Divide and Conquer  363 
10.3  Dynamic Programming  378 
10.4  Randomized Algorithms  390 
10.5  Backtracking Algorithms  399 
11  Amortized Analysis  425 
11.1  An Unrelated Puzzle  426 
11.2  Binomial Queues  426 
11.3  Skew Heaps  431 
11.4  Fibonacci Heaps  433 
11.5  Splay Trees  443 
This book 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 firstyear graduate course in algorithm analysis. Students should have some knowledge of intermediate programming, including such topics as pointers and recursion, and some background in discrete math.
I believe it isimportant for students to learn how to program for themselves, not how to copy programs from a book. On the other hand, it is virtually impossible to discuss realistic programming issues without including sample code. For this reason, the book usually provides about onehalf to threequarters of an implementation, and the student is encouraged to supply the rest. Chapter 12, which is new to this edition, discusses additional data structures with an emphasis on implementation details.
The algorithms in this book are presented in ANSI C, which, despite some flaws, is arguably the most popular systems programming language. The use of C instead of Pascal allows the use of dynamically allocated arrays (see, for instance, rehashing in Chapter 5). It also produces simplified code in several places, usually because the and (&&) operations is shortcircuited.
Most criticisms of C center on the fact that it is easy to write code that is barely readable. Some of the more standard tricks, such as the simultaneous assignment and testing against 0 via
if (x=y)
are generally not used in the text, since the loss of clarity is compensated by only a few keystrokes and no increased speed. I believe that this books demonstrates that unreadable code can be avoided by exercising reasonable care.
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 2 deals with algorithm analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an indepth explanation of logarithms running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divideandconquer programs are introduced, but some of the analysis (solving recurrence relations) is implicitly delayed until Chapter 7, where it is performed in detail.
Chapter 3 covers lists, stacks, and queues. The emphasis here is on coding these data structures using ADTs, fast implementation of these data structures, and an exposition of some of their uses. There are almost no programs (just routines), but the exercises contain plenty of ideas for programming assignments.
Chapter 4 covers trees, with an emphasis on search trees, including external search trees (Btrees). The UNIX file system and expression trees are used as examples. AVL trees and splay trees are introduced but not analyzed. Seventyfive percent of the code is written, leaving similar cases to be completed by the student. More careful treatment of search tree implementation details is found in Chapter 12. Additional coverage of trees, such as file compression and game trees, is deferred until Chapter 10. Data structures for an external medium are considered as the final topic in several chapters.
Chapter 5 is relatively short chapter concerning hash tables. Some analysis is performed, and extendible hashing is covered at the end of the chapter.
Chapter 6 is about priority queues. Binary heaps are covered, and there is additional material on some of the theoretically interesting implementations of priority queues. The Fibonacci heap is discussed in Chapter 11, and the pairing heap is discussed in Chapter 12.
Chapter 7 covers sorting. It is very specific with respect to coding details and analysis. All the important generalpurpose sorting algorithms are covered and compared. Four algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. The analysis of the averagecase running time of heapsort is new to this edition. External sorting is covered at the end of the chapter.
Chapter 8 discusses the disjoint set algorithm with proof of the running time. This is a short and specific chapter that can be skipped if Kruskal's algorithm is not discussed.
Chapter 9 covers graph algorithms. Algorithms on graphs are interesting, not only because they frequently occur in practice but also because their running time is so heavily dependent on the proper use of data structures. Virtually all of the standard algorithms are presented along with appropriate data structures, pseudocode, and analysis of running time. To place these problems in a proper context, a short discussion on complexity theory (including NPcompleteness and undecidability) is provided.
Chapter 10 covers algorithm design by examining common problemsolving techniques. This chapter is heavily fortified with examples. Pseudocode is used in these later chapters so that the student's appreciation of an example algorithm is not obscured by implementation details.
Chapter 11 deals with amortized analysis. Three data structures from Chapters 4 and 6 and the Fibonacci heap, introduced in this chapter, are analyzed.
Chapter 12 is new to this edition. It covers search tree algorithms, the kd tree, and the pairing heap. This chapter departs from the rest of the text by providing complete and careful implementations for the search trees and pairing heap. The material is structured so that the instructor can integrate sections into discussions from other chapters. For example, the topdown red black tree in Chapter 12 can be discussed under AVL trees (in Chapter 4).
Chapters 19 provide enough material for most onesemester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 711. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of NPcompleteness in Chapter 9 is far too brief to be used in such a course. Garey and Johnson's book on NPcompleteness can be used to augment this text.
Exercises, provided at the end of each chapter, match the order in which material is presented. The last exercises may address the chapter as a whole rather than a specific section. Difficult exercises are marked with an asterisk, and more challenging exercises have two asterisks.
A solutions manual containing solutions to almost all the exercises is available to instructors from the AddisonWesley Publishing Company.
References are placed at the end of each chapter. Generally the references either are historical, representing the original source of the material, or they represent extensions and improvements to the results given in the text. Some references represent solutions to exercises.
The example program code in this book is available via anonymous ftp at aw.com. It is also accessible through the World Wide Web; the URL is http://www.aw.com/cseng/authors/weiss/dsaac2/dsaac2e.sup.html (follow the links from there). The exact location of this material may change.
Many, many people have helped me in the preparation of books in this series. Some are listed in other versions of the book; thanks to all.
For this edition, I would like to thank my editors at AddisonWesley, Carter Shanklin and Susan Hartman. Teri Hyde did another wonderful job with the production, and Matthew Harris and his staff at Publication Services did their usual fine work putting the final pieces together.
M.A.W.
Overview