Data Structures and Algorithms in Java, 3rd Edition

by Michael T. Goodrich (Univ. of California, Irvine); Roberto Tamassia (Brown Univ.)

• ISBN13: 9780471469834
• ISBN10: 0471469831
• Edition: 3rd
• Format: Hardcover
• Copyright: 2003-12-01
• Publisher: Wiley

Summary

This version of the book uses the latest Java technology, Java 2 Standard Edition Version 5.0 (J2SE V. 5.0), or otherwise known as "Version 5.0."This revolutionary book intertwines problem solving and software engineering with the study of traditional data structures topics. The book emphasizes the use of objects and object-oriented design. Early chapters provide background coverage of software engineering. Then, in the chapters on data structures, these principles are applied. The authors encourage use of a five-step process for the solution of case studies: problem specification, analysis, design, implementation, and testing. As is done in industry, these steps are sometimes performed in an iterative fashion rather than in strict sequence. The Java Application Programming Interface (API) is used throughout the text. Wherever possible, the specification and interface for a data structure follow the Java Collections Framework. Emphasises the use of objects and object-oriented design Provides a primer on the Java language and offers background coverage of software engineering Encourages an iterative five-step process for the solution of case studies: problem specification, analysis, design, implementation, and testing The Java Application Programming Interface (API) is used throughout

Author Biography

Professors Goodrich and Tamassia are well-recognized researchers in algorithms and data structures, having published many papers in this field, with applications to Internet computing, information visualization, computer security, and geometric computing. They have served as principal investigators in several joint projects sponsored by the National Science Foundation, the Army Research Office, and the Defense Advanced Research Projects Agency. They are also active in educational technology research, with special emphasis on algorithm visualization systems.

Michael Goodrich received his Ph.D. in computer science from Purdue University in 1987. He is currently a professor in the Department of Computer Science at University of California, Irvine. Previously, he was a professor at Johns Hopkins University. He is an editor for the International Journal of Computational Geometry & Applications and Journal of Graph Algorithms and Applications.

Roberto Tamassia received his Ph.D. in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign in 1988. He is currently a professor in the Department of Computer Science at Brown University. He is editor-in-chief for the Journal of Graph Algorithms and Applications and an editor for Computational Geometry: Theory and Applications. He previously served on the editorial board of IEEE Transactions on Computers.

In addition to their research accomplishments, the authors also have extensive experience in the classroom. For example, Dr. Goodrich has taught data structures and algorithms courses, including Data Structures as a freshman-sophomore level course and Introduction to Algorithms as an upper level course. He has earned several teaching awards in this capacity. His teaching style is to involve the students in lively interactive classroom sessions that bring out the intuition and insights behind data structuring and algorithmic techniques. Dr. Tamassia has taught Data Structures and Algorithms as an introductory freshman-level course since 1988. One thing that has set his teaching style apart is his effective use of interactive hypermedia presentations integrated with the Web.

The instructional Web sites, datastructures.net and algorithmdesign.net, supported by Drs. Goodrich and Tamassia are used as reference material by students, teachers, and professionals worldwide.

Table of Contents

