Universities Press

Data Structures, Algorithms, and Applications in JAVA

Sartaj Sahni

ISBN: 9788173715235 | Year: 2005 | Paperback | Pages: 872 | Language : English

Book Size: 180 x 240 mm | Territorial Rights: Restricted

Price: 1250.00

About the Book

Data Structures, Algorithms, and Applications in JAVA (2nd Edition) is the new version of the very popular first edition. It provides a comprehensive coverage of fundamental data structures, making it ideal for use in computer science courses. The author has made the book very user friendly by starting with a gentle introduction, providing intuitive discussions, and including real-world applications. Real-world applications are a unique feature of this text. Dr Sahni provides several applications for each data structure and algorithm design method discussed, taking examples from topics such as sorting, compression and coding, and image processing. These applications motivate and interest students by connecting concepts with their use. Dr Sahni does an excellent job of balancing theoretical and practical information, resulting in learned concepts and interested students. The market-developed pedagogy in this book reinforces concepts and gives students plenty of practice. There are almost 1,000 exercises, including comprehension and simple programming problems, and projects. Additionally, the book has an associated website that contains all the programs in the book, animations, sample data, generated output, solutions to selected exercises, and sample tests with answers.

Contributors (Author(s), Editor(s), Translator(s), Illustrator(s) etc.)

Sartaj Sahni is a Distinguished Professor and Chair of Computer & Information Sciences & Engineering at the University of Florida. He is a member of the European Academy of Sciences, a Fellow of IEEE, ACM, AAAS, and Minnesota Supercomputer Institute, and a Distinguished Alumnus of the IIT, Kanpur. Dr Sahni is the recipient of the 1997 IEEE Computer Society Taylor L Booth Education Award, the 2003 IEEE Computer Society W.Wallace McDowell Award and the 2003 ACM Karl karlstrom Outstanding Educator Award. Dr Sahni received his B.Tech. (EE) degree from the IIT, Kanpur, and MS and PhD degress in Computer Science from Cornell University. Dr Sahni has published over 250 research papers and written 15 texts. His research publications are on the design and analysis of efficient algorithms, parallel computing, interconnection networks, design automation, and medical algorithms.

Table of Content

PARTI PRELIMINARIES
1.	Java Review
	1.1	Introduction
	1.2	Structure of a Java Program
		1.2.1	Stand-Alone Programs and Applets
		1.2.2	Packages
		1.2.3	Importing Classes and Packages
		1.2.4	Superclasses and Subclasses
	1.3	The Java Compiler and Virtual Machine
	1.4	Documentation Comments
	1.5	Data Types
	1.6	Methods
		1.6.1	Parameters
		1.6.2	Overloaded Methods
	1.7	Exceptions
		1.7.1	Throwing an Exception
		1.7.2	Handling Exceptions
	1.8	Your Very Own Data Type
		1.8.1	The Class Currency
		1.8.2	The Data Members of Currency
		1.8.3	The Method Members of Currency
		1.8.4	The Constructors of Currency
		1.8.5	Creating Instances of Currency
		1.8.6	The Accessor Methods of Currency
		1.8.7	The Mutator Methods of Currency
		1.8.8	Invoking Methods and Accessing Data Members
		1.8.9	Output and Arithmetic Methods for Currency
		1.8.10	The Method main
	1.9	Access Modifiers
	1.10	Inheritance and Method Overriding
	1.11	Currency Revisited
	1.12	Defining an Exception Class
	1.13	Generic Methods
		1.13.1	The Interface Computable
		1.13.2	The Generic Method abc
		1.13.3	The Interface java. lang. Comparable
		1.13.4	The Interface Operable
		1.13.5	The Interfaces Zero and CloneableObject
		1.13.6	The Wrapper Class Mylnteger
		1.13.7	Using Data Types and Methods as Parameters
	1.14	Garbage Collection
	1.15	Recursion
		1.15.1	Recursive Functions
		1.15.2	Induction
		1.15.3	Recursive Methods
	1.16	Testing and Debugging
		1.16.1	What Is Testing?
		1.16.2	Designing Test Data
		1.16.3	Debugging
	1.17	References and Selected Readings
2	Performance Analysis
	2.1	What Is Performance?
	2.2	Space Complexity
		2.2.1	Components of Space Complexity
		2.2.2	Examples
	2.3	Time Complexity
		2.3.1	Components of Time Complexity
		2.3.2	Operation Counts
		2.3.3	Best, Worst, and Average Operation Counts
		2.3.4	Step Counts
