Register your product to gain access to bonus material or receive a coupon.
Data Structures and Problem Solving Using Java
- By Mark A. Weiss
- Published Oct 16, 1997
Premium Website
- Sorry, this book is no longer in print.
About
Features
- Takes a unique approach by separating the interface of a data structure (Part 2) from their implementations (Part 4), to motivate abstract thinking and problem solving. Students use the data structures in Part 3 (Applications).
- Contains extensive sample code using Java 1.1, which is available over the Internet and has been tested and reviewed by a professional programmer for accuracy. (Code approved by Sun.)
- Contains advanced data structures in Part 5.
Description
- Copyright 1998
- Edition: 1st
- Premium Website
- ISBN-10: 0-201-54991-3
- ISBN-13: 978-0-201-54991-1
Data Structures and Problem Solving Using Java teaches data structures and algorithms from the perspective of abstract thinking and problem solving. In this text, experienced author and educator Mark Allen Weiss takes a unique approach by clearly separating the specification and implementation of data structures. Dr. Weiss presents the interface and running time of data structures in Part II of the book. Then, he provides the opportunity for students to use the data structures in a variety of practical examples before introducing the implementations in Part IV. By first gaining a familiarity with the interfaces and uses of data structures, readers will be able to think more abstractly about the subject matter.
Features- Contains extensive sample code using Java 1.1, which is available over the Internet and has been tested and reviewed by a professional programmer for accuracy.
- Provides an introduction to Java in Part I and also covers Graphical User Interfaces (GUI's) in an appendix.
- Includes pedagogical aids such as margin notes and comprehensive end-of-chapter material to help readers grasp challenging concepts.
- Offers flexibility in topic coverage by minimizing dependencies among the different chapters.
0201549913B04062001
Sample Content
Table of Contents
I. TOUR OF JAVA.
1. Primitive Java.
The General Environment.
The First Program.
Comments.
main.
Terminal Output.
Primitive Types.
The Primitive Types.
Constants.
Declaration and Initialization of Primitive Types.
Terminal Input and Output.
Basic Operators.
Assignment Operators.
Binary Arithmetic Operators.
Unary Operators.
Type Conversions.
Conditional Statements.
Relational and Equality Operators.
Logical Operators.
The if Statement.
The while Statement.
The for Statement.
The do Statement.
break and continue.
The switch Statement.
The Conditional Operator.
Methods.
Overloading of Method Names.
Storage Classes.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
2. References.
What Is a Reference?
Basics of Objects and References.
The Dot Operator (.).
Declaration of Objects.
Garbage Collection.
The Meaning of =.
Parameter Passing.
The Meaning of ==.
Operator Overloading for Objects.
Strings.
Basics of String Manipulation.
String Concatenation.
Comparing Strings.
Other String Methods.
Converting between Strings and Primitive Types.
Arrays.
Declaration, Assignment, and Methods.
Dynamic Array Expansion.
Multidimensional Arrays.
Command-line Arguments.
Exception Handling.
Processing Exceptions.
The finally Clause.
Common Exceptions.
The throw and throws Clauses.
Input and Output.
Basic Stream Operations.
The StringTokenizer Object.
Sequential Files.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
3. Objects and Classes.
What Is Object-oriented Programming?
A Simple Example.
Javadoc.
Basic Methods.
Constructors.
Mutators and Accessors.
Output and toString.
equals.
static Methods.
main.
Packages.
The import Directive.
The package Statement.
The CLASSPATH Environment Variable.
Package-friendly Visibility Rules.
Separate Compilation.
Additional Constructs.
The this Reference.
The this Shorthand for Constructors.
The instanceof Operator.
Static Fields.
Static Initializers.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
4. Inheritance.
What Is Inheritance?
Basic Java Syntax.
Visibility Rules.
The Constructor and super.
final Methods and Classes.
Overriding a Method.
Abstract Methods and Classes.
Example: Expanding the Shape Class.
Digression: An Introduction to Sorting.
Multiple Inheritance.
The Interface.
Specifying an Interface.
Implementing an Interface.
Multiple Interfaces.
Implementing Generic Components.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
II. ALGORITHMS AND BUILDING BLOCKS.
5. Algorithm Analysis.
What Is Algorithm Analysis?
Examples of Algorithm Running Times.
The Maximum Contiguous Subsequence Sum Problem.
The Obvious O (N) Algorithm.
An Improved O(N 2) Algorithm.
A Linear Algorithm.
General Big-Oh Rules.
The Logarithm.
Static Searching Problem.
Sequential Search.
Binary Search.
Interpolation Search.
Checking an Algorithm Analysis.
Limitations of Big-Oh Analysis.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
6. Data Structures.
Why Do We Need Data Structures?
Stacks.
Stacks and Computer Languages.
Queues.
Linked Lists.
General Trees.
Binary Search Trees.
Hash Tables.
Priority Queues.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
7. Recursion.
What Is Recursion?
Background: Proofs by Mathematical Induction.
Basic Recursion.
Printing Numbers in Any Base.
Why It Works.
How It Works.
Too Much Recursion Can Be Dangerous.
Additional Examples.
Numerical Applications.
Modular Arithmetic.
Modular Exponentiation.
Greatest Common Divisor and Multiplicative Inverses.
The RSA Cryptosystem.
Divide-and-Conquer Algorithms.
The Maximum Contiguous Subsequence Sum Problem.
Analysis of a Basic Divide-and-Conquer Recurrence.
A General Upper Bound for Divide-and-Conquer Running Times.
Dynamic Programming.
Backtracking Algorithms.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
8. Sorting Algorithms.
Why Is Sorting Important?
Preliminaries.
Analysis of the Insertion Sort and Other Simple Sorts.
Shellsort.
Performance of Shellsort.
Mergesort.
Linear-time Merging of Sorted Arrays.
The Mergesort Algorithm.
Quicksort.
The Quicksort Algorithm.
Analysis of Quicksort.
Picking the Pivot.
A Partitioning Strategy.
Keys Equal to the Pivot.
Median-of-three Partitioning.
Small Arrays.
Java Quicksort Routine.
Quickselect.
A Lower Bound for Sorting.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
9. Randomization.
Why Do We Need Random Numbers?
Random-number Generators.
Nonuniform Random Numbers.
Generating a Random Permutation.
Randomized Algorithms.
Randomized Primality Testing.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
III. APPLICATIONS.
10. Fun and Games.
10.1Word Search Puzzles.
Theory.
Java Implementation.
10.2The Game of Tic-Tac-Toe.
Alpha-beta Pruning.
Transposition Tables.
Computer Chess.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
11. Stacks and Compilers.
Balanced-symbol Checker.
Basic Algorithm.
Implementation.
A Simple Calculator.
Postfix Machines.
Infix to Postfix Conversion.
Implementation.
Expression Trees.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
12. Utilities.
File Compression.
Prefix Codes.
Huffman's Algorithm.
The Encoding Phase.
Decoding Phase.
Practical Considerations.
A Cross-Reference Generator.
Basic Ideas.
Java Implementation.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
13. Simulation.
The Josephus Problem.
The Simple Solution.
A More Efficient Algorithm.
Event-driven Simulation.
Basic Ideas.
Example: A Modem Bank Simulation.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
14. Graphs and Paths.
Definitions.
Representation.
Unweighted Shortest-path Problem.
Theory.
Java Implementation.
Positive-weighted, Shortest-path Problem.
Theory: Dijkstra's Algorithm.
Java Implementation.
Negative-weighted, Shortest-path Problem.
Theory.
Java Implementation.
Path Problems in Acyclic Graphs.
Topological Sorting.
Theory of the Acyclic Shortest-path Algorithm.
Java Implementation.
An Application: Critical-path Analysis.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
IV. IMPLEMENTATIONS.
15. Stacks and Queues.
Dynamic Array Implementations.
Stacks.
Queues.
Linked-list Implementations.
Stacks.
Queues.
Comparison of the Two Methods.
Double-ended Queues.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
16. Linked Lists.
Basic Ideas.
Header Nodes.
Iterator Classes.
Java Implementation.
Doubly Linked Lists and Circular Linked Lists.
Sorted Linked Lists.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
17. Trees.
General Trees.
Definitions.
Implementation.
An Application: File Systems.
Binary Trees.
Recursion and Trees.
Tree Traversal: Iterator Classes.
Postorder Traversal.
Inorder Traversal.
Preorder Traversal.
Level-order Traversals.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
18. Binary Search Trees.
Basic Ideas.
The Operations.
Java Implementation.
Order Statistics.
Java Implementation.
Analysis of Binary Search Tree Operations.
AVL Trees.
Properties.
Single Rotation.
Double Rotation.
Summary of AVL Insertion.
Red-Black Trees.
Bottom-up Insertion.
Top-down Red-Black Trees.
Java Implementation.
Top-down Deletion.
AA-Trees.
Insertion.
Deletion.
Java Implementation.
B-Trees.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
19. Hash Tables.
Basic Ideas.
Hash Function.
Linear Probing.
Naive Analysis of Linear Probing.
What Really Happens: Primary Clustering.
Analysis of the find Operation.
Quadratic Probing.
Java Implementation.
Analysis of Quadratic Probing.
Separate Chaining Hashing.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
20. A Priority Queue: The Binary Heap.
Basic Ideas.
Structure Property.
Heap-order Property.
Allowed Operations.
Implementation of the Basic Operations.
insert.
deleteMin.
fixHeap: Linear Time Heap Construction.
Advanced Operations: decreaseKey and merge.
Internal Sorting: Heapsort.
External Sorting.
Why We Need New Algorithms.
Model for External Sorting.
The Simple Algorithm.
Multiway Merge.
Polyphase Merge.
Replacement Selection.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
V. ADVANCED DATA STRUCTURES.
21. Splay Trees.
Self-adjustment and Amortized Analysis.
Amortized Time Bounds.
A Simple Self-adjusting Strategy (That Does Not Work).
The Basic Bottom-up Splay Tree.
Basic Splay Tree Operations.
Analysis of Bottom-up Splaying.
Proof of the Splaying Bound.
Top-down Splay Trees.
Implementation of Top-down Splay Trees.
Comparison of the Splay Tree with Other Search Trees.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
22. Merging Priority Queues.
The Skew Heap.
Merging Is Fundamental.
Simplistic Merging of Heap-Ordered Trees.
The Skew Heap: A Simple Modification.
Analysis of the Skew Heap.
The Pairing Heap.
Pairing Heap Operations and Theory.
Implementation of the Pairing Heap.
Application: Dijkstra's Shortest Weighted Path Algorithm.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
References.
23. The Disjoint Set Class.
Equivalence Relations.
Dynamic Equivalence and Two Applications.
Application #1: Minimum Spanning Trees.
Application #2: The Nearest Common Ancestor Problem.
The Quick-find Algorithm.
The Quick-union Algorithm.
Smart Union Algorithms.
Path Compression.
Java Implementation.
Worst Case for Union-by-rank and Path Compression.
Analysis of the Union/Find Algorithm.
Summary.
Objects of the Game.
Common Error.
On the Internet.
Exercises.
References.
APPENDICES.
Appendix A: Java Platforms.
Setting the Environment.
Unix Instructions.
Windows 95/NT Instructions.
Sun's JDK.
Visual Development Environments.
Symantec Cafe.
Microsoft Visual J++.
Appendix B: Operators.
Appendix C: Some Library Routines .
Classes in Package java.lang.
Character.
Integer.
Object.
String.
StringBuffer.
System.
Thread.
Throwable.
Classes in Package java.io.
BufferedReader.
File.
FileReader.
InputStreamReader.
PushbackReader.
Classes in Package java.util.
Random.
StringTokenizer.
Vector.
On the Internet.
Appendix D: Graphical User Interfaces.
The Abstract Window Toolkit.
Basic Objects in the AWT.
Component.
Container.
Top-level Windows.
Panel.
Important I/O Components.
Basic AWT Principles.
Layout Managers.
Graphics.
Events.
Summary: Putting the Pieces Together.
Animations and Threads.
Applets.
Hypertext Markup Language.
Parameters.
Applet Limitations.
Making an Application an Applet.
Applets with Animation.
Summary.
Objects of the Game.
Common Errors.
On the Internet.
Exercises.
Reference.
Index. 0201549913T04062001