1 Java Programming	1	(54)
1.1 Classes, Types, and Objects	3	(8)
1.2 Methods	11	(6)
1.3 Expressions	17	(8)
1.4 Control Flow	25	(7)
1.5 Arrays	32	(2)
1.6 Simple Input and Output	34	(3)
1.7 An Example Program	37	(3)
1.8 Packages	40	(2)
1.9 Writing a Java Program	42	(7)
1.10 Utilities in the java.lang Package	49	(2)
1.11 Exercises	51	(4)
2 Object-Oriented Design	55	(44)
2.1 Goals and Principles	57	(5)
2.2 Inheritance and Polymorphism	62	(14)
2.3 Exceptions	76	(4)
2.4 Interfaces, Abstract Classes, and Casting	80	(8)
2.5 Recursion and Other Design Patterns	88	(7)
2.6 Exercises	95	(4)
3 Analysis Tools	99	(40)
3.1 What Is Running Time Anyway?	101	(2)
3.2 Pseudo-Code	103	(2)
3.3 The Seven Functions Used in This Book	105	(9)
3.4 Analysis of Algorithms	114	(14)
3.5 Simple Justification Techniques	128	(4)
3.6 Exercises	132	(7)
4 Stacks, Queues, and Recursion	139	(60)
4.1 Using Recursion	141	(11)
4.2 Stacks	152	(18)
4.3 Queues	170	(12)
4.4 Linked Lists	182	(7)
4.5 Double-Ended Queues	189	(5)
4.6 Exercises	194	(5)
5 Vectors, Lists, and Sequences	199	(44)
5.1 Vectors and Array Lists	201	(9)
5.2 Lists	210	(11)
5.3 Sequences	221	(4)
5.4 Favorite Lists and the Move-to-Front Heuristic	225	(7)
5.5 Iterators	232	(5)
5.6 Exercises	237	(6)
6 Trees	243	(60)
6.1 The Tree Abstract Data Type	245	(7)
6.2 Basic Algorithms on Trees	252	(11)
6.3 Binary Trees	263	(15)
6.4 Data Structures for Representing Trees	278	(15)
6.5 Exercises	293	(10)
7 Priority Queues	303	(50)
7.1 The Priority Queue Abstract Data Type	305	(8)
7.2 Implementing a Priority Queue with a List	313	(7)
7.3 Heaps	320	(22)
7.4 Adaptable Priority Queues	342	(5)
7.5 Exercises	347	(6)
8 Maps and Dictionaries	353	(54)
8.1 The Map Abstract Data Type	355	(5)
8.2 Hash Tables	360	(16)
8.3 The Dictionary Abstract Data Type	376	(10)
8.4 Skip Lists	386	(9)
8.5 Extensions and Applications of Dictionaries	395	(6)
8.6 Exercises	401	(6)
9 Search Trees	407	(78)
9.1 Binary Search Trees	410	(11)
9.2 AVL Trees	421	(11)
9.3 Splay Trees	432	(11)
9.4 (2,4) Trees	443	(12)
9.5 Red-Black Trees	455	(18)
9.6 External Searching in B-Trees	473
9.7 Exercises	470	(15)
10 Sorting, Sets, and Selection	485	(54)
10.1 Merge-Sort	487	(14)
10.2 Quick-Sort	501	(12)
10.3 A Lower Bound on Comparison-Based Sorting	513	(2)
10.4 Bucket-Sort and Radix-Sort	515	(3)
10.5 Comparison of Sorting Algorithms	518	(2)
10.6 The Set ADT and Union/Find Structures	520	(9)
10.7 Selection	529	(3)
10.8 Exercises	532	(7)
11 Text Processing	539	(42)
11.1 String Operations	541	(3)
11.2 Pattern Matching Algorithms	544	(12)
11.3 Tries	556	(11)
11.4 Text Compression	567	(3)
11.5 Text Similarity Testing	570	(5)
11.6 Exercises	575	(6)
12 Graphs	581	(78)
12.1 The Graph Abstract Data Type	503	(86)
12.2 Data Structures for Graphs	589	(8)
12.3 Graph Traversals	597	(15)
12.4 Directed Graphs	612	(14)
12.5 Weighted Graphs	626	(1)
12.6 Shortest Paths	627	(11)
12.7 Minimum Spanning Trees	638	(10)
12.8 Exercises	648	(11)
A Useful Mathematical Facts	659	(8)
Bibliography	667	(5)
Index	672
0807744174
Foreword by Ann Lieberman vii
Preface	xi
Part I. What Leads to Teacher Research in Schools?
1. Our Journey: Supporting Teacher Research in Schools	3	(6)
Courtney Rogers
2. Out of Our Experience: Useful Theory	9	(14)
3. Developing a Definition of Teacher Research	23	(6)
Part II. What Happens When Teachers Conduct Teacher Research?
4. The Way I Would Teach: Student Knowledge of Teaching and Learning	29	(9)
Marian M. Mohr
5. It All Adds Up: Learning Number Facts in First Grade	38	(11)
Betsy Sanford
6. Paying Attention in a Different Way: How Teacher Researchers Teach	49	(17)
Marian M. Mohr
7. Coming Into Focus: How Teacher Researchers Learn	66	(19)
Courtney Rogers
Part III. How Does Teacher Research Affect Schools?
8. Roles and Relationships: Principals and Teacher Researcher Leaders	85	(11)
Mary Ann Nocerino
9. Not Entirely by Design: Teacher Research and School Planning	96	(11)
Marion S. MacLean
10. The Leaven in the Loaf: Teacher Research Knowledge in Schools	107	(11)
Courtney Rogers
11. Teacher Researcher Leadership	118	(11)
Mary Ann Nocerino
12. The Teacher Researcher Network	129	(14)
Courtney Rogers
Part IV. What Does Teacher Research in Schools Mean to the Educational Community?
13. Recommendations for Teacher Colleagues	143	(6)
Betsy Sanford
14. Recommendations for School-Level Administrators	149	(4)
Mary Ann Nocerino
15. Recommendations for Central Office Administrators	153	(5)
Courtney Rogers
16. Recommendations for Teacher Educators and Professional Developers	158	(3)
Marion S. MacLean
17. Recommendations for Parents and School Communities	161	(4)
Marian M. Mohr
18. How Teacher Research Can Affect Decision Making in the Educational Community	165	(14)
Bibliography	179	(4)
Index	183	(8)
About the Authors	191