| |
| |
| |
| Tour Of Java | |
| |
| |
| |
| Primitive Java | |
| |
| |
| The General Environment | |
| |
| |
| The First Program | |
| |
| |
| Primitive Types | |
| |
| |
| Basic Operators | |
| |
| |
| Conditional Statements | |
| |
| |
| Methods | |
| |
| |
| |
| Reference Types | |
| |
| |
| What Is a Reference | |
| |
| |
| Basics of Objects and References | |
| |
| |
| Strings | |
| |
| |
| Arrays | |
| |
| |
| Exception Handling | |
| |
| |
| Input and Output | |
| |
| |
| |
| Objects and Classes | |
| |
| |
| What Is Object-oriented Programming? | |
| |
| |
| A Simple Example | |
| |
| |
| Javadoc | |
| |
| |
| Basic Methods | |
| |
| |
| Additional Constructs | |
| |
| |
| Packages | |
| |
| |
| A Design Pattern: Composite (Pair) | |
| |
| |
| |
| Inheritance | |
| |
| |
| What Is Inheritance? | |
| |
| |
| Designing Hierarchies | |
| |
| |
| Multiple Inheritance | |
| |
| |
| The Interface | |
| |
| |
| Fundamental Inheritance in Java | |
| |
| |
| Implementing Generic Components | |
| |
| |
| The Functor (Function Objects) | |
| |
| |
| Dynamic Binding Details | |
| |
| |
| |
| Algorithms And Building Blocks | |
| |
| |
| |
| Algorithm Analysis | |
| |
| |
| What Is Algorithm Analysis? | |
| |
| |
| Examples of Algorithm Running Times | |
| |
| |
| The Maximum Contiguous Subsequence Sum Problem | |
| |
| |
| General Big-Oh Rules | |
| |
| |
| The Logarithm | |
| |
| |
| Static Searching Problem | |
| |
| |
| Checking an Algorithm Analysis | |
| |
| |
| Limitations of Big-Oh Analysis | |
| |
| |
| |
| The Collections API | |
| |
| |
| Introduction | |
| |
| |
| The Iterator Pattern | |
| |
| |
| Collections API: Containers and Iterators | |
| |
| |
| Generic Algorithms | |
| |
| |
| The List Interface | |
| |
| |
| Stacks and Queues | |
| |
| |
| Sets | |
| |
| |
| Maps | |
| |
| |
| Priority Queues | |
| |
| |
| |
| Recursion | |
| |
| |
| What Is Recursion? | |
| |
| |
| Background: Proofs by Mathematical Induction | |
| |
| |
| Basic Recursion | |
| |
| |
| Numerical Applications | |
| |
| |
| Divide-and-Conquer Algorithms | |
| |
| |
| Dynamic Programming | |
| |
| |
| Backtracking Algorithms | |
| |
| |
| |
| Sorting Algorithms | |
| |
| |
| Why Is Sorting Important? | |
| |
| |
| Preliminaries | |
| |
| |
| Analysis of the Insertion Sort and Other Simple Sorts | |
| |
| |
| Shellsort | |
| |
| |
| Mergesort | |
| |
| |
| Quicksort | |
| |
| |
| Quickselect | |
| |
| |
| A Lower Bound for Sorting | |
| |
| |
| |
| Randomization | |
| |
| |
| Why Do We Need Random Numbers? | |
| |
| |
| Random-number Generators | |
| |
| |
| Nonuniform Random Numbers | |
| |
| |
| Generating a Random Permutation | |
| |
| |
| Randomized Algorithms | |
| |
| |
| Randomized Primality Testing | |
| |
| |
| |
| Applications | |
| |
| |
| |
| Fun and Games | |
| |
| |
| Word Search Puzzles | |
| |
| |
| The Game of Tic-Tac-Toe | |
| |
| |
| |
| Stacks and Compilers | |
| |
| |
| Balanced-Symbol Checker | |
| |
| |
| A Simple Calculator | |
| |
| |
| |
| Utilities | |
| |
| |
| File Compression | |
| |
| |
| A Cross-reference Generator | |
| |
| |
| |
| Simulation | |
| |
| |
| The Josephus Problem | |
| |
| |
| Event-driven Simulation | |
| |
| |
| |
| Graphs and Paths | |
| |
| |
| Definitions | |
| |
| |
| Unweighted Shortest-path Problem | |
| |
| |
| Positive-weighted, Shortest-path Problem | |
| |
| |
| Negative-weighted, Shortest-path Problem | |
| |
| |
| Path Problems in Acyclic Graphs | |
| |
| |
| |
| Implementations | |
| |
| |
| |
| Inner Classes and ArrayList Implementation | |
| |
| |
| Iterators and Nested Classes | |
| |
| |
| Iterators and Inner Classes | |
| |
| |
| The AbstractCollection Class | |
| |
| |
| Implementation of ArrayList with an Iterator | |
| |
| |
| |
| Stacks and Queues | |
| |
| |
| Dynamic Array Implementations | |
| |
| |
| Linked-list Implementations | |
| |
| |
| Comparison of the Two Methods | |
| |
| |
| The java.util.Stack Class | |
| |
| |
| Double-Ended Queues | |
| |
| |
| |
| Linked Lists | |
| |
| |
| Basic Ideas | |
| |
| |
| Java Implementation | |
| |
| |
| Doubly Linked Lists and Circular Linked Lists | |
| |
| |
| Sorted Linked Lists | |
| |
| |
| Implementing the Collections API LinkedList Class | |
| |
| |
| |
| Trees | |
| |
| |
| General Trees | |
| |
| |
| Binary Trees | |
| |
| |
| Recursion and Trees | |
| |
| |
| Tree Traversal: Iterator Classes | |
| |
| |
| |
| Binary Search Trees | |
| |
| |
| Basic Ideas | |
| |
| |
| Order Statistics | |
| |
| |
| Analysis of Binary Search Tree Operations | |
| |
| |
| AVL Trees | |
| |
| |
| Red-Black Trees | |
| |
| |
| AA-Trees | |
| |
| |
| Implementing the Collections API TreeSet and TreeMap Classes | |
| |
| |
| B-Trees | |
| |
| |
| |
| Hash Tables | |
| |
| |
| Basic Ideas | |
| |
| |
| Hash Function | |
| |
| |
| Linear Probing | |
| |
| |
| Quadratic Probing | |
| |
| |
| Separate Chaining Hashing | |
| |
| |
| Hash Tables Versus Binary Search Trees | |
| |
| |
| Hashing Applications | |
| |
| |
| |
| A Priority Queue: The Binary Heap | |
| |
| |
| Basic Ideas | |
| |
| |
| Implementation of the Basic Operations | |
| |
| |
| The buildHeap Operation: Linear-Time Heap Construction | |
| |
| |
| Advanced Operations: decreaseKey and merge | |
| |
| |
| Internal Sorting: Heapsort | |
| |
| |
| External Sorting | |
| |
| |
| |
| Advanced Data Structures | |
| |
| |
| |
| Splay Trees | |
| |
| |
| Self-Adjustment and Amortized Analysis | |
| |
| |
| The Basic Bottom-Up Splay Tree | |
| |
| |
| Basic Splay Tree Operations | |
| |
| |
| Analysis of Bottom-Up Splaying | |
| |
| |
| Top-Down Splay Trees | |
| |
| |
| Implementation of Top-Down Splay Trees | |
| |
| |
| Comparison of the Splay Tree with Other Search Trees | |
| |
| |
| |
| Merging Priority Queues | |
| |
| |
| The Skew Heap | |
| |
| |
| The Pairing Heap | |
| |
| |
| |
| The Disjoint Set Class | |
| |
| |
| Equivalence Relations | |
| |
| |
| Dynamic Equivalence and Two Applications | |
| |
| |
| The Quick-Find Algorithm | |
| |
| |
| The Quick-Union Algorithm | |
| |
| |
| Java Implementation | |
| |
| |
| Worst Case for Union-by-Rank and Path Compression | |
| |
| |
| Appendices | |
| |
| |
| |
| Operators | |
| |
| |
| |
| Graphical User Interfaces | |