Like New — packaging may have been opened. A "Like New" item is suitable to give as a gift.

Very Good — may have minor signs of wear on packaging but item works perfectly and has no damage.

Good — item is in good condition but packaging may have signs of shelf wear/aging or torn packaging. All specific defects should be noted in the Comments section associated with each item.

Acceptable — item is in working order but may show signs of wear such as scratches or torn packaging. All specific defects should be noted in the Comments section associated with each item.

Used — An item that has been opened and may show signs of wear. All specific defects should be noted in the Comments section associated with each item.

Refurbished — A used item that has been renewed or updated and verified to be in proper working condition. Not necessarily completed by the original manufacturer.

<b style='color: #000'>Lightly used. Inside looks clean.</b> Ships same day or next business day. Free USPS Tracking Number. Excellent Customer Service. Ships from TN

Data Structures and Algorithm Analysis in C++ is an advanced algorithms book that bridges the gap between traditional CS2 and Algorithms Analysis courses.

As the speed and power of computers increases, so does the need for effective programming and algorithm analysis. By approaching these skills in tandem, Mark Allen Weiss teaches readers to develop well-constructed, maximally efficient programs using the C++ programming language.

This book explains topics from binary heaps to sorting to NP-completeness, and dedicates a full chapter to amortized analysis and advanced data structures and their implementation. Figures and examples illustrating successive stages of algorithms contribute to Weissâ€™ careful, rigorous and in-depth analysis of each type of algorithm.

Mark Weiss uses C++ to provide a smooth introduction to object-oriented design for programmers competent in one other language. Using C++, the book delivers a series of carefully developed examples which illustrate the important concepts of object orientation alongside its main theme of data structures.

Written for the advanced data structures course, this textbook highlights theoretical topics such as abstract data types and the efficiency of algorithms and data structures, as well as performance and running time. The second edition adds an appendix on the Standard Template Library (STL), and C++ code that conforms to the ANSI ISO final draft standard. Annotation c. by Book News, Inc., Portland, Or.

Mark Allen Weiss is Professor and Associate Director for the School of Computing and Information Sciences at Florida International University. He is also currently serving as both Director of Undergraduate Studies and Director of Graduate Studies. He received his Bachelorâ€™s Degree in Electrical Engineering from the Cooper Union in 1983, and his Ph.D. in Computer Science from Princeton University in 1987, working under Bob Sedgewick. He has been at FIU since 1987 and was promoted to Professor in 1996. His interests include data structures, algorithms, and education. He is most well-known for his highly-acclaimed Data Structures textbooks, which have been used for a generation by roughly a million students.

Professor Weiss is the author of numerous publications in top-rated journals and was recipient of the Universityâ€™s Excellence in Research Award in 1994. In 1996 at FIU he was the first in the world to teach Data Structures using the Java programming language, which is now the de facto standard. From 1997-2004 he served as a member of the Advanced Placement Computer Science Development Committee, chairing the committee from 2000-2004. The committee designed the curriculum and wrote the AP exams that were taken by 20,000 high school students annually.

In addition to his Research Award in 1994, Professor Weiss is also the recipient of the Universityâ€™s Excellence in Teaching Award in 1999 and the School of Computing and Information Science Excellence in Teaching Award (2005) and Excellence in Service Award (2007).

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-basedprogramming, 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 (the class and template) 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 an object-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++ class design.

Chapter 2 deals with algorithm analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an in-depth explanation of logarithmic running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divide-and-conquer 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 complete programs, but the exercises contain plenty of ideas for programming assignments.

Chapter 4 covers trees, with an emphasis on search trees, including external search trees (B-trees). The UNIX file system and expression trees are used as examples. AVL trees and splay trees are introduced. 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 a 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 general-purpose sorting algorithms are covered and compared. Four algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. 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 NP-completeness and undecidability) is provided.

Chapter 10 covers algorithm design by examining common problem-solving 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 covers search tree algorithms, the k-d 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 top-down red-black tree in Chapter 12 can be discussed under AVL trees (in Chapter 4). Appendix A discusses the Standard Template Library and illustrates how the concepts described in this text are applied to a high-performance data structures and algorithms library. Appendix B describes an implementation of vector and string.

