Lessons 1: Introduction
- Organising Data
Lessons 2: Prelude: Designing Classes
- Encapsulation
- Specifying Methods
- Java Interfaces
- Choosing Classes
- Reusing Classes
- Exercises
- Projects
Lessons 3: Bags
- The Bag
- Specifying a Bag
- Using the ADT Bag
- Using an ADT Is Like Using a Vending Machine
- The ADT Set
- Java Class Library: The Interface Set
- Java Interlude 1: Generics
- Lesson Summary
- Programming Tip
- Exercises
- Projects
Lessons 4: Bag Implementations That Use Arrays
- Using a Fixed-Size Array to Implement the ADT Bag
- Using Array Resizing to Implement the ADT Bag
- The Pros and Cons of Using an Array to Implement the ADT Bag
- Java Interlude 2 Exceptions
- Lesson Summary
- Programming Tips
- Exercises
- Projects
Lessons 5: A Bag Implementation That Links Data
- Linked Data
- A Linked Implementation of the ADT Bag
- Removing an Item from a Linked Chain
- A Class Node That Has Set and Get Methods
- The Pros and Cons of Using a Chain to Implement the ADT Bag
- Lesson Summary
- Programming Tip
- Exercises
- Projects
Lessons 6: The Efficiency of Algorithms
- Motivation
- Measuring an Algorithm’s Efficiency
- Big Oh Notation
- Picturing Efficiency
- The Efficiency of Implementations of the ADT Bag
- Lesson Summary
- Exercises
- Projects
Lessons 7: Stacks
- Specifications of the ADT Stack
- Using a Stack to Process Algebraic Expressions
- The Program Stack
- Java Class Library: The Class Stack
- Lesson Summary
- Programming Tip
- Exercises
- Projects
Lessons 8: Stack Implementations
- A Linked Implementation
- An Array-Based Implementation
- A Vector-Based Implementation
- Java Interlude 3: More About Exceptions
- Lesson Summary
- Exercises
- Projects
Lessons 9: Queues, Deques and Priority Queues
- The ADT Queue
- The ADT Deque
- The ADT Priority Queue
- Lesson Summary
- Programming Tip
- Exercises
- Projects
Lessons 10: Queue, Deque and Priority Queue Implementations
- A Linked Implementation of a Queue
- An Array-Based Implementation of a Queue
- Circular Linked Implementations of a Queue
- Java Class Library: The Class AbstractQueue
- A Doubly Linked Implementation of a Deque
- Possible Implementations of a Priority Queue
- Lesson Summary
- Programming Tip
- Exercises
- Projects
Lessons 11: Recursion
- What Is Recursion?
- Tracing a Recursive Method
- Recursive Methods That Return a Value
- Recursively Processing an Array
- Recursively Processing a Linked Chain
- The Time Efficiency of Recursive Methods
- Tail Recursion
- Using a Stack Instead of Recursion
- Lesson Summary
- Programming Tips
- Exercises
- Projects
Lessons 12: Lists
- Specifications for the ADT List
- Using the ADT List
- Java Class Library: The Interface List
- Java Class Library: The Class ArrayList
- Lesson Summary
- Exercises
- Projects
Lessons 13: A List Implementation That Uses an Array
- Using an Array to Implement the ADT List
- The Efficiency of Using an Array to Implement the ADT List
- Lesson Summary
- Exercises
- Projects
Lessons 14: A List Implementation That Links Data
- Operations on a Chain of Linked Nodes
- Beginning the Implementation
- Continuing the Implementation
- A Refined Implementation
- The Efficiency of Using a Chain to Implement the ADT List
- Java Class Library: The Class LinkedList
- Java Interlude 4: Iterators
- Lesson Summary
- Exercises
- Projects
Lessons 15: Iterators for the ADT List
- Ways to Implement an Iterator
- A Separate Class Iterator
- An Inner Class Iterator
- Why Are Iterator Methods in Their Own Class?
- An Array-Based Implementation of the Interface ListIterator
- Lesson Summary
- Programming Tip
- Exercises
- Projects
Lessons 16: Problem Solving with Recursion
- A Simple Solution to a Difficult Problem
- A Poor Solution to a Simple Problem
- Languages and Grammars
- Indirect Recursion
- Backtracking
- Java Interlude 5: More About Generics
- Lesson Summary
- Exercises
- Projects
Lessons 17: An Introduction to Sorting
- Organising Java Methods That Sort an Array
- Selection Sort
- Insertion Sort
- Shell Sort
- Comparing the Algorithms
- Lesson Summary
- Programming Tip
- Exercises
- Projects
Lessons 18: Faster Sorting Methods
- Merge Sort
- Quick Sort
- Radix Sort
- Comparing the Algorithms
- Java Interlude 6: Mutable and Immutable Objects
- Lesson Summary
- Exercises
- Projects
Lessons 19: Sorted Lists
- Specifications for the ADT Sorted List
- A Linked Implementation
- An Implementation That Uses the ADT List
- Java Interlude 7: Inheritance and Polymorphism
- Lesson Summary
- Exercises
- Projects
Lessons 20: Inheritance and Lists
- Using Inheritance to Implement a Sorted List
- Designing a Base Class
- An Efficient Implementation of a Sorted List
- Lesson Summary
- Programming Tips
- Exercises
- Projects
Lessons 21: Searching
- The Problem
- Searching an Unsorted Array
- Searching a Sorted Array
- Searching an Unsorted Chain
- Searching a Sorted Chain
- Choosing a Search Method
- Java Interlude 8: Generics Once Again
- Lesson Summary
- Programming Tip
- Exercises
- Projects
Lessons 22: Dictionaries
- Specifications for the ADT Dictionary
- Using the ADT Dictionary
- Java Class Library: The Interface Map
- Lesson Summary
- Programming Tips
- Exercises
- Projects
Lessons 23: Dictionary Implementations
- Array-Based Implementations
- Linked Implementations
- Lesson Summary
- Programming Tips
- Exercises
- Projects
Lessons 24: Introducing Hashing
- What Is Hashing?
- Hash Functions
- Resolving Collisions
- Lesson Summary
- Exercises
- Projects
Lessons 25: Hashing as a Dictionary Implementation
- The Efficiency of Hashing
- Rehashing
- Comparing Schemes for Collision Resolution
- A Dictionary Implementation That Uses Hashing
- Java Class Library: The Class HashMap
- Java Class Library: The Class HashSet
- Lesson Summary
- Exercises
- Projects
Lessons 26: Trees
- Tree Concepts
- Traversals of a Tree
- Java Interfaces for Trees
- Examples of Binary Trees
- Examples of General Trees
- Lesson Summary
- Exercises
- Projects
Lessons 27: Tree Implementations
- The Nodes in a Binary Tree
- An Implementation of the ADT Binary Tree
- An Implementation of an Expression Tree
- General Trees
- Using a Binary Tree to Represent a General Tree
- Java Interlude 9: Cloning
- Lesson Summary
- Programming Tips
- Exercises
- Projects
Lessons 28: A Binary Search Tree Implementation
- Getting Started
- Searching and Retrieving
- Traversing
- Adding an Entry
- Removing an Entry
- The Efficiency of Operations
- An Implementation of the ADT Dictionary
- Lesson Summary
- Exercises
- Projects
Lessons 29: A Heap Implementation
- Reprise: The ADT Heap
- Using an Array to Represent a Heap
- Adding an Entry
- Removing the Root
- Creating a Heap
- Heap Sort
- Lesson Summary
- Exercises
- Projects
Lessons 30: Balanced Search Trees
- AVL Trees
- 2-3 Trees
- 2-4 Trees
- Red-Black Trees
- B-Trees
- Lesson Summary
- Exercises
- Projects
Lessons 31: Graphs
- Some Examples and Terminology
- Traversals
- Topological Order
- Paths
- Java Interfaces for the ADT Graph
- Lesson Summary
- Exercises
- Projects
Lessons 32: Graph Implementations
- An Overview of Two Implementations
- Vertices and Edges
- An Implementation of the ADT Graph
- Lesson Summary
- Exercises
- Projects
Appendix A: Documentation and Programming Style
- Naming Variables and Classes
- Indenting
- Comments
Appendix B: Java Classes
- Objects and Classes
- Using the Methods in a Java Class
- Defining a Java Class
- Enumeration as a Class
- Packages
Appendix C: Creating Classes from Other Classes
- Composition
- Inheritance
- Type Compatibility and Superclasses
Lessons 36: Supplement 1: Java Basics
- Introduction
- Elements of Java
- Simple Input and Output Using the Keyboard and Screen
- The if-else Statement
- The switch Statement
- Enumerations
- Scope
- Loops
- The Class String
- The Class StringBuilder
- Using Scanner to Extract Pieces of a String
- Arrays
- Wrapper Classes
Lessons 37: Supplement 2: File Input and Output
- Preliminaries
- Text Files
- Binary Files
Standard: