preface
Thi, book is designed for a two-semester sequence in computer science,
beginning with what is typically known as Data Structures and continuing
with advanced data structures and algorithm analysis. It is appropriate for the
courses from both the two-course and three-course sequences in "B.l
intfOductory Tracks:' as outlined in the final report of the Computing Curricula
y Yracks:' as outlined in the final report of the Computing Curricula
2001 project (CC2001)--a joint undertaking of the ACM and the IEEE.
The content of the Data Structures course has been evolving for some
time. Although there is some general consensus concerning topic coverage,
considerable disagreement still exists over the details. One uniformly
accented topic is principles of software development, most notably the
conpted topic is principles of software development, most notably the
concepts of encapsulation and information hiding. Algorithmically, all Data
Structures courses tend to include an intfoduction to running-time analysis,
.,..,.,,,, 1 x.
recursion, basic sorting algorithms, and elementary data structures. Many
universities offer an advanced course that covers topics in data strictures,
algopics in data strictures,
algorithms, and running-time analysis at a higher level. The material in this text
has been designed for use in both levels of courses, thus eliminating the need
to purchase a second textbook.
Although the most passionate debates in Data Structures revolve around
the choice of a programming language, other fundamental choices need to be
made:
. Whether to introduce object-oriented design or object-based
design early
. The level of mathematical rigor
5
-'
Iv preface
. The appropriate balance between the implementation of data
stmcppropriate balance between the implementation of data
stack
tures and their use
.
. Programming details related to the language chosen (for instance,
.ramming details related to the language chosen (for instance,
,,,
should GUIs be used earlV)
J )
My goal in writing this text was to provide a practical introduction to data
y goal in writing this text was to provide a practical introduction to data
.
structures and algorithms from the viewpoint of abstract thinking and
probe point of abstract thinking and
problem solving. I tried to cover all the important details concerning the data
e. i tried to cover all the important details concerning the data
-.
structures, their analyses, and their Java implementations, while staying away
from data structures that are theoretically interesting but not widely used. It is
y Interesting but not widely used. It is
..,,, 1,
impossible to cover all the different data structures, including their uses and
the analVsis, described in this text in a single course. So I designed the
texts .is, described in this text in a single course. So I designed the
textbook to allow instructors flexibilitV in topic coverage. The instructor will need
J in topic coverage. The instructor will need
.
to decide on an appropriate balance between practice and theory and then
'
choose the topics that best fit the course. As I discuss later in this Preface, I
.,
organized the text to minimize dependencies among the various chapters.
.anned the text to minimize dependencies among the various chapters.
-
summary of chanqes
y of changes
- - - - - - - - -
in the fourth edition
1. This edition provides additional discussion on using classes (Chapter 2),
..
wntinZ classes (ChaDter 3), and interfaces (Chapter 4).
o
ry
2. Chapter 6 contains additional material discussing the running time of
lists, the use of maps, and the use of views in the Java Collections API.
3. The Scanner class is described, and code throughout the text makes use
n
of the Scanner class.
4. Chapter 9 describes and implements the 48-bit linear congruential
gener.
ator that is part of both the Java and many C++ libraries.
5. Chapter 20 has new material on separate chaining hash tables and the
t parate chaining hash tables and the
Sin na hashCode method.
Jtri ng hashCode method.
6. There are numerous revisions to the text that improve on the prose in the
.,..
previous edition.
~
7. Many new exercises are provided in Parts i. 11. and tV
j flew exercises are provided in Parts i, II, and tV
-
~ -. ~ = - I
a unique approach
me approach
My basic Dremise is that software develoDment tools in all languages come with
j Dasic premise is that software development tools in all languages come with
large libraries, and many data structUres are part of these libraries. I envision an
e, and many data structUres are part of these libraries. I envision an
'
eventual shift in emDhasis of data structures courses from imDlementation to
phasis of data structures courses from implementation to
preface v
use. In this book I tabs a unique approach by separating the data structures into
their sDecincation and subseQuent implementation and taking advantage of an
pecification and subsequent implementation and taking advantage of an
already existing data structures library, the Java Collections API.
J existing data structures library, the Java Collections API.
A subset of the Collections API suitable for most applications is discussed
.., 1
in a single chapter (Chapter 6) in Part Two. Part TWo also covers basic
analyble chapter (Chapter 6) in Part Two. Part TWo also covers basic
analysis techniques, recursion, and sorting. Part Three contains a host of
applica.'
nons that use the Collections API's data structures. Implementation of the
Collections API is not shown until Paft Four, once the data structures have
already been used. Because the Collections API is Dart of Java, students can
j paft of Java, students can
design large projects early on, using existing software components.
Despite the central use of the Collections API in this text, it is neither a book
pite the central use of the Collections API in this text, it is neither a book
on the Collections API nor a primer on implementing the Collections API
specificallV; it remains a book that emphasizes data structures and basic
problems, it remains a book that emphasizes data structures and basic
problemsolving techniques. Of course, the general techniques used in the design of data
-. -,'. -.
structures are applicable to the implementation of the Collections API, so
several chapters in Part FOur include Collections API implementations. Howevef,
instructors can choose the simpler implementations in Part Four that do not
discuss the Collections API protocol. Chapter 6, which presents the Collections
API, is essential to understanding the code in Pat Three. I attempted to use only
the basic parts of the Collections API.
Many instructors will Drefer a more traditional approach in which each
y Instructors will prefer a more traditional approach in which each
data structure is defined, implemented, and then used. Because there is no
dependency between material in Parts Three and Four, a traditional course can
easily be taught from this book.
j .nt from this book.
- -
prerequisites
Students using this book should have knowledge of either an object-oriented
or procedural programming language. Knowledge of basic features, including
...
primitive data types, operators, control structures, functions (methods), and
.
input and output (but not necessarily arrays and classes) is assumed.
StUdents who have taken a first course using C++ or Java may find the first
four chapters "light" reading in some places. Howevef, other parts are definitely
"heavV" with Java details that may not have been covered in intfoductory courses.
J with Java details that may not have been covered in introductory courses.
Students who have had a first course in another language should begin at
Chapter 1 and proceed slowly. If a student would like to use a Java reference
book as well, some recommendations are given in Chapter 1.
Knowledge of discrete math is helpful but is not an absolute
prerequi.
site. Several mathematical proofs are presented, but the more complex
proofs are preceded by a brief math review. Chapters 7 and 19--24 require
-'
yi preface
t t.
some degree of mathematical sophistication. The instructor may easily elect
arse of mathematical sophistication. The instructor may easily elect
to skip mathematical aspects of the proofs by presenting only the results.
p mathematical aspects of the proofs by presenting only the results.
All proofs in the text are clearly marked and are separate from the body of
the text.
java
ac.
fbis textbook presents material using the Java programming language. Java
.,
is a language that is often examined in comparison with C++. Java offers
auage that is often examined in comparison with C++. Java offers
,
manV benents. and Drogrammers often view Java as a safef, more portable,
J, and programmers often view Java as a safer, more portable,
,.,
and easiento-use language than C++.
guage than C++.
ac r T', 'q wory,,iwos
Yhe use of Java requires that some decisions be made when writing a
textbook. Some of the decisions made are as follows:
1. The minimum required comDiler is Java S. Please make sure Von are
4mred compiler is Java S. Please make sure you are
..,
using a compiler that is Java 5-compatible.
a a compiler that is Java 5-compatible.
ry
2. GUIs are not emphasized. Although GUIs are a nice feature in Java,
phasized. Although GUIs are a nice feature in Java,
.
theV seem to be an implementation detail rather than a core Data
J deem to be an implementation detail rather than a core Data
Rtmctures toDic. We do not use Swing in the text, but because man\'
strictures topic. We do not use Swing in the text, but because many
.
instructors maV Prefer to do so, a brief introduction to Swing is
proy prefer to do so, a brief introduction to Swing is
pro.,,.',. n
vided in Appendix B.
ppendix B.
3. APPlets are not emphasized. Applets use GUIs. Furthef, the focus of
the course is on data stttictllres, rather than language features.
Instruc.
tors who would like to discuss applets will need to supplement this
.'
text with a Java reference.
4. Inner classes are used. Inner classes are used primarily in the
imple.
mentation of the Collections API, and can be avoided by instructors
, aam
who prefer to do so.
prefer to do so.
5. The conceDt of a pointer is discussed when reference variables are
pt Of a pointer is discussed when reference variables are
.', T'
introduced. Java does not have a pointer type. Instead, it has a
reference tVPe. However, Dointers have traditionallV been an imDortant
ype. However, pointers have traditionally been an important
Data Structures topic that needs to be introduced. I illustrate the
concept of pointers in other languages when discussing reference
pt of pointers in other languages when discussing reference
.,,
vanables.
6. Threads are not discussed. Some members of the CS community
argue that multithreaded computing should become a core topic in the
. I
introductorV programming sequence. Although it is possible that this
y programming sequence. Although it is possible that this
., 1,., ac
will happen in the future, few introductory programming courses
dis-. -.
cuss this difficult topic.
pie.
preface vii
7. Some Java 5 features are not used. Including f
. Static imports, not used because in my opinion it actually makes
ports, not used because in my opinion it actually makes
the code harder to read.
. Enumefated tVves. not used because there were few "laces to
ypes, not used because there were few places to
declare public enumerated types that would be usable by clients. In
the few possible places, it did not seem to help the code's readability.
teXt organization
In this text I introduce Java and object-oriented programming (particularly
,ect-onented programming (particularly
abstraction) in Part One. I discuss primitive types, reference types, and some
of the predefined classes and exceptions before proceeding to the design of
classes and inheritance.
In Part Two, I discuss Big-Oh and algorithmic paradigms, including
.,,..'.,.,
recursion and randomization. An entire chapter is devoted to sorting, and a
separate chapter contains a description of basic data stmctures. I use the
Collections API to present the interfaces and running times of the data structures.
At this point in the text, the instrUctor may take several approaches to present
t' Lhe instrUctor may take several approaches to present
the remaining material, including the following two.
1. Discuss the corresponding implementations (either the Collections
API versions or the simpler versions) in Part Four as each data
strucpler versions) in Part Four as each data
structure is described. The instructor can ask students to extend the classes
.. -.
in various waVs, as suggested in the exercises.
J a, as suggested in the exercises.
2. Show how each Collections API class is used and cover
implementation at a later point in the course. The case studies in Part Three can
point in the course. The case studies in Part Three can
be used to support this approach. As complete implementations are
available on every modem Java compilef, the instructor can use the
Collections API in programming projects. Details on using this
,.,,
approach are given shortly.
Part Five describes advanced data structures such as splay trees, pairing
heaps, and the disjoint set data structure, which can be covered if time permits
,. 1,. n 1 1
or, more likely, in a follow-up course.
chapter-by-chapter teXt organization
Part One consists of four chapters that describe the basics of Java used
throughout the text. Chapter I describes primitive types and illustrates how to
write basic programs in Java. Chapter 2 discusses reference types and illustrates
- - -'
vill preface
the general concept of a pointer-yen though Java does not have pointers--so
that students learn this important Data Structures topic. Several of the basic
reference tVves (strings, arrays, files, and Scanners) are illustrated, and the use
J pos (strings, arrays, files, and Scanners) are illustrated, and the use
of exceptions is discussed. Chapter 3 continues this discussion by describing
how a class is implemented. Chapter 4 illustrates the use of inheritance in
designing hierarchies (including exception classes and I/O) and generic
components. Material on design patterns, including the wrappef, adapter, and
decI
orator Dattems can be found in Pat One.
patterns can be found in Pat One.
Part Two focuses on the basic algorithms and building blocks. In
Chapter 5 a complete discussion of time complexity and Big-Oh notation
.., 1 n.,.,,., 1,,
is provided. Binary search is also discussed and analyzed. Chapter 6 is
.',.,
crucial because it covers the Collections API and argues intuitively what
the running time of the supported operations should be for each data
struck Lime of the supported operations should be for each data
structure. (The implementation of these data structures, in both Collections
API-stVle and a simDlined version. is not Drovided until Part Four). This
ale and a simplified version, is not provided until Part Four). This
, 1.'
chapter also introduces the iterator pattern as well as nested, local, and
, r, 1 n,. 1 o.
anonVmous classes. Inner classes are deferred until Part Four, where theV
Jmous classes. Inner classes are deferred until Part Four, where they
,.,. 1. 1.
are discussed as an implementation technique. Chapter 7 describes
recur.,
sion bV first introducing the notion of proof by induction. It also discusses
Y nrst introducing the notion of proof by induction. It also discusses
divide-and-conquer, dynamic programming, and backtracking. A section
describes several recursive numerical algorithms that are used to
impleI
ment the RSA crvptosvstem. For many students, the material in the second
Jptosystem. For many students, the material in the second
half of Chapter 7 is more suitable for a follow-up course. Chapter 8
describes, codes, and analyzes several basic sorting algorithms, including
.
the insertion sort, Shellsort, mergesort, and quicksort, as well as indirect
. ~.
sorting. It also proves the classic lower bound for sorting and discusses the
b. It also proves the classic lower bound for sorting and discusses the
1 1', rt,. ~. 11
related problems of selection. Finally, Chapter 9 is a short chapter that
dis,,.,,.,..,. 1. 1
cusses random numbers, including their generation and use in randomized
,.,
algorithms.
aorithms.
Part Three provides several case studies, and each chapter is organized
, 1,
around a general theme. Chapter 10 illustrates several important techniques
e pier 10 illustrates several important techniques
by examining games. Chapter I I discusses the use of stacks in computer
fan; e games. Chapter I I discusses the use of stacks in computer
fan,..,.',, r,,,',,,
guages by examining an algorithm to check for balanced symbols and the
,.,.,. 1
classic oDerator Drecedence marsing algorithm. Complete implementations
perator precedence parsing algorithm. Complete implementations
. I
with code are provided for both algorithms. Chapter 12 discusses the basic
provided for both algorithms. Chapter 12 discusses the basic
..
utilities of file compression and cross-reference generation, and provides a
,.,.
complete implementation of both. Chapter 13 broadly examines simulation by
looking at one problem that can be viewed as a simulation and then at the
,.,..,. ~., 1
more classic event-driven simulation. FinallV, Chapter 14 illustrates how data
J, pier 14 illustrates how data
preface ix
-.
structures are used to implement several shortest path algorithms efficiently
for graphs.
.raphs.
Paft Four presents the data structure implementations. Chapter 15
dispresents the data structure implementations. Chapter 15
dis.,.,.'.,., 1
cusses inner classes as an implementation technique and illustrates their use
.
in the ArrayList implementation. In the remaining chapters of Part Four,
. 1.,.,,
implementations that use simple protocols (insert, find, remove variations)
are provided. In some cases, Collections API implementations that tend to
'.
use more complicated Java sVntax (in addition to being complex because of
plicated Java syntax (in addition to being complex because of
their large set of required operations) are presented. Some mathematics is
used in this part, esneciallV in Chapters 19--21, and can be skipped at the
dispart, especially in Chapters 19--21, and can be skipped at the
discretion of the instructor. Chapter 16 provides implementations for both
stacks and queues. First these data structures are implemented using an
expanding array, then they are implemented using linked lists. The
Collections API versions are discussed at the end of the chapter. General linked lists
are described in Chapter 17. Singly linked lists are illustrated with a simple
protocol, and the more complex Collections API version that uses doubly
linked lists is provided at the end of the chapter. Chapter 18 describes trees
and illustrates the basic traversal schemes. Chapter 19 is a detailed chapter
that provides several implementations of binary search trees. Initially, the
basic binarV search tree is shown, and then a binary search tree that supports
y .earch tree is shown, and then a binary search tree that suppofts
order statistics is derived. AVL trees are discussed but not implemented, but
the more practical red--black trees and AA-trees are implemented. Then the
Collections API TreeSet and TreeMap are implemented. Finally, the B-tree is
.'
examined. Chapter 20 discusses hash tables and implements the quadratic
probing scheme as part of HashSet and HashMap, after examination of a simpler
alternative. Chapter ZI describes the binary heap and examines heapsort and
external softing.
Part Five contains material suitable for use in a more advanced course or for
general reference. The algorithms are accessible even at the first-year level.
Howevef, for completeness, sophisticated mathematical analyses that are almost
certainly beyond the reach of a first-year student were included. Chapter 22
describes the snlaV tree, which is a binary search tree that seems to perform
play tree, which is a binary search tree that seems to perform
extremelV well in practice and is competitive with the binary heap in some
J bell in practice and is competitive with the binary heap in some
applications that require priority queues. Chapter 23 describes priority queues
that support merging operations and provides an implementation of the pairing
heap. Finally, Chapter 24 examines the classic disjoint set data structure.
The appendices contain additional Java reference material. Appendix A
lists the operators and their precedence. Appendix B has material on Swing,
and Appendix C describes the bitwise operators used in Chapter 12.
x preface
- - - -
chapter dependencies
Generally sDedeng, most chapters are independent of each other However
y apecing, most chapters are independent of each other Howevef,
the following are some of the notable dependencies.
e are some of the notable dependencies.
. Part One (Tour of java): The first four chapters should be covered in their
..
entAnty in seouence first, boor tO continuing on to the rest of the tCXt.
y in sequence first, Prior tO continuing on to the rest of the tCXt.
. ChaDter 5 (Algorithm Analysis): This chapter should be covered prior
pier 5 (Algorithm Analysis): This chapter should be covered prior
to Chapters 6 and 8. Recursion (Chapter 7) can be covered prior to
I
-.
this chaptef, but the instructor will have to gloss over some details
.
,.'..
about avoiding inefficient recursion.
b Inefficient recursion.
. ChaDter 6 (The Collections APe: This chapter can be covered prior to
pier 6 (The Collections APe: This chapter can be covered prior to
.....
or in conlunction with material in Part Three or FouL
J
. ChaDter 7 (Recursion): The material in Sections 7.l--7.3 should be
pier 7 (Recursion): The material in Sections 7.l--7.3 should be
1.
covered prior to discussing recursive sorting algorithms, trees, the
.
ac ac m
nc-Tao-TOe case study, and shortest-path algorithms. Material such
J, and shortest-path algorithms. Material such
as the RSA crVDtosVstem, dVnamic Drogramming, and backtracking
Jptosystem, dynamic programming, and backtracking
(unless Tie-Tao-TOe is discussed) is otherwise optional.
. ChaDter 8 (Sorting Algorithms): This chapter should follow Chapters
pier 8 (Sorting Algorithms): This chapter should follow Chapters
5 and 7. Howevef, it is possible to cover Shellsort without Chapters 5
'
1 - R' '1..
and 7. Shellsort is not recursive (hence there is no need for Chapter 7),
and a rigorous analysis of its running time is too complex and is not
borons analysis of its running time is too complex and is not
,.,,,
covered in the book (hence there is little need for Chapter 5).
. ChaDter 15 (Inner Classes and Implementations of ArraVLists):
pier 15 (Inner Classes and Implementations of ArrayLists):
This material should precede the discussion of the Collections API
.,.
implementations.
. ChaDters 16 and 17 (Stacks and Oueues/Linked Lists): These chanters
piers 16 and 17 (Stacks and Queues/Linked Lists): These chapters
,,..' 1 T T x ac
may be covered in either order However, I prefer to cover Chanter 16
y be covered in either order However, I prefer to cover Chapter 16
nrst because I believe that it presents a similer examDle of linked lists.
presents a simpler example of linked lists.
. ChaDters 18 and 19 (Trees/Binary Search Trees): These chapters can
piers 18 and 19 (Trees/Binary Search Trees): These chapters can
be covered in either order or simultaneouslV'
J.
- - - -
separate entities
ac,
she other chapters have little or no dependencies:
.
. ChaDter 9 (Randomization): The material on random numbers can be
pier 9 (Randomization): The material on random numbers can be
1.,,
covered at anV joint as needed.
J point as needed.
preface xi
. Part Three (APPlications): Chapters 10--14 can be covered in
con... t ac
Junction with or after the Collections API (in Chapter 6) and in
roughly any order. There are a few references to earlier chapters.
These include Section 10.2 (Tie-Tao-Toe), which refers to a
discus..
sion in Section 7.7, and Section 12.2 (cross-reference generation),
which refers to similar lexical analysis code in Section 1 1. 1 (balanced
symbol checking).
. ChaDters 20 and 21 (Hash Tables/A Priority Queue): These chapters
piers 20 and 21 (Hash Tables/A Priority Queue): These chapters
can be covered at any point.
J point.
. Part Five (Advanced Data Structures): The material in Chapters
22--24 is self-contained and is tVDicallv covered in a follow-uD course.
yplcally covered in a follow-up course.
mathematiI have attempted to provide mathematical rigor for use in Data Structures
courses that emphasize theory and for follow-up courses that require more
analysis. However, this material stands out from the main text in the form of
yDls. Howevef, this material stands out from the main text in the form of
separate theorems and, in some cases, separate sections or subsections. Thus
it can be skipped by instmctors in courses that deemphasize theory.
In all cases, the proof of a theorem is not necessary to the understanding
of the theorem's meaning. This is another illustration of the separation of an
interface (the theorem statement) from its implementation (the proof). Some
inherently mathematical material, such as Section 7.4 (Numerical
APPlicaJ mathematical material, such as Section 7.4 (Numerical
APPlications of Recursion), can be skipped without affecting comprehension of the
rest of the chapteL
t
- -
course organization
A crucial issue in teaching the course is deciding how the materials in Parts
Twedour are to be used. The material in Part One should be covered in
depth, and the student should write one or two programs that illustrate the
design, implementation, testing of classes and generic classes, and perhaps
object-oriented design, using inheritance. Chapter 5 discusses Big-Oh
notation. An exercise in which the student writes a short program and compares
the running time with an analysis can be given to test comprehension.
In the separation approach, the key concept of Chapter 6 is that different
data structures support different access schemes with different efficiency. Any
case studV (exceDt the Tie-Tao-Toe examDle that uses recursion) can be used
y (except the Tie-Tao-Toe example that uses recursion) can be used
- -'
Xll preface
.,
to illustrate the applications of the data structures. In this way, the student can
see the data structure and how it is used but not how it is efficiently
imDleJ
impleI
mented. This is trulV a separation. Viewing things this way will greatly
J a separation. Viewing things this way will greatly
'',.,.
enhance the ability of students to think abstractlV' Students can also provide
j J. students can also provide
.,.,.
simple implementations of some of the Collections API components (some
...
suggestions are given in the exercises in Chapter 6) and see the difference
.gestions are given in the exercises in Chapter 6) and see the difference
between efficient data structure implementations in the existing Collections
API and inefficient data structure imDlementations that theV will write.
Stuplementations that they will write.
Students can also be asked to extend the case studV, but again, they are not
J, DUt again, they are not
.', n.
required to know any of the details of the data structures.
Efficient implementation of the data structures can be discussed afted
',. 1.
ward, and recursion can be introduced whenever the instructor feels it is
..,,...
appropnate, provided it is prior to binary search trees. The details of sorting
,,.,.
can be discussed at anV time after recursion. At this joint, the course can
cone time after recursion. At this point, the course can
con. -.
tinue bV using the same case studies and experimenting with modincations to
j b penmenting with modifications to
the implementations of the data structures. For instance, the student can
plementations of the data structures. For instance, the student can
..,
experiment with various forms of balanced binarV search trees.
penment with various forms of balanced binary search trees.
Instructors who opt for a more traditional approach can simply discuss a
case study in Part Three after discussing a data structure implementation in
J in Part Three after discussing a data structure implementation in
Part FouL Again, the book's chapters are designed to be as independent of
&am, the book's chapters are designed to be as independent of
'
each other as possible.
exercISes
~...
-exercises come in vanous navors; i nave provided tour varieties. me basic in
Short exercise asks a simple question or requires hand-drawn simulations of an
,..
algorithm described in the text. The in Theory section asks questions that either
a y section asks questions that either
..
require mathematical analVsis or asks for theoretically interesting solutions to
quire mathematical analysis or asks for theoretically interesting solutions to
,, al x n....,..
problems. The in Practice section contains simple programming questions,
.',..,.',., 1.
including questions about syntax or particularly tricky lines of code. Finally,
e questions about syntax or particularly tricky lines of code. Finally,
.
the Progmmming Projects section contains ideas for extended assignments.
- - - -
pedagogical features
. Margin notes are used to highlight important topics.
.in notes are used to highlight important topics.
k. The Key COncepts section lists important terms along with definitions
and page references.
preface xiii
. The Common Errors section at the end of each chapter provides a list the
aam
of commonlV made errors. @
J made errors. @
. References for further reading are provided at the end of most chapters. k
W
supplementS
A variety of supplemental materials are available for this text. The following
y of supplemental materials are available for this text. The following
., 1 1
resources are available at http: //www. aw. corn/cssupport for all readers of this
textbooks
. Source code mes from the book. (The On the internet section at the ac
J' .aam
end of each chapter lists the filenames for the chapter's code.) j u
In addition, the following supplements are available to qualified instructors.
TO access them, visit http: //www. pearsonhi ghered. corn/cs and search our
catalog by title for Data Structures and Problem SOlving Using Java. Once on the
catalog page for this book, select the link to instructor Resources.
. POwerpoint slides of all figures in the book.
gures in the book.
. Instructor's Guide that illustrates several approaches to the material.
pproaches to the material.
It includes samples of test questions, assignments, and syllabi.
Answers to select exercises are also provided.
acknowledgmentS
Many, many people have helped me in the preparation of this book. Many
y, many people have helped me in the preparation of this book. Many
have alreadV been acknowledged in the prior edition and the related C++
verb .cd in the prior edition and the related C++
ver.
sion. Others, too numerous to list, have sent e-mail messages and pointed out
.... -.'
errors or inconsistencies in explanations that I have tried to fix in this edition.
planations that I have tried to fix in this edition.
For this edition I would like to thank my editor Michael Hirsch, editorial
assistant Stephanie Sellinger, senior production supervisor Marilyn Lloyd,
phanie Sellinger, senior production supervisor Marilyn Lloyd,
and project manager Rebecca Lazure and her team at Laserwords. Thanks
also go to Allison Michael and Erin Davis in marketing and Elena Sidorova
and Suzanne Heiser of Night & Day Design for a terrific cover.
Some of the material in this text is adapted from my textbook Effcient C
Programming: A Practical APPmach (Prentice Hall, 1995) and is used with
-'
xlv preface
..
penmssion of the published I have included end-of-chapter references where
appropriate.
My WOrld Wide Web page, http: //www. cs. fi u. edu/~wei ss, will contain
updated source code, an errata list, and a link for receiving bug reports.
M. A. W
Miami, Florida