Chapters 1-9 provide enough material for most one-semester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 7-11. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of NP-completeness in Chapter 9 is far too brief to be used in such a course. Garey and Johnson's book on NP-completeness can be used to augment this text.

Exercises

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 online to instructors from the Addison Wesley Longman Publishing Company. Instructors should contact their Addison-Wesley local sales representative for information on the manual's availability.

References

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.

Code Availability

The example program code in this book is available via anonymous ftp at ftp.awl.com/cseng/authors/weiss. It is also accessible through the World Wide Web; the URL is ...

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, andobject-basedprogramming, 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 (the class and template) 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 an object-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++ class design.

Chapter 2 deals with algorithm analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an in-depth explanation of logarithmic running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divide-and-conquer 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 complete programs, but the exercises contain plenty of ideas for programming assignments.

Chapter 4 covers trees, with an emphasis on search trees, including external search trees (B-trees). The UNIX file system and expression trees are used as examples. AVL trees and splay trees are introduced. 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 a 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 general-purpose sorting algorithms are covered and compared. Four algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. 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 NP-completeness and undecidability) is provided.

Chapter 10 covers algorithm design by examining common problem-solving 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 covers search tree algorithms, the k-d 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 top-down red-black tree in Chapter 12 can be discussed under AVL trees (in Chapter 4). Appendix A discusses the Standard Template Library and illustrates how the concepts described in this text are applied to a high-performance data structures and algorithms library. Appendix B describes an implementation of vector and string.

Chapters 1-9 provide enough material for most one-semester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 7-11. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of NP-completeness in Chapter 9 is far too brief to be used in such a course. Garey and Johnson's book on NP-completeness can be used to augment this text.

Exercises

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 online to instructors from the Addison Wesley Longman Publishing Company. Instructors should contact their Addison-Wesley local sales representative for information on the manual's availability.

References

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.

Code Availability

The example program code in this book is available via anonymous ftp at ftp.awl.com/cseng/authors/weiss. It is also accessible through the World Wide Web; the URL is ...

Our reader reviews allow you to share your comments on titles you liked,
or didn't, with others. By submitting an online review, you are representing to
Barnes & Noble.com that all information contained in your review is original
and accurate in all respects, and that the submission of such content by you
and the posting of such content by Barnes & Noble.com does not and will not
violate the rights of any third party. Please follow the rules below to help
ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer.
However, we cannot allow persons under the age of 13 to have accounts at BN.com or
to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the
information on the product page, please send us an email.

Reviews should not contain any of the following:

- HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone

- Time-sensitive information such as tour dates, signings, lectures, etc.

- Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.

- Comments focusing on the author or that may ruin the ending for others

- Phone numbers, addresses, URLs

- Pricing and availability information or alternative ordering information

- Advertisements or commercial solicitation

Reminder:

- By submitting a review, you grant to Barnes & Noble.com and its
sublicensees the royalty-free, perpetual, irrevocable right and license to use the
review in accordance with the Barnes & Noble.com Terms of Use.

- Barnes & Noble.com reserves the right not to post any review -- particularly
those that do not follow the terms and conditions of these Rules. Barnes & Noble.com
also reserves the right to remove any review at any time without notice.

- See Terms of Use for other conditions and disclaimers.

Search for Products You'd Like to Recommend

Create a Pen Name

Welcome, penname

You have successfully created your Pen Name. Start enjoying the benefits of the BN.com Community today.

If you find inappropriate content, please report it to Barnes & Noble

## More About This Textbook

## Overview

is an advanced algorithms book that bridges the gap between traditional CS2 and Algorithms Analysis courses.Data Structures and Algorithm Analysis in C++As the speed and power of computers increases, so does the need for effective programming and algorithm analysis. By approaching these skills in tandem, Mark Allen Weiss teaches readers to develop well-constructed, maximally efficient programs using the C++ programming language.

This book explains topics from binary heaps to sorting to

