| |
| |
Preface | |
| |
| |
Table of Contents | |
| |
| |
| |
Introduction to Java | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Java Fundamentals | |
| |
| |
| |
Primitive Types | |
| |
| |
| |
The char Type | |
| |
| |
| |
Classes | |
| |
| |
| |
The String Class | |
| |
| |
| |
Using javadoc Notation for Method Specifications | |
| |
| |
| |
Equality of References and Equality of Objects | |
| |
| |
| |
Local Variables | |
| |
| |
| |
The Scanner Class | |
| |
| |
| |
Arrays | |
| |
| |
| |
Arguments and Parameters | |
| |
| |
| |
Output Formatting | |
| |
| |
Crossword Puzzle | |
| |
| |
Programming Exercises | |
| |
| |
| |
Object Oriented Concepts | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Data Abstraction | |
| |
| |
| |
Abstract Methods and Interfaces | |
| |
| |
| |
Abstract Data Types and Data Structures | |
| |
| |
| |
An Interface and a Class that Implements that Interface | |
| |
| |
| |
Using the FullTimeEmployee Class | |
| |
| |
| |
Inheritance | |
| |
| |
| |
The protected Visibility Modifier | |
| |
| |
| |
Inheritance and Constructors | |
| |
| |
| |
The Subclass Substitution Rule | |
| |
| |
| |
The SalariedEmployee Class | |
| |
| |
| |
Is-a versus Has-a | |
| |
| |
| |
Information Hiding | |
| |
| |
| |
Polymorphism | |
| |
| |
| |
The Unified Modeling Language | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
Developing and Testing a CalendarDate Class | |
| |
| |
| |
Addditional Features of Java | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Static Variables, Constants and Methods | |
| |
| |
| |
Exception Handling | |
| |
| |
| |
Propagating Exceptions | |
| |
| |
| |
The finally Block | |
| |
| |
| |
Exception Handling | |
| |
| |
| |
File Input and Output | |
| |
| |
| |
File Output | |
| |
| |
| |
File Input | |
| |
| |
| |
Method Testing | |
| |
| |
| |
The HourlyEmployeeDriver Class | |
| |
| |
| |
The Java Virtual Machine | |
| |
| |
| |
Pre-Initialization of Fields | |
| |
| |
| |
Garbage Collection | |
| |
| |
| |
Packages | |
| |
| |
| |
Overriding The Object CLASS'S equals Method | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
Analysis of Algorithms | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Estimating The Efficiency of Methods | |
| |
| |
| |
Big-O Notation | |
| |
| |
| |
Getting Big-O Estimates Quickly | |
| |
| |
| |
Big-Omega, Big-Theta and Plain English | |
| |
| |
| |
Growth Rates | |
| |
| |
| |
Trade-Offs | |
| |
| |
| |
Run-Time Analysis | |
| |
| |
| |
Timing | |
| |
| |
| |
Overview of the Random Class | |
| |
| |
| |
Randomness and Timing | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
| |
| |
Let's Make a Deal! | |
| |
| |
| |
The Java Collections Framework | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Collections | |
| |
| |
| |
Collection Classes | |
| |
| |
| |
Storage Structures for Collection Classes | |
| |
| |
| |
Outline of The Java Collections Framework | |
| |
| |
| |
Abstract Classes | |
| |
| |
| |
A Class for Regular Polygons | |
| |
| |
| |
Parameterized Types | |
| |
| |
| |
The Collection Interface | |
| |
| |
| |
The ArrayCollection Class | |
| |
| |
Iterators | |
| |
| |
Design Patterns | |
| |
| |
| |
The List Interface | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
| |
| |
Wear a Developer's Hat and a User's Hat | |
| |
| |
| |
Recursion | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Introduction | |
| |
| |
| |
Factorials | |
| |
| |
| |
Execution Frames | |
| |
| |
| |
Decimal to Binary | |
| |
| |
| |
Fibonacci Numbers | |
| |
| |
| |
Towers of Hanoi | |
| |
| |
| |
Analysis of the move Method | |
| |
| |
| |
Searching an Array | |
| |
| |
| |
Iterative Binary Search | |
| |
| |
| |
Generating Permutations | |
| |
| |
| |
Backtracking | |
| |
| |
| |
An A-maze-ing Application | |
| |
| |
| |
Indirect Recursion | |
| |
| |
| |
The Cost of Recursion | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
| |
| |
Iterative Version of Towers of Hanoi | |
| |
| |
| |
| |
| |
Eight Queens | |
| |
| |
| |
| |
| |
Knight's Tour | |
| |
| |
| |
| |
| |
Sudoku | |
| |
| |
| |
| |
| |
Numbrix | |
| |
| |
| |
Array-Based Lists | |
| |
| |
Chapter Objectives | |
| |
| |
| |
The List Interface | |
| |
| |
| |
THE ArrayList CLASS | |
| |
| |
| |
Method Specifications for the ArrayList Class | |
| |
| |
| |
A Simple Program with an ArrayList Object | |
| |
| |
| |
The ArrayList Class's Heading and Fields | |
| |
| |
| |
Definition of the One-Parameter add Method | |
| |
| |
| |
More Details of the ArrayList Class | |
| |
| |
| |
Application: High-Precision Arithmetic | |
| |
| |
| |
Method Specifications of the VeryLongInt Class | |
| |
| |
| |
Fields of the VeryLongInt Class | |
| |
| |
| |
Method Definitions of the VeryLongInt Class | |
| |
| |
| |
Using the VeryLongInt Class | |
| |
| |
| |
Implementation of the VeryLongIntExample Class | |
| |
| |
| |
Expanding the VeryLongInt Class | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
| |
| |
Expanding the VeryLongInt Class | |
| |
| |
| |
| |
| |
An Integrated Web-Browser and Search Engine, Part I | |
| |
| |
| |
Linked Lists | |
| |
| |
Chapter Objectives | |
| |
| |
| |
What is A Linked List? | |
| |
| |
| |
The SinglyLinkedList Class - A Toy Class! | |
| |
| |
| |
Fields and Method Definitions in the SinglyLinkedList Class | |
| |
| |
| |
Iterating through a SinglyLinkedList Object | |
| |
| |
| |
Expanding the SinglyLinkedList Class | |
| |
| |
| |
Doubly-Linked Lists | |
| |
| |
| |
A User's View of the LinkedList Class | |
| |
| |
| |
The LinkedList Class Versus the ArrayList Class | |
| |
| |
| |
LinkedList Iterators | |
| |
| |
| |
A Simple Program that Uses a LinkedList Object | |
| |
| |
| |
Working with LinkedList Iterators | |
| |
| |
| |
Timing the ArrayList and LinkedList Classes | |
| |
| |
| |
Fields in the LinkedList Class | |
| |
| |
| |
Creating and Maintaining a LinkedList Object | |
| |
| |
| |
Definition of the Two-Parameter add Method | |
| |
| |
| |
APPLICATION: A LINE EDITOR | |
| |
| |
| |
Design of the Editor Class | |
| |
| |
| |
Method Definitions for the Editor Class | |
| |
| |
| |
Big-O Analysis of the Editor Class Methods | |
| |
| |
| |
Design of the EditorExample Class | |
| |
| |
| |
Implementation of the EditorExample Class | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
| |
| |
Expanding the SinglyLinkedList Class | |
| |
| |
| |
| |
| |
Defining the remove() method in SinglyLinkedListIterator | |
| |
| |
| |
| |
| |
Expanding the Line Editor | |
| |
| |
| |
| |
| |
Alternative Design and Implementation of the LinkedList | |
| |
| |
Class | |
| |
| |
| |
| |
| |
An Integrated Web Browser and Search Engine, Part 2 | |
| |
| |
| |
Stacks and Queues | |
| |
| |
Chapter Objectives | |
| |
| |
| |
STACKS | |
| |
| |
| |
The Stack Class | |
| |
| |
| |
A Fatal Flaw | |
| |
| |
| |
Stack Application 1: How Compilers Implement Recursion | |
| |
| |
| |
Stack Application 2: Converting from Infix to Postfix | |
| |
| |
| |
Postfix Notation | |
| |
| |
| |
Transition Matrix | |
| |
| |
| |
Tokens | |
| |
| |
| |
Converting from Infix to Postfix | |
| |
| |
| |
Prefix Notation | |
| |
| |
| |
QUEUES | |
| |
| |
| |
The Queue Interface | |
| |
| |
| |
Implementations of the Queue Interface | |
| |
| |
| |
Computer Simulation | |
| |
| |
| |
Queue Application: A Simulated Car Wash | |
| |
| |
| |
Program Design | |
| |
| |
| |
Fields in the CarWash Class | |
| |
| |
| |
Method Definitions of the CarWashExample Class | |
| |
| |
| |
The CarWashExample Class | |
| |
| |
| |
Randomizing the Arrival Times | |
| |
| |
| |
Randomizing the Arrival Times | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
Extending Speedo's Car Wash | |
| |
| |
| |
Run-Time Evaluation of a Condition | |
| |
| |
| |
An Iterative Version of Maze-Search | |
| |
| |
| |
Binary Trees | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Definition | |
| |
| |
| |
Properties of Binary Trees | |
| |
| |
| |
The Binary Tree Theorem | |
| |
| |
| |
External Path Length | |
| |
| |
| |
Traversals of a Binary Tree | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
| |
Binary Search Trees | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Binary Search Trees | |
| |
| |
| |
The BinarySearchTree Implementation of the Set Interface | |
| |
| |
| |
Implementation of the BinarySearchTree Class | |
| |
| |
| |
Fields and Embedded Classes of the BinarySearchTree Class | |
| |
| |
| |
Implementation of Simple Methods in the BinarySearchTree Class | |
| |
| |
| |
Definition of the contains Method | |
| |
| |
| |
Definition of the add Method | |
| |
| |
| |
Definition of the remove Method | |
| |
| |
| |
The TreeIterator Class | |
| |
| |
| |
A Run-Time Estimate of the Height of a BinarySearchTree Object | |
| |
| |
| |
Balanced Binary Search Trees | |
| |
| |
| |
AVL Trees | |
| |
| |
| |
The Height of an AVL Tree | |
| |
| |
| |
The AVLTree Class | |
| |
| |
| |
Run-Time Estimates | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
An Alternate Design and Implementation of the BinarySearchTree Class | |
| |
| |
| |
Printing a BinarySearchTree Object | |
| |
| |
| |
The fixAfterInsertion Method in the AVLTree Class | |
| |
| |
| |
The fixAfterDeletion Method in the AVLTree Class | |
| |
| |
| |
Sorting | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Introduction | |
| |
| |
| |
Simple Sorts | |
| |
| |
| |
Insertion Sort | |
| |
| |
| |
Selection Sort | |
| |
| |
| |
Bubble Sort | |
| |
| |
| |
The Comparator Interface | |
| |
| |
| |
How Fast Can We Sort? | |
| |
| |
| |
Merge Sort | |
| |
| |
| |
Other Merge Sort Methods | |
| |
| |
| |
The Divide-and-Conquer Design Pattern | |
| |
| |
| |
Quick Sort | |
| |
| |
| |
Optimizations to the Quick Sort Algorithm | |
| |
| |
| |
Radix Sort | |
| |
| |
| |
Run-Times for Sort Methods | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Project 11.1 | |
| |
| |
File Sorting | |
| |
| |
| |
Tree Maps and Tree Sets | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Red-Black Trees | |
| |
| |
| |
The Height of a Red-Black Tree | |
| |
| |
| |
The Map Interface | |
| |
| |
| |
THE TreeMap Implementation of the Map Interface | |
| |
| |
| |
The TreeMap Class's Fields and Embedded Entry Class | |
| |
| |
| |
Method Definitions in the TreeMap Class | |
| |
| |
| |
The fixAfterInsertion Method | |
| |
| |
| |
The fixAfterDeletion Method | |
| |
| |
| |
Application: A Simple Thesaurus | |
| |
| |
| |
Design and Implementation of the Thesaurus Class | |
| |
| |
| |
Design of the ThesaurusExample Class | |
| |
| |
| |
Implementation of the ThesaurusExample Class | |
| |
| |
| |
Tree Sort | |
| |
| |
| |
Calling treeSort | |
| |
| |
| |
Analysis of treeSort | |
| |
| |
| |
The TreeSet CLASS | |
| |
| |
| |
Fields and Implementation of the TreeSet Class | |
| |
| |
| |
Application: A Simple Spell Checker | |
| |
| |
| |
Design and Implementation of the SpellChecker Class | |
| |
| |
| |
Design of the SpellCheckerExample Class | |
| |
| |
| |
Implementation of the SpellCheckerExample Class | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
Enhancing the SpellChecker Project | |
| |
| |
| |
Determining Word Frequencies | |
| |
| |
| |
Building a Concordance | |
| |
| |
| |
An Integrated Web-Browser and Search Engine, Part 3 | |
| |
| |
| |
Priority Queues | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Introduction | |
| |
| |
| |
THE PriorityQueue Class | |
| |
| |
| |
Implementations of The PriorityQueue Class | |
| |
| |
| |
Fields and Method Definitions in the PriorityQueue Class | |
| |
| |
| |
The FixUp Method | |
| |
| |
| |
The element() and remove() Methods | |
| |
| |
| |
The fixDown (int k) Method | |
| |
| |
| |
Incorporating Fairness in Priority Queues | |
| |
| |
| |
The heapSort Method | |
| |
| |
| |
Analysis of heapSort | |
| |
| |
| |
Application of Priority Queues: Huffman Codes | |
| |
| |
| |
Huffman Trees | |
| |
| |
| |
The Greedy-Algorithm Design Pattern | |
| |
| |
| |
The Huffman Encoding Project | |
| |
| |
| |
The HuffmanEncoder Class | |
| |
| |
| |
Method Definitions in the HuffmanEncoder Class | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
| |
| |
Decoding a Huffman-encoded Message | |
| |
| |
| |
| |
| |
An Integrated Web-Browser and Search Engine, Part 4 | |
| |
| |
| |
Hashing | |
| |
| |
Chapter Objectives | |
| |
| |
| |
A Framework to Analyze Searching | |
| |
| |
| |
A Review of Searching | |
| |
| |
| |
Sequential Search | |
| |
| |
| |
Binary Search | |
| |
| |
| |
Red-Black Tree Search | |
| |
| |
| |
The HashMap Implementation of The Map Interface | |
| |
| |
| |
Hashing | |
| |
| |
| |
The Uniform Hashing Assumption | |
| |
| |
| |
Chaining | |
| |
| |
| |
Implementation of the HashMap Class | |
| |
| |
| |
Analysis of containsKey Method | |
| |
| |
| |
The HashIterator Class | |
| |
| |
| |
APPLICATION: Creating a Symbol Table | |
| |
| |
| |
Design of the Hasher Class | |
| |
| |
| |
Implementation of the Hasher Class | |
| |
| |
| |
THE HashSet Class | |
| |
| |
| |
Timing the Hash Classes | |
| |
| |
| |
Open-Address Hashing (Optional) | |
| |
| |
| |
The remove Method | |
| |
| |
| |
Primary Clustering | |
| |
| |
| |
Double Hashing | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
Double-Hashing Implementation of the HashMap Class | |
| |
| |
| |
An Integrated Web-Browser and Search Engine, Part 5 | |
| |
| |
| |
Graphs, Trees and Networks | |
| |
| |
Chapter Objectives | |
| |
| |
| |
Undirected Graphs | |
| |
| |
| |
Directed Graphs | |
| |
| |
| |
Trees | |
| |
| |
| |
Networks | |
| |
| |
| |
Graph Algorithms | |
| |
| |
| |
Iterators | |
| |
| |
| |
Breadth-First Iterators | |
| |
| |
| |
Depth-First Iterators | |
| |
| |
| |
Connectedness | |
| |
| |
| |
Generating a Minimal Spanning Tree | |
| |
| |
| |
Finding the Shortest Path through a Network | |
| |
| |
| |
Finding the Longest Path through a Network | |
| |
| |
| |
Topological Sorting | |
| |
| |
| |
A Network CLASS | |
| |
| |
| |
Method Specifications of the Network Class | |
| |
| |
| |
Fields in the Network Class | |
| |
| |
| |
Method Definitions in the Network Class | |
| |
| |
| |
The Traveling Salesperson Problem | |
| |
| |
| |
Application: Backtracking Through A Network | |
| |
| |
Summary | |
| |
| |
Crossword Puzzle | |
| |
| |
Concept Exercises | |
| |
| |
Programming Exercises | |
| |
| |
| |
Solving the Travelling Salesperson Problem | |
| |
| |
| |
Backtracking through a Network | |
| |
| |
| |
Determining Critical Activities in a Project Network | |
| |
| |
| |
An Integrated Web-Browser and Search Engine, Part 6 | |
| |
| |
| |
Additional Features of The Java Collections Framework | |
| |
| |
| |
Introduction | |
| |
| |
| |
Serialization | |
| |
| |
| |
Fail-Fast Iterators | |
| |
| |
| |
Mathematical Background | |
| |
| |
| |
Introduction | |
| |
| |
| |
Functions and Sequences | |
| |
| |
| |
Sums and Products | |
| |
| |
| |
Logarithms | |
| |
| |
| |
Mathematical Induction | |
| |
| |
The Principle of Mathematical Induction | |
| |
| |
| |
Sum of Initial Sequence of Positive Integers | |
| |
| |
| |
Number of Iterations of "Halving" Loop | |
| |
| |
| |
Upper-Bound on nth Fibonacci Number | |
| |
| |
| |
Closed-Form Formula for nth Fibonacci Number | |
| |
| |
| |
Upper-Bound on Number of Leaves in a Non-Empty Binary Tree | |
| |
| |
| |
The Height of a Red-Black Tree Induction and Recursion | |
| |
| |
Concept Exercises | |
| |
| |
| |
Choosing A Data Structure | |
| |
| |
| |
Introduction | |
| |
| |
| |
Time-Based Ordering | |
| |
| |
| |
Index-Based Ordering | |
| |
| |
| |
Comparison-Based Ordering | |
| |
| |
| |
Hash-Based Ordering | |
| |
| |
ReferenceS | |
| |
| |
Index | |