3	Asymptotic Notation
	3.1	Introduction
	3.2	Asymptotic Notation
		3.2.1	Big Oh Notation (O)
		3.2.2	Omega (SI) and Theta (9) Notations
	3.3	Asymptotic Mathematics (Optional)
		3.3.1	Big Oh Notation (O)
		3.3.2	Omega Notation (SI)
		3.3.3	Theta Notation (6)
		3.3.4	Little Oh Notation (o)
		3.3.5	Properties
	3.4	Complexity Analysis Examples
	3.5	Practical Complexities
	3.6	References and Selected Readings
4	Performance Measurement
	4.1	Introduction
	4.2	Choosing Instance Size
	4.3	Developing the Test Data
	4.4	Setting Up the Experiment
	4.5	Your Cache and You
		4.5.1	A Simple Computer Model
		4.5.2	Effect of Cache Misses on Run Time
		4.5.3	Matrix Multiplication
	4.6	References and Selected Readings
PART II DATA STRUCTURES
5	Linear Lists—Array Representation
	5.1	Data Objects and Structures
	5.2	The Linear List Data Structure
		5.2.1	Abstract Data Type LinearList
		5.2.2	The Interface LinearList
		5.2.3	The Abstract Class LinearListAsAbstractClass
	5.3	Array Representation
		5.3.1	The Representation
		5.3.2	Changing the Length of a One-Dimensional Array
		5.3.3	The Class ArrayLinearList
		5.3.4	An Iterator for ArrayLinearList
	5.4	Vector Representation
	5.5	Multiple Lists in a Single Array
	5.6	Performance Measurement
	5.7	The Class Java.util.ArrayList
	5.8	References and Selected Readings
6	Linear Lists—Linked Representation
	6.1	Singly Linked Lists and Chains
		6.1.1	The Representation
		6.1.2	The Class ChainNode
		6.1.3	The Class Chain
		6.1.4	Extensions to the ADT LinearList
		6.1.5	The Class ExtendedChain
		6.1.6	Performance Measurement
	6.2	Circular Lists and Header Nodes
	6.3	Doubly Linked Lists
	6.4	Glossary of Linked List Terms
	6.5	Applications
		6.5.1	Bin Sort
		6.5.2	Radix Sort
		6.5.3	Convex Hull
7	Linear Lists—Simulated Pointers
	7.1	The Need for Simulated Pointers
	7.2	Simulating Pointers
	7.3	Memory Management
		7.3.1	The Class SimulatedSpacel
		7.3.2	The Class SimulatedSpace2
		7.3.3	Evaluation of Simulated Memory Management
	7.4	Comparison with Garbage Collection
	7.5	Simulated Chains
		7.5.1	The Class SimulatedChain
		7.5.2	Performance Measurement
	7.6	Memory Managed Chains
	7.7	Application—Union-Find Problem
		7.7.1	Equivalence Classes
		7.7.2	Applications
		7.7.3	First Union-Find Solution
		7.7.4	Second Union-Find Solution
8	Arrays and Matrices
	8.1	Arrays
		8.1.1	The Abstract Data Type
		8.1.2	Indexing a Java Array
		8.1.3	Row- and Column-Major Mappings
		8.1.4	Array of Arrays Representation
		8.1.5	Row-Major and Column-Major Representation
		8.1.6	Irregular Two-Dimensional Arrays
	8.2	Matrices
		8.2.1	Definitions and Operations
		8.2.2	The Class Matrix
	8.3	Special Matrices
		8.3.1	Definitions and Applications
		8.3.2	Diagonal Matrices
		8.3.3	Tridiagonal Matrix
		8.3.4	Triangular Matrices
		8.3.5	Symmetric Matrices
	8.4	Sparse Matrices
		8.4.1	Motivation
		8.4.2	Representation Using a Single Linear List
		8.4.3	Representation Using Many Linear Lists
		8.4.4	Performance Measurement
9	Stacks
	9.1	Definition and Applications
	9.2	The Abstract Data Type
	9.3	Array Representation
		9.3.1	Implementation as a Subclass
		9.3.2	The Class ArrayStack
		9.3.3	Performance Measurement
	9.4	Linked Representation
		9.4.1	The Class DerivedLinkedStack
		9.4.2	The Class LinkedStack
		9.4.3	Performance Measurement
	9.5	Applications
		9.5.1	Parenthesis Matching
		9.5.2	Towers of Hanoi
		9.5.3	Rearranging Railroad Cars
		9.5.4	Switch Box Routing
		9.5.5	Offline Equivalence Class Problem
		9.5.6	Rat in a Maze
	9.6	References and Selected Readings
10	Queues
	10.1	Definition and Applications
	10.2	The Abstract Data Type
	10.3	Array Representation
		10.3.1	The Representation
		10.3.2	The Class ArrayQueue
	10.4	Linked Representation
	10.5	Applications
		10.5.1	Railroad Car Rearrangement
		10.5.2	Wire Routing
		10.5.3	Image-Component Labeling
		10.5.4	Machine Shop Simulation
	10.6	References and Selected Readings
11	Skip Lists and Hashing
	11.1	Dictionaries
	11.2	The Abstract Data Type
	11.3	Linear List Representation
	11.4	Skip List Representation (Optional)
		11.4.1	The Ideal Case
		11.4.2	Insertions and Deletions
		11.4.3	Assigning Levels
		11.4.4	The Class SkipNode
		11.4.5	The Class SkipList
		11.4.6	Complexity of SkipList Methods
	11.5	Hash Table Representation
		11.5.1	Ideal Hashing
		11.5.2	Hash Functions and Tables
		11.5.3	Linear Probing
		11.5.4	Hashing with Chains
	11.6	An Application—Text Compression
		11.6.1	LZW Compression
		11.6.2	Implementation of LZW Compression
		11.6.3	LZW Decompression
		11.6.4	Implementation of LZW Decompression
		11.6.5	Performance Evaluation
	11.7	References and Selected Readings
12	Binary and Other Trees
	12.1	Trees
	12.2	Binary Trees
	12.3	Properties of Binary Trees
	12.4	Representation of Binary Trees
		12.4.1	Array-Based Representation
		12.4.2	Linked Representation
	12.5	Common Binary Tree Operations
	12.6	Binary Tree Traversal
	12.7	The ADT BinaryTree
	12.8	The Class LinkedBinaryTree
	12.9	Applications
		12.9.1	Placement of Signal Boosters
		12.9.2	Union-Find Problem
	12.10	References and Selected Readings
13	Priority Queues
	13.1	Definition and Applications
	13.2	The Abstract Data Type
	13.3	Linear Lists
	13.4	Heaps
		13.4.1	Definitions
		13.4.2	Insertion into a Max Heap
		13.4.3	Deletion from a Max Heap
		13.4.4	Max Heap Initialization
		13.4.5	The Class MaxHeap
	13.5	Leftist Trees
		13.5.1	Height- and Weight-Biased Min and Max Leftist Trees
		13.5.2	Insertion into a Max HBLT
		13.5.3	Deletion from a Max HBLT
		13.5.4	Melding Two Max HBLTs
		13.5.5	Initialization
		13.5.6	The Class MaxHBLT
	13.6	Applications
		13.6.1	Heap Sort
		13.6.2	Machine Scheduling
		13.6.3	Huffman Codes
	13.7	References and Selected Readings
14	Tournament Trees
	14.1	Winner Trees and Applications
	14.2	The ADT WinnerTree
	14.3	Winner Tree Implementation
		14.3.1	Representation
		14.3.2	Initializing a Winner Tree
		14.3.3	Replaying Matches
		14.3.4	The Class CompleteWinnerTree
	14.4	Loser Trees
	14.5	Applications
		14.5.1	Bin Packing Using First Fit
		14.5.2	Bin Packing Using Next Fit
	14.6	References and Selected Readings
15	Binary Search Trees
	15.1	Definitions
		15.1.1	Binary Search Trees
		15.1.2	Indexed Binary Search Trees
	15.2	Abstract Data Types
	15.3	Binary Search Tree Operations and Implementation
		15.3.1	The Class BinarySearchTree
		15.3.2	Searching
		15.3.3	Inserting an Element
		15.3.4	Deleting an Element
		15.3.5	Height of a Binary Search Tree
	15.4	Binary Search Trees with Duplicates
	15.5	Indexed Binary Search Trees
	15.6	Applications
		15.6.1	Histogramming
		15.6.2	Best-Fit Bin Packing
		15.6.3	Crossing Distribution
