Data Structures and Algorithms with Object-Oriented Design Patterns in Java

by Preiss, Bruno R.

• ISBN13: 9780471346135
• ISBN10: 0471346136
• Edition: 1st
• Format: Paperback
• Copyright: 1999-08-02
• Publisher: Wiley
• More Book Details
• Purchase Benefits

Summary

Author Bruno Preiss presents the fundamentals of data structures and algorithms from a modern, object-oriented perspective. The text promotes object-oriented design using Java and illustrates the use of the latest object-oriented design patterns. Virtually all the data structures are discussed in the context of a single class hierarchy. This frame work clearly shows the relationships between data structures and illustrates how polymophism and inheritance can be used effectively.

Author Biography

<b>Bruno R. Preiss</b> is an Associate Professor in the Department of Electrical and Computer Engineering at the University of Waterloo, Canada. He is a member of the Parallel and Distributed Systems Group, the Computer Communications Networks Group, and the VLSI Research Group. After earning a B.A.Sc. degree in Engineering Science, Professor Preiss received an M.A.Sc. and Ph.D. in Electrical Engineering from the University of Toronto, Canada.

Table of Contents

CHAPTER 1 INTRODUCTION	1	(5)
1.1 What This Book Is About	1	(1)
1.2 Object-Oriented Design	1	(1)
1.3 Object Hierarchies and Design Patterns	2	(1)
1.4 The Features of Java You Need to Know	3	(1)
1.5 How This Book Is Organized	4	(2)
CHAPTER 2 Algorithm Analysis	6	(29)
2.1 A Detailed Model of the Computer	7	(15)
2.2 A Simplified Model of the Computer	22	(10)
Exercises	32	(1)
Programming Projects	33	(2)
CHAPTER 3 Asymptotic Notation	35	(32)
3.1 An Asymptotic Upper Bound--Big Oh	35	(12)
3.2 An Asymptotic Lower Bound--Omega	47	(3)
3.3 More Notation--Theta and Little Oh	50	(1)
3.4 Asymptotic Analysis of Algorithms	50	(13)
Exercises	63	(3)
Programming Projects	66	(1)
CHAPTER 4 Foundational Data Structures	67	(28)
4.1 Arrays	67	(7)
4.2 Multi-Dimensional Arrays	74	(7)
4.3 Singly-Linked Lists	81	(11)
Exercises	92	(1)
Programming Projects	93	(2)
CHAPTER 5 Data Types and Abstraction	95	(25)
5.1 Abstract Data Types	95	(2)
5.2 Design Patterns	97	(19)
Exercises	116	(2)
Programming Projects	118	(2)
CHAPTER 6 Stacks, Queues and Deques	120	(35)
6.1 Stacks	120	(15)
6.2 Queues	135	(10)
6.3 Deques	145	(6)
Exercises	151	(1)
Programming Projects	152	(3)
CHAPTER 7 Ordered Lists and Sorted Lists	155	(39)
7.1 Ordered Lists	155	(24)
7.2 Sorted Lists	179	(12)
Exercises	191	(2)
Programming Projects	193	(1)
CHAPTER 8 Hashing, Hash Tables, and Scatter Tables	194	(53)
8.1 Hashing--The Basic Idea	194	(3)
8.2 Hashing Methods	197	(4)
8.3 Hash Function Implementations	201	(10)
8.4 Hash Tables	211	(7)
8.5 Scatter Tables	218	(9)
8.6 Scatter Table Using Open Addressing	227	(14)
8.7 Applications	241	(3)
Exercises	244	(2)
Programming Projects	246	(1)
CHAPTER 9 Trees	247	(45)
9.1 Basics	248	(3)
9.2 N-ary Trees	251	(3)
9.3 Binary Trees	254	(2)
9.4 Tree Traversals	256	(2)
9.5 Expression Trees	258	(3)
9.6 Implementing Trees	261	(27)
Exercises	288	(2)
Programming Projects	290	(2)
CHAPTER 10 Search Trees	292	(55)
10.1 Basics	292	(2)
10.2 Searching a Search Tree	294	(2)
10.3 Average Case Analysis	296	(6)
10.4 Implementing Search Trees	302	(6)
10.5 AVL Search Trees	308	(13)
10.6 M-Way Search Trees	321	(10)
10.7 B-Trees	331	(11)
10.8 Applications	342	(1)
Exercises	343	(2)
Programming Projects	345	(2)
CHAPTER 11 Heaps and Priority Queues	347	(44)
11.1 Basics	348	(1)
11.2 Binary Heaps	349	(10)
11.3 Leftist Heaps	359	(9)
11.4 Binomial Queues	368	(15)
11.5 Applications	383	(4)
Exercises	387	(2)
Programming Projects	389	(2)
CHAPTER 12 Sets, Multisets, and Partitions	391	(36)
12.1 Basics	391	(1)
12.2 Array and Bit-Vector Sets	392	(9)
12.3 Multisets	401	(9)
12.4 Partitions	410	(12)
12.5 Applications	422	(2)
Exercises	424	(2)
Programming Projects	426	(1)
CHAPTER 13 Garbage Collection	427	(19)
13.1 What Is Garbage?	428	(2)
13.2 Reference Counting Garbage Collection	430	(4)
13.3 Mark-and-Sweep Garbage Collection	434	(3)
13.4 Stop-and-Copy Garbage Collection	437	(2)
13.5 Mark-and-Compact Garbage Collection	439	(4)
Exercises	443	(1)
Programming Projects	443	(3)
CHAPTER 14 Algorithmic Patterns and Problem Solvers	446	(45)
14.1 Brute-Force and Greedy Algorithms	446	(4)
14.2 Backtracking Algorithms	450	(9)
14.3 Top-Down Algorithms: Divide and Conquer	459	(10)
14.4 Bottom-Up Algorithms: Dynamic Programming	469	(8)
14.5 Randomized Algorithms	477	(10)
Exercises	487	(2)
Programming Projects	489	(2)
CHAPTER 15 Sorting Algorithms and Sorters	491	(47)
15.1 Basics	491	(1)
15.2 Sorting and Sorters	492	(2)
15.3 Insertion Sorting	494	(5)
15.4 Exchange Sorting	499	(11)
15.5 Selection Sorting	510	(9)
15.6 Merge Sorting	519	(5)
15.7 A Lower Bound on Sorting	524	(2)
15.8 Distribution Sorting	526	(6)
15.9 Performance Data	532	(3)
Exercises	535	(2)
Programming Projects	537	(1)
CHAPTER 16 Graphs and Graph Algorithms	538	(61)
16.1 Basics	539	(8)
16.2 Implementing Graphs	547	(9)
16.3 Graph Traversals	556	(14)
16.4 Shortest-Path Algorithms	570	(10)
16.5 Minimum-Cost Spanning Trees	580	(9)
16.6 Application: Critical Path Analysis	589	(5)
Exercises	594	(3)
Programming Projects	597	(2)
APPENDIX A Java and Object-Oriented Programming	599	(22)
A.1 Variables	599	(2)
A.2 Parameter Passing	601	(3)
A.3 Objects and Classes	604	(5)
A.4 Inner Classes	609	(1)
A.5 Inheritance and Polymorphism	610	(9)
A.6 Exceptions	619	(2)
APPENDIX B Class Hierarchy Diagrams	621	(2)
APPENDIX C Character Codes	623	(2)
Bibliography	625	(2)
Index	627