Data Structures and Algorithms in Java, 2nd Edition

by Michael T. Goodrich (Johns Hopkins Univ.); Roberto Tamassia (Brown Univ.)

• ISBN13: 9780471383673
• ISBN10: 0471383678
• Edition: 2nd
• Format: Hardcover
• Copyright: 2001-01-01
• Publisher: Wiley

Summary

Using the power of technology to go beyond the borders of the printed page, Goodrich and Tamassia have created a book that is conceptually elegant and innovative. It incorporates the object-oriented design paradigm, using Java as the implementation language while also providing the fundamental intuition and analysis of each data structure studied.

Author Biography

Professor Goodrich and Tamassi are well-recognized researchers in data structures and algorithms, having published many papers in this field, with applications to internet computing, information visualization, geographic information systems, computer security, and computer-aided layout. They have an extensive record of research collaboration and 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 and infrastructure support for distance learning.<br> <b>Michael Goodrich</b> received his Ph.D. in Computer Science from Purdue University in 1987. He is currently a professor in the Department of Computer Science at John Hopkins University, and codirector of the Johns Hopkins Center for Algorithms Engineering. He is an editor for the <i>International Journal of Computational Geometry &amp; Applications, Journal of Computational and System Sciences</i>, and <i>Journal of Graph Algorithms and Applications.<br> </i><b>Roberto Tamassia</b> 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 also an editor for <i>Computational Geometry: Theory and Applications</i>, and the <i>Journal of Graph Algorithms and Applications</i>, and previously served on the editorial board of IEEE <i>Transactions on Computers.</i>

Table of Contents

Java Programming	1	(54)
Classes, Types, and Objects	3	(8)
Methods	11	(6)
Expressions	17	(8)
Control Flow	25	(7)
Arrays	32	(1)
Simple Input and Output	33	(3)
An Example Program	36	(4)
Packages	40	(2)
Writing a Java Program	42	(7)
Utilities in the java.lang Package	49	(2)
Exercises	51	(4)
Object-Oriented Design	55	(42)
Goals and Principles	56	(6)
Inheritance and Polymorphism	62	(14)
Exceptions	76	(4)
Interfaces and Abstract Classes	80	(4)
Casting	84	(5)
Design Patterns	89	(3)
Exercises	92	(5)
Analysis Tools	97	(38)
What Is Running Time Anyway?	98	(2)
Pseudo-Code	100	(3)
A Quick Mathematical Review	103	(3)
Simple Justification Techniques *	106	(5)
Analysis of Algorithms	111	(3)
Asymptotic Notation	114	(6)
Asymptotic Analysis	120	(6)
Exercises	126	(9)
Stacks, Queues, and Deques	135	(48)
Stacks	136	(13)
Queues	149	(10)
Linked Lists	159	(7)
Double-Ended Queues	166	(7)
Sample Case Study Application	173	(6)
Exercises	179	(4)
Vectors, Lists, and Sequences	183	(44)
Vectors	185	(9)
Lists	194	(12)
Sequences	206	(5)
Case Study: Bubble-Sort on a Sequence	211	(3)
Iterators	214	(2)
A Hierarchy of Sequence ADTs	216	(3)
Exercises	219	(8)
Trees	227	(58)
The Tree Abstract Data Type	229	(7)
Basic Algorithms on Trees	236	(10)
Binary Trees	246	(17)
Data Structures for Representing Trees	263	(11)
Exercises	274	(11)
Priority Queues	285	(48)
The Priority Queue Abstract Data Type	287	(8)
Implementing a Priority Queue with a Sequence	295	(6)
Heaps	301	(18)
The Locator Design Pattern *	319	(7)
Exercises	326	(7)
Dictionaries	333	(46)
The Dicionary Abstract Data Type	335	(5)
Log Files	340	(1)
Hash Tables	341	(16)
The Ordered Dictionary ADT	357	(1)
Look-Up Tables	358	(4)
Skip Lists	362	(8)
Supporting Locators in a Dictionary *	370	(3)
Exercises	373	(6)
Search Trees	379	(68)
Binary Search Trees	382	(11)
AVL Trees	393	(11)
Multi-Way Search Trees	404	(4)
(2,4) Trees	408	(8)
Red-Black Trees	416	(18)
External Searching *	434	(5)
Exercises	439	(8)
Sorting, Sets, and Selection	447	(48)
Merge-Sort	448	(13)
The Set ADT	461	(6)
Quick-Sort	467	(11)
A Lower Bound on Comparison-Based Sorting	478	(2)
Bucket-Sort and Radix-Sort	480	(3)
Comparison of Sorting Algorithms	483	(1)
Selection	484	(4)
Exercises	488	(7)
Text Processing	495	(42)
String Operations	497	(3)
Pattern Matching Algorithms	500	(12)
Tries	512	(11)
Text Compression	523	(3)
Text Similarity Testing	526	(5)
Exercises	531	(6)
Graphs	537	(80)
The Graph Abstract Data Type	539	(8)
Data Structures for Graphs	547	(10)
Graph Traversal	557	(13)
Directed Graphs	570	(14)
Weighted Graphs	584	(1)
Shortest Paths	585	(11)
Minimum Spanning Trees	596	(10)
Exercises	606	(11)
A Useful Mathematical Facts	617	(8)
Bibliography	625	(5)
Index	630