Data Structures and Algorithm Analysis in C++, 2nd Edition

About

Features

• All code has been updated and tested on multiple platforms and conforms to the ANSI standard.

• Provides chapter on advanced structures and their implementation covering red black trees, top down splay trees, treaps, k-d trees, pairing heaps, and more.

• Includes a chapter on algorithm and design techniques that covers greedy algorithms, divide and conquer algorithms, dynamic programming, randomized algorithms, and backtracking.



Description

• Copyright 1999
• Edition: 2nd

• Book
• ISBN-10: 0-201-36122-1
• ISBN-13: 978-0-201-36122-3

In this second edition of his successful book, experienced teacher and author Mark Allen Weiss continues to refine and enhance his innovative approach to algorithms and data structures. Written for the advanced data structures course, this text highlights theoretical topics such as abstract data types and the efficiency of algorithms, as well as performance and running time. Before covering algorithms and data structures, the author provides a brief introduction to C++ for programmers unfamiliar with the language. Dr. Weiss's clear writing style, logical organization of topics, and extensive use of figures and examples to demonstrate the successive stages of an algorithm make this an accessible, valuable text.

New to this Edition

• An appendix on the Standard Template Library (STL)
• C++ code, tested on multiple platforms, that conforms to the ANSI ISO final draft standard

0201361221B04062001



Sample Content

Table of Contents

1. Introduction.

What's the Book About?

Mathematics Review.

Exponents.

Logarithms.

Series.

Modular Arithmetic.

The P Word.

A Brief Introduction to Recursion

C++ Classes.

Basic class Syntax.

Extra Constructor Syntax and Accessors

Separation of Interface and Implementation.

vector and string.

C++ Details.

Pointers.

Parameter Passing.

Return Passing

Reference Variables.

The Big Three: Destructor, Copy Constructor, operator=.

The World of C.

Templates.

Function Templates.

Class Templates.

Object, Comparable, and an Example.

Using Matrices.

The Data Members, Constructor, and Basic Accessors.

operator [ ].

Destructor, Copy Assignment, Copy Constructor.

Summary.

Exercises.

References.

2. Algorithm Analysis.

Mathematical Background.

Model.

What to Analyze.

Running Time Calculations.

A Simple Example.

General Rules.

Solutions for the Maximum Subsequence Sum Problem.

Logarithms in the Running Time.

Checking Your Analysis.

A Grain of Salt.

Summary.

Exercises.

References.

3. Lists, Stacks, and Queues.

Abstract Data Types (ADTs).

The List ADT.

Simple Array Implementation of Lists.

Linked Lists.

Programming Details.

Memory Reclamation and the Big Three.

Doubly Linked Lists.

Circular Linked Lists.

Examples.

Cursor Implementation of Linked Lists.

The Stack ADT.

Stack Model.

Implementation of Stacks.

Applications.

The Queue ADT.

Queue Model.

Array Implementation of Queues.

Applications of Queues.

Summary.

Exercises.

4. Trees.

Preliminaries.

Implementation of Trees.

Tree Traversals with an Application.

Binary Trees.

Implementation.

An Example: Expression Trees.

The Search Tree ADT-Binary Search Trees.

find.

findMin and findMax.

insert.

remove.

Destructor and Copy Assignment Operator.

Average-Case Analysis.

AVL Trees.

Single Rotation.

Double Rotation.

Splay Trees.

A Simple Idea (That Does Not Work).

Splaying.

Tree Traversals (Revisited).

B-Trees.

Summary.

Exercises.

References.

5. Hashing.

General Idea.

Hash Function.

Separate Chaining.

Open Addressing.

Linear Probing.

Quadratic Probing.

Double Hashing.

Rehashing.

Extendible Hashing.

Summary.

Exercises.

References.

6. Priority Queues (Heaps).

Model.

Simple Implementations.

Binary Heap.

Structure Property.

Heap-Order Property.

Basic Heap Operations.

Other Heap Operations.

Applications of Priority Queues.

The Selection Problem.

Event Simulation.

d-Heaps.

Leftist Heaps.

Leftist Heap Property.

Leftist Heap Operations.

Skew Heaps.

Binomial Queues.

Binomial Queue Structure.

Binomial Queue Operations.

Implementation of Binomial Queues.

Summary.

Exercises.

References.

7. Sorting.

Preliminaries.

Insertion Sort.

The Algorithm.

Analysis of Insertion Sort.

A Lower Bound for Simple Sorting Algorithms.

Shellsort.

Worst-Case Analysis of Shellsort

Heapsort.

Analysis of Heapsort.

Mergesort.

Analysis of Mergesort.

Quicksort.

Picking the Pivot.

Partitioning Strategy.

Small Arrays.

Actual Quicksort Routines.

Analysis of Quicksort

A Linear-Expected-Time Algorithm for Selection.

Indirect Sorting.

