Data Structures and Algorithms in Java, 6ed (An Indian Adaptation)

Description

Data Structures and Algorithms in Java offers a comprehensive, definitive introduction to data structures and algorithms, including their design, analysis, and implementation in Java. The contents of the book are organized to provide a pedagogical path that starts with the basics of Java programming and object-oriented design and foundational techniques such as algorithm analysis and recursion. The book then presents fundamental data structures, such as arrays, linked lists, stacks, queues, trees, heaps, maps, hash tables, search trees, and graphs, concluding with a discussion on searching and sorting algorithms and memory management. The book incorporates a host of pedagogical features, including illustrations, code fragments, and end-of-chapter exercises.

About the Author

Michael T. Goodrich is a Chancellor’s Professor in the Department of Computer Science at University of California, Irvine. Previously, he was a professor at Johns Hopkins University. His research interests include analysis, design, and implementation of algorithms, data security, cloud computing, graph drawing, and computational geometry. He is a Fulbright scholar and a fellow of the American Association for the Advancement of Science (AAAS), Association for Computing Machinery (ACM), and Institute of Electrical and Electronics Engineers (IEEE).

Roberto Tamassia is the Plastech Professor of Computer Science in the Department of Computer Science at Brown University. He is also the Director of Brown’s Center for Geometric Computing. His research interests include data security, applied cryptography, cloud computing, analysis, design, and implementation of algorithms, graph drawing, and computational geometry. He is a fellow of the American Association for the Advancement of Science (AAAS), Association for Computing Machinery (ACM), and Institute of Electrical and Electronics Engineers (IEEE).

Michael Goldwasser is currently a Professor in the Department of Mathematics and Computer Science at Saint Louis University and the Director of their Computer Science program. Previously, he was a faculty member in the Department of Computer Science at Loyola University Chicago. His research interests focus on the design and implementation of algorithms, having published work involving approximation algorithms, online computation, computational biology, and computational geometry.

Table of Contents

Book Review

1 Introduction to Java

1.1 Preliminaries

1.2 Objects and Classes

1.3 Special Types

1.4 Java Expressions

1.5 Control Flow

1.6 Input and Output

1.7 Java Packages

1.8 Writing a Java Program

2 Object-Oriented Programming

2.1 Goals, Principles, and Patterns

2.2 Inheritance

2.3 Interfaces and Abstract Classes

2.4 Exception

2.5 Casting and Generics

2.6 Nested Classes

3 Introduction to Data Structures and Algorithms

3.1 Data Structures

3.2 Empirical Analysis

3.2.1 Moving Beyond Experimental Analysis

3.3 Common Mathematical Functions

3.4 Asymptotic Notations

4 Arrays and Linked Lists

4.1 Practical Uses of Arrays

4.2 Singly Linked Lists

4.3 Circularly Linked Lists

4.4 Doubly Linked Lists

4.5 Testing for Equality

4.6 Copying Data Structures

5 Recursion

5.1 Foundations of Recursion

5.2 Recursive Analysis

5.3 Applications of Recursion

5.4 Using Recursion

5.5 Pitfalls of Recursion

6 Stacks and Queues

6.1 Stacks

6.2 Queues

6.3 Double-Ended Queues

7 List Abstractions

7.1 The List ADT

7.2 Array-Based Lists

7.3 Position-Based Lists

7.4 Iterators

7.5 The Collections Framework

8 Trees

8.1 Trees Definitions and Properties

8.2 Binary Trees

8.3 Tree Representations

8.4 Tree Traversal Algorithms

9 Priority Queues and Heaps

9.1 The Priority Queue Abstract Data Type

9.2 Implementing a Priority Queue

9.3 Heaps

9.4 Sorting with a Priority Queue

9.5 Adaptable Priority Queues

10 Maps, Hash Tables, and Skip Lists

10.1 The Map Abstract Data Type

10.2 Hashing

10.3 The Sorted Map Abstract Data Type

10.4 Skip Lists

10.5 Sets, Multisets, and Multimaps

11 Search Trees

11.1 Binary Search Trees

11.2 Balanced Search Trees

11.3 AVL Trees

11.4 (2, 4) Trees

11.5 Red-Black Trees

11.6 Splay Trees

12 Graphs

12.1 Graphs

12.2 Data Structures for Graphs

12.3 Graph Traversals

12.4 Transitive Closure

12.5 Directed Acyclic Graphs

12.6 Shortest Paths

12.7 Minimum Spanning Trees

13 Strings and Dynamic Programming

13.1 Preliminaries

13.2 Pattern-Matching Algorithms

13.3 Tries

13.4 Text Compression and the Greedy Method

13.5 Dynamic Programming

14 Sorting and Selection

14.1 Merge-Sort

14.2 Quick-Sort

14.3 Studying Sorting through an Algorithmic Lens

14.4 Comparing Sorting Algorithms

14.5 Selection

15 Additional Topics

15.1 Memory Management

15.2 Memory Hierarchies and Caching

15.3 External Searching and B-Trees

15.4 Binomial Heap

15.5 External-Memory Sorting

15.6 Range Trees

Exercises

Multiple Choice Questions

Chapter Notes

Answer Key

Appendix A: Useful Mathematical Facts

Bibliography

Index