NP-completeness, and dedicates a full chapter to amortized analysis and advanced data structures and their implementation. Figures and examples illustrating successive stages of algorithms contribute to Weissâ€™ careful, rigorous and in-depth analysis of each type of algorithm.Mark Weiss uses C++ to provide a smooth introduction to object-oriented design for programmers competent in one other language. Using C++, the book delivers a series of carefully developed examples which illustrate the important concepts of object orientation alongside its main theme of data structures.

## Editorial Reviews

## Booknews

Written for the advanced data structures course, this textbook highlights theoretical topics such as abstract data types and the efficiency of algorithms and data structures, as well as performance and running time. The second edition adds an appendix on the Standard Template Library (STL), and C++ code that conforms to the ANSI ISO final draft standard. Annotation c. by Book News, Inc., Portland, Or.## Product Details

## Related Subjects

## Meet the Author

Mark Allen Weiss is Professor and Associate Director for the School of Computing and Information Sciences at Florida International University. He is also currently serving as both Director of Undergraduate Studies and Director of Graduate Studies. He received his Bachelorâ€™s Degree in Electrical Engineering from the Cooper Union in 1983, and his Ph.D. in Computer Science from Princeton University in 1987, working under Bob Sedgewick. He has been at FIU since 1987 and was promoted to Professor in 1996. His interests include data structures, algorithms, and education. He is most well-known for his highly-acclaimed Data Structures textbooks, which have been used for a generation by roughly a million students.

Professor Weiss is the author of numerous publications in top-rated journals and was recipient of the Universityâ€™s Excellence in Research Award in 1994. In 1996 at FIU he was the first in the world to teach Data Structures using the Java programming language, which is now the de facto standard. From 1997-2004 he served as a member of the Advanced Placement Computer Science Development Committee, chairing the committee from 2000-2004. The committee designed the curriculum and wrote the AP exams that were taken by 20,000 high school students annually.

In addition to his Research Award in 1994, Professor Weiss is also the recipient of the Universityâ€™s Excellence in Teaching Award in 1999 and the School of Computing and Information Science Excellence in Teaching Award (2005) and Excellence in Service Award (2007).

## Read an Excerpt

## 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-basedprogramming, 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 (the

classandtemplate) 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 an

object-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++ class design.

Chapter 2 deals with algorithm analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an in-depth explanation of logarithmic running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divide-and-conquer 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

`ADT`

s, fast implementation of these data structures, and an exposition of some of their uses. There are almost no complete programs, but the exercises contain plenty of ideas for programming assignments.Chapter 4 covers trees, with an emphasis on search trees, including external search trees (B-trees). The UNIX file system and expression trees are used as examples.

`AVL`

trees and splay trees are introduced. 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 a 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 general-purpose sorting algorithms are covered and compared. Four algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. 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

NP-completeness and undecidability) is provided.Chapter 10 covers algorithm design by examining common problem-solving 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 covers search tree algorithms, the

k-d 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 top-down red-black tree in Chapter 12 can be discussed under`AVL`

trees (in Chapter 4). Appendix A discusses the Standard Template Library and illustrates how the concepts described in this text are applied to a high-performance data structures and algorithms library. Appendix B describes an implementation of`vector`

and`string`

.Chapters 1-9 provide enough material for most one-semester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 7-11. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of

NP-completeness in Chapter 9 is far too brief to be used in such a course. Garey and Johnson's book onNP-completeness can be used to augment this text.## Exercises

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 online to instructors from the Addison Wesley Longman Publishing Company. Instructors should contact their Addison-Wesley local sales representative for information on the manual's availability.

## References

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.

## Code Availability

The example program code in this book is available via anonymous ftp at

`ftp.awl.com/cseng/authors/weiss`

. It is also accessible through the World Wide Web; the URL is`...`

## Table of Contents

Chapter 1 Programming: A General Overview 11.1 Whatâ€™s This Book About? 1

1.2 Mathematics Review 2

1.2.1 Exponents 3

1.2.2 Logarithms 3

1.2.3 Series 4

1.2.4 Modular Arithmetic 5

1.2.5 The

PWord 61.3 A Brief Introduction to Recursion 8

1.4 C++ Classes 12

1.4.1 Basic class Syntax 12

1.4.2 Extra Constructor Syntax and Accessors 13