16	Balanced Search Trees
	16.1	AVL Trees
		16.1.1	Definition
		16.1.2	Height of an AVL Tree
		16.1.3	Representation of an AVL Tree
		16.1.4	Searching an AVL Search Tree
		16.1.5	Inserting into an AVL Search Tree
		16.1.6	Deletion from an AVL Search Tree
	16.2	Red-Black Trees
		16.2.1	Definition
		16.2.2	Representation of a Red-Black Tree
		16.2.3	Searching a Red-Black Tree
		16.2.4	Inserting into a Red-Black Tree
		16.2.5	Deletion from a Red-Black Tree
		16.2.6	Implementation Considerations and Complexity
	16.3	Splay Trees
		16.3.1	Introduction
		16.3.2	The Splay Operation
		16.3.3	Amortized Complexity
	16.4	B-Trees
		16.4.1	Indexed Sequential Access Method (ISAM)
		16.4.2	m-Way Search Trees
		16.4.3	B-Trees of Order m
		16.4.4	Height of a B-Tree
		16.4.5	Searching a B-Tree
		16.4.6	Inserting into a B-Tree
		16.4.7	Deletion from a B-Tree
		16.4.8	Node Structure
	16.5	References and Selected Readings
17	Graphs
	17.1	Definitions
	17.2	Applications and More Definitions
	17.3	Properties
	17.4	The ADT Graph
	17.5	Representation of Unweighted Graphs
		17.5.1	Adjacency Matrix
		17.5.2	Linked Adjacency Lists
		17.5.3	Array Adjacency Lists
	17.6	Representation of Weighted Graphs
	17.7	Class Implementations
		17.7.1	The Different Classes
		17.7.2	Adjacency-Matrix Classes
		17.7.3	An Extension to the Class Chain
		17.7.4	Linked-List Classes
	17.8	Graph Search Methods
		17.8.1	Breadth-First Search
		17.8.2	Implementation of Breadth-First Search
		17.8.3	Complexity Analysis of Graph.bfs
		17.8.4	Depth-First Search
		17.8.5	Implementation of Depth-First Search
		17.8.6	Complexity Analysis of Graph.dfs
	17.9	Applications Revisited
		17.9.1	Finding a Path
		17.9.2	Connected Graphs and Components
		17.9.3	Spanning Trees
PART III ALGORITHM-DESIGN METHODS
18	The Greedy Method
	18.1	Optimization Problems
	18.2	The Greedy Method
	18.3	Applications
		18.3.1	Container Loading
		18.3.2	0/1 Knapsack Problem
		18.3.3	Topological Sorting
		18.3.4	Bipartite Cover
		18.3.5	Single-Source Shortest Paths
		18.3.6	Minimum-Cost Spanning Trees
	18.4	References and Selected Readings
19	Divide and Conquer
	19.1	The Method
	19.2	Applications
		19.2.1	Defective Chessboard
		19.2.2	Merge Sort
		19.2.3	Quicksort
		19.2.4	Selection
		19.2.5	Closest Pair of Points
	19.3	Solving Recurrence Equations
	19.4	Lower Bounds on Complexity
		19.4.1	Lower Bound for the Minmax Problem
		19.4.2	Lower Bound for Sorting
20	Dynamic Programming
	20.1	The Method
	20.2	Applications
		20.2.1	0/1 Knapsack Problem
		20.2.2	Matrix Multiplication Chains
		20.2.3	All-Pairs Shortest Paths
		20.2.4	Single-Source Shortest Paths with Negative Costs
		20.2.5	Noncrossing Subset of Nets
	20.3	References and Selected Readings
21	Backtracking (On the Web)
	21.1	The Method
	21.2	Applications
		21.2.1	Container Loading
		21.2.2	0/1 Knapsack Problem
		21.2.3	Max Clique
		21.2.4	Traveling Salesperson
		21.2.5	Board Permutation
22	Branch and Bound (On the Web)
	22.1	The Method
	22.2	Applications
		22.2.1	Container Loading
		22.2.2	0/1 Knapsack Problem
		22.2.3	Max Clique
		22.2.4	Traveling Salesperson
		22.2.5	Board Permutation
Index

Resources

https://www.universitiespress.com/sartajsahni/dsajava?isbn=9788173715235