vector<Comparable *> Does Not Work.

Smart Pointer Class.

Overloading operator<

Dereferencing a Pointer with *.

Overloading the Type Conversion Operator

Implicit Type Conversions Are Everywhere.

Dual-Direction Implicit Conversions Can Cause Ambiguities.

Pointer Subtraction Is Legal.

A General Lower Bound for Sorting.

Decision Trees.

Bucket Sort.

External Sorting.

Why We Need New Algorithms.

Model for External Sorting.

The Simple Algorithm.

Multiway Merge.

Polyphase Merge.

Replacement Selection.

Summary.

Exercises.

References.

8. The Disjoint Set ADT.

Equivalence Relations.

The Dynamic Equivalence Problem.

Basic Data Structure.

Smart Union Algorithms.

Path Compression.

Worst Case for Union-by-Rank and Path Compression.

Analysis of the Union/Find Algorithm.

An Application.

Summary.

Exercises.

References.

9. Graph Algorithms.

Definitions.

Representation of Graphs.

Topological Sort.

Shortest-Path Algorithms.

Unweighted Shortest Paths.

Dijkstra's Algorithm.

Graphs with Negative Edge Costs

Acyclic Graphs.

All-Pairs Shortest Path.

Network Flow Problems.

A Simple Maximum-Flow Algorithm.

Minimum Spanning Tree.

Prim's Algorithm.

Kruskal's Algorithm.

Applications of Depth-First Search.

Undirected Graphs.

Biconnectivity.

Euler Circuits.

Directed Graphs.

Finding Strong Components.

Introduction to NP-Completeness.

Easy vs. Hard.

The Class NP.

NP-Complete Problems.

Summary.

Exercises.

References.

10. Algorithm Design Techniques.

Greedy Algorithms.

A Simple Scheduling Problem.

Huffman Codes.

Approximate Bin Packing.

Divide and Conquer.

Running Time of Divide and Conquer Algorithms.

Closest-Points Problem.

The Selection Problem.

Theoretical Improvements for Arithmetic Problems.

Dynamic Programming.

Using a Table Instead of Recursion.

Ordering Matrix Multiplications.

Optimal Binary Search Tree.

All-Pairs Shortest Path.

Randomized Algorithms.

Random Number Generators.

Skip Lists.

Primality Testing.

Backtracking Algorithms.

The Turnpike Reconstruction Problem.

Games.

Summary.

Exercises.

References.

11. Amortized Analysis.

An Unrelated Puzzle.

Binomial Queues.

Skew Heaps.

Fibonacci Heaps.

Cutting Nodes in Leftist Heaps.

Lazy Merging for Binomial Queues.

The Fibonacci Heap Operations.

Proof of the Time Bound.

Splay Trees.

Summary.

Exercises.

References.

12. Advanced Data Structures and Implementation.

Top-Down Splay Trees.

Red-Black Trees.

Bottom-Up Insertion.

Top-Down Red-Black Trees.

Top-Down Deletion.

Deterministic Skip Lists.

AA-Trees.

Treaps.

k-d Trees.

Pairing Heaps.

Summary.

Exercises.

References.

Appendix A. The Standard Template Library.

Introduction

Basic STL Concepts.

Header Files and the using Directive

Containers.

iterator.

Pairs.

Function Objects.

Unordered Sequences: vector and list.

vector versus list.

Stacks and Queues.

Sets.

Maps.

Example: Generating a Concordance.

STL Version.

Version without Using the STL

Example: Shortest-Path Calculation.

STL Implementation.

Version without Using the STL.

Other STL Features.

Appendix B. vector and string Classes.

First-Class versus Second-Class Objects.

vector Class.

string Class.

Index. 0201361221T04062001

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, 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 (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 http://www.awl.com/cseng/ (follow the links from there). The exact location of this material may change.

Acknowledgments

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.

As usual, the writing process was made easier by the professionals at Addison Wesley Longman. I'd like to thank my editor, Susan Hartman; associate editor, Katherine Harutunian; and production editor, Pat Unubun. I'd also like to thank Kris Engberg and her staff at Publication Services for their usual fine work putting the final pieces together.

I would like to thank the reviewers, who provided valuable comments, many of which have been incorporated into the text. For this edition, they are Phillip T. Conrad (Temple University), Robin Hill (University of Wyoming), Bob Robinson (University of Georgia), Gurdip Singh (Kansas State University), Bernard M. Waxman (Southern Illinois University at Edwardsville), and William W. White (Southern Illinois University at Edwardsville).

Finally, I'd like to thank the numerous readers who have sent e-mail messages and pointed out errors or inconsistencies in earlier versions. My World Wide Web page http://www.cs.fiu.edu/~weiss will contain updated source code (in C++, C, and Java), an errata list, and a link to submit bug reports.

M.A.W.
Miami, Florida

0201361221P04062001



Updates

Submit Errata