1.4.3 Separation of Interface and Implementation 16

1.4.4 vector and string 19

1.5 C++ Details 21

1.5.1 Pointers 21

1.5.2 Lvalues, Rvalues, and References 23

1.5.3 Parameter Passing 25

1.5.4 Return Passing 27

1.5.5 std::swap and std::move 29

1.5.6 The Big-Five: Destructor, Copy Constructor, Move Constructor, Copy Assignment operator=, Move Assignment operator= 30

1.5.7 C-style Arrays and Strings 35

1.6 Templates 36

1.6.1 Function Templates 37

1.6.2 Class Templates 38

1.6.3 Object, Comparable, and an Example 39

1.6.4 Function Objects 41

1.6.5 Separate Compilation of Class Templates 44

1.7 Using Matrices 44

1.7.1 The Data Members, Constructor, and Basic Accessors 44

1.7.2 operator[] 45

1.7.3 Big-Five 46

Summary 46

Exercises 46

References 48

Chapter 2 Algorithm Analysis 512.1 Mathematical Background 51

2.2 Model 54

2.3 What to Analyze 54

2.4 Running-Time Calculations 57

2.4.1 A Simple Example 58

2.4.2 General Rules 58

2.4.3 Solutions for the Maximum Subsequence Sum Problem 60

2.4.4 Logarithms in the Running Time 66

2.4.5 Limitations of Worst Case Analysis 70

Summary 70

Exercises 71

References 76

Chapter 3 Lists, Stacks, and Queues 773.1 Abstract Data Types (ADTs) 77

3.2 The List ADT 78

3.2.1 Simple Array Implementation of Lists 78

3.2.2 Simple Linked Lists 79

3.3 vector and list in the STL 80

3.3.1 Iterators 82

3.3.2 Example: Using erase on a List 83

3.3.3 const_iterators 84

3.4 Implementation of vector 86

3.5 Implementation of list 91

3.6 The Stack ADT 103

3.6.1 Stack Model 103

3.6.2 Implementation of Stacks 104

3.6.3 Applications 104

3.7 The Queue ADT 112

3.7.1 Queue Model 113

3.7.2 Array Implementation of Queues 113

3.7.3 Applications of Queues 115

Summary 116

Exercises 116

Chapter 4 Trees 1214.1 Preliminaries 121

4.1.1 Implementation of Trees 122

4.1.2 Tree Traversals with an Application 123

4.2 Binary Trees 126

4.2.1 Implementation 128

4.2.2 An Example: Expression Trees 128

4.3 The Search Tree ADTâ€“Binary Search Trees 132

4.3.1 contains 134

4.3.2 findMin and findMax 135

4.3.3 insert 136

4.3.4 remove 139

4.3.5 Destructor and Copy Constructor 141

4.3.6 Average-Case Analysis 141

4.4 AVL Trees 144

4.4.1 Single Rotation 147

4.4.2 Double Rotation 149

4.5 Splay Trees 158

4.5.1 A Simple Idea (That Does Not Work) 158

4.5.2 Splaying 160

4.6 Tree Traversals (Revisited) 166

4.7 B-Trees 168

4.8 Sets and Maps in the Standard Library 173

4.8.1 Sets 173

4.8.2 Maps 174

4.8.3 Implementation of set and map 175

4.8.4 An Example That Uses Several Maps 176

Summary 181

Exercises 182

References 189

Chapter 5 Hashing 1935.1 General Idea 193

5.2 Hash Function 194

5.3 Separate Chaining 196

5.4 Hash Tables without Linked Lists 201

5.4.1 Linear Probing 201

5.4.2 Quadratic Probing 202

5.4.3 Double Hashing 207

5.5 Rehashing 208

5.6 Hash Tables in the Standard Library 210

5.7 Hash Tables with Worst-Case

O(1) Access 2125.7.1 Perfect Hashing 213

5.7.2 Cuckoo Hashing 215

5.7.3 Hopscotch Hashing 224

5.8 Universal Hashing 230

5.9 Extendible Hashing 233

Summary 236

Exercises 238

References 242

Chapter 6 Priority Queues (Heaps) 2456.1 Model 245

