Contents
Colophon
Dedication
Preface
Goals
Approach
Outline
Suggested Course Outline
Online Course Materials
Introduction
What This Book Is About
Object-Oriented Design
Abstraction
Encapsulation
Object Hierarchies and Design Patterns
Containers
Enumerations
Visitors
Cursors
Adapters
Singletons
The Features of Java You Need to Know
Variables
Primitive Types and Reference Types
Parameter Passing
Classes and Objects
Inheritance
Interfaces and Polymorphism
Other Features
How This Book Is Organized
Models and Asymptotic Analysis
Foundational Data Structures
Abstract Data Types and the Class Hierarchy
Data Structures
Algorithms
Algorithm Analysis
A Detailed Model of the Computer
The Basic Axioms
A Simple Example-Arithmetic Series Summation
Array Subscripting Operations
Another Example-Horner's Rule
Analyzing Recursive Methods
Solving Recurrence Relations-Repeated Substitution
Yet Another Example-Finding the Largest Element of an Array
Average Running Times
About Harmonic Numbers
Best-Case and Worst-Case Running Times
The Last Axiom
A Simplified Model of the Computer
An Example-Geometric Series Summation
About Arithmetic Series Summation
Example-Geometric Series Summation Again
About Geometric Series Summation
Example-Computing Powers
Example-Geometric Series Summation Yet Again
Exercises
Projects
Asymptotic Notation
An Asymptotic Upper Bound-Big Oh
A Simple Example
Big Oh Fallacies and Pitfalls
Properties of Big Oh
About Polynomials
About Logarithms
Tight Big Oh Bounds
More Big Oh Fallacies and Pitfalls
Conventions for Writing Big Oh Expressions
An Asymptotic Lower Bound-Omega
A Simple Example
About Polynomials Again
More Notation-Theta and Little Oh
Asymptotic Analysis of Algorithms
Rules For Big Oh Analysis of Running Time
Example-Prefix Sums
Example-Fibonacci Numbers
Example-Bucket Sort
Reality Check
Checking Your Analysis
Exercises
Projects
Foundational Data Structures
Arrays
Extending Java Arrays
Constructors
assign Method
Accessor Methods
Array Indexing Methods-get and put
Resizing an Array-setBase and setLength
Multi-Dimensional Arrays
Array Subscript Calculations
An Implementation
Constructor
Array Indexing Methods-get and put
Matrices
Dense Matrices
Canonical Matrix Multiplication
Singly-Linked Lists
An Implementation
List Elements
LinkedList Constructor
purge Method
Accessor Methods
getFirst and getLast Methods
prepend Method
append Method
assign Method
extract Method
insertAfter and insertBefore Methods
Exercises
Projects
Data Types and Abstraction
Abstract Data Types
Design Patterns
Class Hierarchy
Java Objects and the Comparable Interface
Abstract Comparable Objects
Wrappers for the Primitive Types
Containers
Abstract Containers
Visitors
The isDone Method
Abstract Visitors
The AbstractContainer Class toString Method
Enumerations
Searchable Containers
Abstract Searchable Containers
Associations
Exercises
Projects
Stacks, Queues, and Deques
Stacks
Array Implementation
Fields
Constructor and purge Methods
push, pop, and getTop Methods
accept Method
getEnumeration Method
Linked-List Implementation
Fields
Constructor and purge Methods
push, pop, and getTop Methods
accept Method
getEnumeration Method
Applications
Evaluating Postfix Expressions
Implementation
Queues
Array Implementation
Fields
Constructor and purge Methods
getHead, enqueue, and dequeue Methods
Linked-List Implementation
Fields
Constructor and purge Methods
getHead, enqueue, and dequeue Methods
Applications
Implementation
Deques
Array Implementation
The ``Head'' Methods
The ``Tail'' Methods
Linked List Implementation
The ``Head'' Methods
The ``Tail'' Methods
Doubly-Linked and Circular Lists
Exercises
Projects
Ordered Lists and Sorted Lists
Ordered Lists
Array Implementation
Fields
Creating a List and Inserting Items
Finding Items in a List
Removing Items from a List
Positions of Items in a List
Finding the Position of an Item and Accessing by Position
Inserting an Item at an Arbitrary Position
Removing Arbitrary Items by Position
Linked-List Implementation
Fields
Inserting and Accessing Items in a List
Finding Items in a List
Removing Items from a List
Positions of Items in a List
Finding the Position of an Item and Accessing by Position
Inserting an Item at an Arbitrary Position
Removing Arbitrary Items by Position
Performance Comparison: OrderedListAsArray vs. ListAsLinkedList
Applications
Sorted Lists
Array Implementation
Inserting Items in a Sorted List
Locating Items in an Array-Binary Search
Finding Items in a Sorted List
Removing Items from a List
Linked-List Implementation
Inserting Items in a Sorted List
Other Operations on Sorted Lists
Performance Comparison: SortedListAsArray vs. SortedListAsList
Applications
Implementation
Analysis
Exercises
Projects
Hashing, Hash Tables, and Scatter Tables
Hashing-The Basic Idea
Example
Keys and Hash Functions
Avoiding Collisions
Spreading Keys Evenly
Ease of Computation
Hashing Methods
Division Method
Middle Square Method
Multiplication Method
Fibonacci Hashing
Hash Function Implementations
Integral Keys
Floating-Point Keys
Character String Keys
Hashing Containers
Using Associations
Hash Tables
Abstract Hash Tables
Separate Chaining
Implementation
Constructor, getLength and purge Methods
Inserting and Removing Items
Finding an Item
Average Case Analysis
Scatter Tables
Chained Scatter Table
Implementation
Constructor, getLength, and purge Methods
Inserting and Finding an Item
Removing Items
Worst-Case Running Time
Average Case Analysis
Scatter Table using Open Addressing
Linear Probing
Quadratic Probing
Double Hashing
Implementation
Constructor, getLength, and purge Methods
Inserting Items
Finding Items
Removing Items
Average Case Analysis
Applications
Exercises
Projects
Trees
Basics
Terminology
More Terminology
Alternate Representations for Trees
N-ary Trees
Binary Trees
Tree Traversals
Preorder Traversal
Postorder Traversal
Inorder Traversal
Breadth-First Traversal
Expression Trees
Infix Notation
Prefix Notation
Postfix Notation
Implementing Trees
Tree Traversals
Depth-First Traversal
Preorder, Inorder, and Postorder Traversals
Breadth-First Traversal
accept Method
Tree Enumerations
Constructor
hasMoreElements and nextElement Methods
General Trees
Fields
Constructor and purge Methods
getKey and getSubtree Methods
attachSubtree and detachSubtree Methods
N-ary Trees
Fields
Constructors
isEmpty Method
getKey, attachKey, and detachKey Methods
getSubtree, attachSubtree and detachSubtree Methods
Binary Trees
Fields
Constructors
purge Method
Binary Tree Traversals
Comparing Trees
Applications
Implementation
Exercises
Projects
Search Trees
Basics
M-Way Search Trees
Binary Search Trees
Searching a Search Tree
Searching an M-way Tree
Searching a Binary Tree
Average Case Analysis
Successful Search
Solving The Recurrence-Telescoping
Unsuccessful Search
Traversing a Search Tree
Implementing Search Trees
Binary Search Trees
Fields
find Method
findMin Method
Inserting Items in a Binary Search Tree
insert and attachKey Methods
Removing Items from a Binary Search Tree
withdraw Method
AVL Search Trees
Implementing AVL Trees
Constructor
getHeight, adjustHeight, and getBalanceFactor Methods
Inserting Items into an AVL Tree
Balancing AVL Trees
Single Rotations
Double Rotations
Implementation
Removing Items from an AVL Tree
M-Way Search Trees
Implementing M-Way Search Trees
Implementation
Constructor and getM Methods
Inorder Traversal
Finding Items in an M-Way Search Tree
Linear Search
Binary Search
Inserting Items into an M-Way Search Tree
Removing Items from an M-Way Search Tree
B-Trees
Implementing B-Trees
Fields
Constructor and attachSubtree Methods
Inserting Items into a B-Tree
Implementation
Running Time Analysis
Removing Items from a B-Tree
Applications
Exercises
Projects
Heaps and Priority Queues
Basics
Binary Heaps
Complete Trees
Complete N-ary Trees
Implementation
Fields
Constructor and purge Methods
Putting Items into a Binary Heap
Removing Items from a Binary Heap
Leftist Heaps
Leftist Trees
Implementation
Fields
Merging Leftist Heaps
Putting Items into a Leftist Heap
Removing Items from a Leftist Heap
Binomial Queues
Binomial Trees
Binomial Queues
Implementation
Heap-Ordered Binomial Trees
Adding Binomial Trees
Binomial Queues
Fields
addTree and removeTree
findMinTree and findMin Methods
Merging Binomial Queues
Putting Items into a Binomial Queue
Removing an Item from a Binomial Queue
Applications
Discrete Event Simulation
Implementation
Exercises
Projects
Sets, Multisets, and Partitions
Basics
Implementing Sets
Array and Bit-Vector Sets
Basic Operations
Union, Intersection, and Difference
Comparing Sets
Bit-Vector Sets
Basic Operations
Union, Intersection, and Difference
Multisets
Array Implementation
Basic Operations
Union, Intersection, and Difference
Linked-List Implementation
Union
Intersection
Partitions
Representing Partitions
Implementing a Partition using a Forest
Implementation
Constructor
find and join Methods
Collapsing Find
Union by Size
Union by Height or Rank
Applications
Exercises
Projects
Garbage Collection and the Other Kind of Heap
What is Garbage?
Reduce, Reuse, Recycle
Reduce
Reuse
Recycle
Helping the Garbage Collector
Reference Counting Garbage Collection
When Objects Refer to Other Objects
Why Reference Counting Does Not Work
Mark-and-Sweep Garbage Collection
The Fragmentation Problem
Stop-and-Copy Garbage Collection
The Copy Algorithm
Mark-and-Compact Garbage Collection
Handles
Exercises
Projects
Algorithmic Patterns and Problem Solvers
Brute-Force and Greedy Algorithms
Example-Counting Change
Brute-Force Algorithm
Greedy Algorithm
Example-0/1 Knapsack Problem
Backtracking Algorithms
Example-Balancing Scales
Representing the Solution Space
Abstract Backtracking Solvers
Abstract Solvers
Depth-First Solver
Breadth-First Solver
Branch-and-Bound Solvers
Depth-First, Branch-and-Bound Solver
Example-0/1 Knapsack Problem Again
Top-Down Algorithms: Divide-and-Conquer
Example-Binary Search
Example-Computing Fibonacci Numbers
Example-Merge Sorting
Running Time of Divide-and-Conquer Algorithms
Case 1 ( )
Case 2 ( )
Case 3 ( )
Summary
Example-Matrix Multiplication
Bottom-Up Algorithms: Dynamic
Programming
Example-Generalized Fibonacci Numbers
Example-Computing Binomial Coefficients
Application: Typesetting Problem
Example
Implementation
Randomized Algorithms
Generating Random Numbers
The Minimal Standard Random Number Generator
Implementation
Random Variables
A Simple Random Variable
Uniformly Distributed Random Variables
Exponentially Distributed Random Variables
Monte Carlo Methods
Example-Computing
Simulated Annealing
Example-Balancing Scales
Exercises
Projects
Sorting Algorithms and Sorters
Basics
Sorting and Sorters
Abstract Sorters
Sorter Class Hierarchy
Insertion Sorting
Straight Insertion Sort
Implementation
Average Running Time
Binary Insertion Sort
Exchange Sorting
Bubble Sort
Quicksort
Implementation
Running Time Analysis
Worst-Case Running Time
Best-Case Running Time
Average Running Time
Selecting the Pivot
Selection Sorting
Straight Selection Sorting
Implementation
Sorting with a Heap
Implementation
Building the Heap
Running Time Analysis
The Sorting Phase
Merge Sorting
Implementation
Merging
Two-Way Merge Sorting
Running Time Analysis
A Lower Bound on Sorting
Distribution Sorting
Bucket Sort
Implementation
Radix Sort
Implementation
Performance Data
Exercises
Projects
Graphs and Graph Algorithms
Basics
Directed Graphs
Terminology
More Terminology
Directed Acyclic Graphs
Undirected Graphs
Terminology
Labeled Graphs
Representing Graphs
Adjacency Matrices
Sparse vs. Dense Graphs
Adjacency Lists
Implementing Graphs
Vertices
Enumerations
Edges
Graphs and Digraphs
Accessors and Mutators
Enumerations
Graph Traversals
Directed Graphs
Abstract Graphs
Implementing Undirected Graphs
Using Adjacency Matrices
Using Adjacency Lists
Comparison of Graph Representations
Space Comparison
Time Comparison
Graph Traversals
Depth-First Traversal
Implementation
Running Time Analysis
Breadth-First Traversal
Implementation
Running Time Analysis
Topological Sort
Implementation
Running Time Analysis
Graph Traversal Applications:
Testing for Cycles and Connectedness
Connectedness of an Undirected Graph
Connectedness of a Directed Graph
Testing Strong Connectedness
Testing for Cycles in a Directed Graph
Shortest-Path Algorithms
Single-Source Shortest Path
Dijkstra's Algorithm
Data Structures for Dijkstra's Algorithm
Implementation
Running Time Analysis
All-Pairs Source Shortest Path
Floyd's Algorithm
Implementation
Running Time Analysis
Minimum-Cost Spanning Trees
Constructing Spanning Trees
Minimum-Cost Spanning Trees
Prim's Algorithm
Implementation
Kruskal's Algorithm
Implementation
Running Time Analysis
Application: Critical Path Analysis
Implementation
Exercises
Projects
Java and Object-Oriented Programming
Variables
Primitive Types
References Types
Null References
Parameter Passing
Passing Primitive Types
Passing Reference Types
Objects and Classes
Class Members: Fields and Methods
Constructors
The No-Arg Constructor
Accessors and Mutators
Mutators
Member Access Control
Inner Classes
Static Inner Classes
Non-Static Inner Classes
Inheritance and Polymorphism
Derivation and Inheritance
Derivation and Access Control
Polymorphism
Interfaces
Abstract Methods and Abstract Classes
Method Resolution
Abstract Classes and Concrete Classes
Algorithmic Abstraction
Multiple Inheritance
Run-Time Type Information and Casts
Exceptions
Class Hierarchy Diagrams
Character Codes
References
Index
Download this book click here
No comments:
Post a Comment