6.2 Simple Implementations 246

6.3 Binary Heap 247

6.3.1 Structure Property 247

6.3.2 Heap-Order Property 248

6.3.3 Basic Heap Operations 249

6.3.4 Other Heap Operations 252

6.4 Applications of Priority Queues 257

6.4.1 The Selection Problem 258

6.4.2 Event Simulation 259

6.5

d-Heaps 2606.6 Leftist Heaps 261

6.6.1 Leftist Heap Property 261

6.6.2 Leftist Heap Operations 262

6.7 Skew Heaps 269

6.8 Binomial Queues 271

6.8.1 Binomial Queue Structure 271

6.8.2 Binomial Queue Operations 271

6.8.3 Implementation of Binomial Queues 276

6.9 Priority Queues in the Standard Library 283

Summary 283

Exercises 283

References 288

Chapter 7 Sorting 2917.1 Preliminaries 291

7.2 Insertion Sort 292

7.2.1 The Algorithm 292

7.2.2 STL Implementation of Insertion Sort 293

7.2.3 Analysis of Insertion Sort 294

7.3 A Lower Bound for Simple Sorting Algorithms 295

7.4 Shellsort 296

7.4.1 Worst-Case Analysis of Shellsort 297

7.5 Heapsort 300

7.5.1 Analysis of Heapsort 301

7.6 Mergesort 304

7.6.1 Analysis of Mergesort 306

7.7 Quicksort 309

7.7.1 Picking the Pivot 311

7.7.2 Partitioning Strategy 313

7.7.3 Small Arrays 315

7.7.4 Actual Quicksort Routines 315

7.7.5 Analysis of Quicksort 318

7.7.6 A Linear-Expected-Time Algorithm for Selection 321

7.8 A General Lower Bound for Sorting 323

7.8.1 Decision Trees 323

7.9 Decision-Tree Lower Bounds for Selection Problems 325

7.10 Adversary Lower Bounds 328

7.11 Linear-Time Sorts: Bucket Sort and Radix Sort 331

7.12 External Sorting 336

7.12.1 Why We Need New Algorithms 336

7.12.2 Model for External Sorting 336

7.12.3 The Simple Algorithm 337

7.12.4 Multiway Merge 338

7.12.5 Polyphase Merge 339

7.12.6 Replacement Selection 340

Summary 341

Exercises 341

References 347

Chapter 8 The Disjoint Sets Class 3518.1 Equivalence Relations 351

8.2 The Dynamic Equivalence Problem 352

8.3 Basic Data Structure 353

8.4 Smart Union Algorithms 357

8.5 Path Compression 360

8.6 Worst Case for Union-by-Rank and Path Compression 361

8.6.1 Slowly Growing Functions 362

8.6.2 An Analysis by Recursive Decomposition 362

8.6.3 An

O(Mlog *N) Bound 3698.6.4 An

O(M Î±(M, N) ) Bound 3708.7 An Application 372

Summary 374

Exercises 375

References 376

Chapter 9 Graph Algorithms 3799.1 Definitions 379

9.1.1 Representation of Graphs 380

9.2 Topological Sort 382

9.3 Shortest-Path Algorithms 386

9.3.1 Unweighted Shortest Paths 387

9.3.2 Dijkstraâ€™s Algorithm 391

9.3.3 Graphs with Negative Edge Costs 400

9.3.4 Acyclic Graphs 400

9.3.5 All-Pairs Shortest Path 404

9.3.6 Shortest Path Example 404

9.4 Network Flow Problems 406

9.4.1 A Simple Maximum-Flow Algorithm 408

9.5 Minimum Spanning Tree 413

9.5.1 Primâ€™s Algorithm 414

9.5.2 Kruskalâ€™s Algorithm 417

9.6 Applications of Depth-First Search 419

9.6.1 Undirected Graphs 420

9.6.2 Biconnectivity 421

9.6.3 Euler Circuits 425

9.6.4 Directed Graphs 429

9.6.5 Finding Strong Components 431

9.7 Introduction to NP-Completeness 432

9.7.1 Easy vs. Hard 433

9.7.2 The Class NP 434

9.7.3 NP-Complete Problems 434

Summary 437

Exercises 437

References 445

Chapter 10 Algorithm Design Techniques 44910.1 Greedy Algorithms 449

10.1.1 A Simple Scheduling Problem 450

10.1.2 Huffman Codes 453

10.1.3 Approximate Bin Packing 459

10.2 Divide and Conquer 467

10.2.1 Running Time of Divide-and-Conquer Algorithms 468

10.2.2 Closest-Points Problem 470

10.2.3 The Selection Problem 475

10.2.4 Theoretical Improvements for Arithmetic Problems 478

10.3 Dynamic Programming 482

10.3.1 Using a Table Instead of Recursion 483

10.3.2 Ordering Matrix Multiplications 485

10.3.3 Optimal Binary Search Tree 487

10.3.4 All-Pairs Shortest Path 491

10.4 Randomized Algorithms 494

10.4.1 Random-Number Generators 495

10.4.2 Skip Lists 500

10.4.3 Primality Testing 503

10.5 Backtracking Algorithms 506

10.5.1 The Turnpike Reconstruction Problem 506

10.5.2 Games 511

Summary 518

Exercises 518

References 527

Chapter 11 Amortized Analysis 53311.1 An Unrelated Puzzle 534

11.2 Binomial Queues 534

11.3 Skew Heaps 539

11.4 Fibonacci Heaps 541

11.4.1 Cutting Nodes in Leftist Heaps 542

11.4.2 Lazy Merging for Binomial Queues 544

11.4.3 The Fibonacci Heap Operations 548

11.4.4 Proof of the Time Bound 549

11.5 Splay Trees 551

Summary 555

Exercises 556

References 557

Chapter 12 Advanced Data Structures and Implementation 55912.1 Top-Down Splay Trees 559

12.2 Red-Black Trees 566

12.2.1 Bottom-Up Insertion 567

12.2.2 Top-Down Red-Black Trees 568

12.2.3 Top-Down Deletion 570

12.3 Treaps 576

12.4 Suffix Arrays and Suffix Trees 579

12.4.1 Suffix Arrays 580

12.4.2 Suffix Trees 583

12.4.3 Linear-Time Construction of Suffix Arrays and Suffix Trees 586

12.5

k-d Trees 59612.6 Pairing Heaps 602

Summary 606

Exercises 608

References 612

Appendix A Separate Compilation of Class Templates 615A.1 Everything in the Header 616

A.2 Explicit Instantiation 616

Index 619

## Preface

## 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, andobject-basedprogramming, 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 (the

classandtemplate) 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 an

object-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++ class design.

Chapter 2 deals with algorithm analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an in-depth explanation of logarithmic running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divide-and-conquer 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

`ADT`

s, fast implementation of these data structures, and an exposition of some of their uses. There are almost no complete programs, but the exercises contain plenty of ideas for programming assignments.Chapter 4 covers trees, with an emphasis on search trees, including external search trees (B-trees). The UNIX file system and expression trees are used as examples.

`AVL`

trees and splay trees are introduced. 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 a 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 general-purpose sorting algorithms are covered and compared. Four algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. 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

NP-completeness and undecidability) is provided.Chapter 10 covers algorithm design by examining common problem-solving 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 covers search tree algorithms, the

k-d 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 top-down red-black tree in Chapter 12 can be discussed under`AVL`

trees (in Chapter 4). Appendix A discusses the Standard Template Library and illustrates how the concepts described in this text are applied to a high-performance data structures and algorithms library. Appendix B describes an implementation of`vector`

and`string`

.Chapters 1-9 provide enough material for most one-semester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 7-11. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of

NP-completeness in Chapter 9 is far too brief to be used in such a course. Garey and Johnson's book onNP-completeness can be used to augment this text.## Exercises

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 online to instructors from the Addison Wesley Longman Publishing Company. Instructors should contact their Addison-Wesley local sales representative for information on the manual's availability.

## References

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.

## Code Availability

The example program code in this book is available via anonymous ftp at

`ftp.awl.com/cseng/authors/weiss`

. It is also accessible through the World Wide Web; the URL is`...`