Building Java Programs: A Back to Basics Approach (5th Edition)

Building Java Programs A Back to Basics Approach
Preface
	New to This Edition
	Features from Prior Editions
	Layers and Dependencies
	Supplements
	MyLab Programming
	VideoNotes
Location of Video Notes in the Text http://www.pearson.com/cs-resources
Brief Contents
Contents
Chapter 1 Introduction to Java Programming
	Introduction
	1.1 Basic Computing Concepts
		Why Programming?
		Hardware and Software
		The Digital Realm
		The Process of Programming
		Why Java?
		The Java Programming Environment
	1.2 And Now—Java
		String Literals (Strings)
		System.out.println
		Escape Sequences
		print versus println
		Identifiers and Keywords
		A Complex Example: DrawFigures1
		Comments and Readability
	1.3 Program Errors
		Syntax Errors
		Logic Errors (Bugs)
	1.4 Procedural Decomposition
		Static Methods
		Flow of Control
		Methods That Call Other Methods
		An Example Runtime Error
	1.5 Case Study: DrawFigures
		Structured Version
		Final Version without Redundancy
		Analysis of Flow of Execution
	Chapter Summary
	Self-Check Problems
		Section 1.1: Basic Computing Concepts
		Section 1.2: And Now—Java
		Section 1.3: Program Errors
		Section 1.4: Procedural Decomposition
	Exercises
	Programming Projects
Chapter 2 Primitive Data and Definite Loops
	Introduction
	2.1 Basic Data Concepts
		Primitive Types
		Expressions
		JShell
		Literals
		Arithmetic Operators
		Precedence
		Mixing Types and Casting
	2.2 Variables
		Assignment/Declaration Variations
		String Concatenation
		Increment/Decrement Operators
		Variables and Mixing Types
	2.3 The for Loop
		Tracing for Loops
		for Loop Patterns
		Nested for Loops
	2.4 Managing Complexity
		Scope
		Pseudocode
		The Table Technique
		Class Constants
	2.5 Case Study: Hourglass Figure
		Problem Decomposition and Pseudocode
		Initial Structured Version
		Adding a Class Constant
		Further Variations
	Chapter Summary
	Self-Check Problems
		Section 2.1: Basic Data Concepts
		Section 2.2: Variables
		Section 2.3: The for Loop
		Section 2.4: Managing Complexity
	Exercises
	Programming Projects
Chapter 3 Introduction to Parameters and Objects
	Introduction
	3.1 Parameters
		The Mechanics of Parameters
		Limitations of Parameters
		Multiple Parameters
		Parameters versus Constants
		Overloading of Methods
	3.2 Methods That Return Values
		The Math Class
		Defining Methods That Return Values
	3.3 Using Objects
		String Objects
		Interactive Programs and Scanner Objects
		Sample Interactive Program
	3.4 Case Study: Projectile Trajectory
		Unstructured Solution
		Structured Solution
	Chapter Summary
	Self-Check Problems
		Section 3.1: Parameters
		Section 3.2: Methods That Return Values
		Section 3.3: Using Objects
	Exercises
	Programming Projects
Supplement 3G Graphics (Optional)
	Introduction
	3G.1 Introduction to Graphics
		DrawingPanel
		Drawing Lines and Shapes
		Colors
		Drawing with Loops
		Text and Fonts
		Images
	3G.2 Procedural Decomposition with Graphics
		A Larger Example: DrawDiamonds
	3G.3 Case Study: Pyramids
		Unstructured Partial Solution
		Generalizing the Drawing of Pyramids
		Complete Structured Solution
	Chapter Summary
	Self-Check Problems
		Section 3G.1: Introduction to Graphics
	Exercises
	Programming Projects
Chapter 4 Conditional Execution
	Introduction
	4.1 if/else Statements
		Relational Operators
		Nested if/else Statements
		Object Equality
		Factoring if/else Statements
		Testing Multiple Conditions
	4.2 Cumulative Algorithms
		Cumulative Sum
		Min/Max Loops
		Cumulative Sum with if
		Roundoff Errors
	4.3 Text Processing
		The char Type
		char versus int
		Cumulative Text Algorithms
		System.out.printf
	4.4 Methods with Conditional Execution
		Preconditions and Postconditions
		Throwing Exceptions
		Revisiting Return Values
		Reasoning about Paths
	4.5 Case Study: Body Mass Index
		One-Person Unstructured Solution
		Two-Person Unstructured Solution
		Two-Person Structured Solution
		Procedural Design Heuristics
	Chapter Summary
	Self-Check Problems
		Section 4.1: if/else Statements
		Section 4.2: Cumulative Algorithms
		Section 4.3: Text Processing
		Section 4.4: Methods with Conditional Execution
	Exercises
	Programming Projects
Chapter 5 Program Logic and Indefinite Loops
	Introduction
	5.1 The while Loop
		A Loop to Find the Smallest Divisor
		Random Numbers
		Simulations
		do/while Loop
	5.2 Fencepost Algorithms
		Fencepost with if
		Sentinel Loops
	5.3 The boolean Type
		Logical Operators
		Short-Circuited Evaluation
		boolean Variables and Flags
		Boolean Zen
		Negating Boolean Expressions
	5.4 User Errors
		Scanner Lookahead
		Handling User Errors
	5.5 Assertions and Program Logic
		Reasoning about Assertions
		A Detailed Assertions Example
	5.6 Case Study: NumberGuess
		Initial Version without Hinting
		Randomized Version with Hinting
		Final Robust Version
	Chapter Summary
	Self-Check Problems
		Section 5.1: The while Loop
		Section 5.2: Fencepost Algorithms
		Section 5.3: The boolean Type
		Section 5.4: User Errors
		Section 5.5: Assertions and Program Logic
	Exercises
	Programming Projects
Chapter 6 File Processing
	Introduction
	6.1 File-Reading Basics
		Data, Data Everywhere
		Files and File Objects
		Reading a File with a Scanner
	6.2 Details of Token-Based Processing
		Structure of Files and Consuming Input
		Scanner Parameters
		Paths and Directories
		A More Complex Input File
	6.3 Line-Based Processing
		String Scanners and Line/Token Combinations
	6.4 Advanced File Processing
		Output Files with PrintStream
		Guaranteeing That Files Can Be Read
	6.5 Case Study: Zip Code Lookup
	Chapter Summary
	Self-Check Problems
		Section 6.1: File-Reading Basics
		Section 6.2: Details of Token-Based Processing
		Section 6.3: Line-Based Processing
		Section 6.4: Advanced File Processing
	Exercises
	Programming Projects
Chapter 7 Arrays
	Introduction
	7.1 Array Basics
		Constructing and Traversing an Array
		Accessing an Array
		Initializing Arrays
		A Complete Array Program
		Random Access
		Arrays and Methods
		The For-Each Loop
		The Arrays Class
	7.2 Array-Traversal Algorithms
		Printing an Array
		Searching and Replacing
		Testing for Equality
		Reversing an Array
		String Traversal Algorithms
		Functional Approach
	7.3 Reference Semantics
		Multiple Objects
	7.4 Advanced Array Techniques
		Shifting Values in an Array
		Arrays of Objects
		Command-Line Arguments
		Nested Loop Algorithms
	7.5 Multidimensional Arrays
		Rectangular Two-Dimensional Arrays
		Jagged Arrays
	7.6 Arrays of Pixels
	7.7 Case Study: Benford’s Law
		Tallying Values
		Completing the Program
	Chapter Summary
	Self-Check Problems
		Section 7.1: Array Basics
		Section 7.2: Array-Traversal Algorithms
		Section 7.3: Reference Semantics
		Section 7.4: Advanced Array Techniques
		Section 7.5: Multidimensional Arrays
	Exercises
	Programming Projects
Chapter 8 Classes
	Introduction
	8.1 Object-Oriented Programming
		Classes and Objects
		Point Objects
	8.2 Object State and Behavior
		Object State: Fields
		Object Behavior: Methods
		The Implicit Parameter
		Mutators and Accessors
		The toString Method
	8.3 Object Initialization: Constructors
		The Keyword this
		Multiple Constructors
	8.4 Encapsulation
		Private Fields
		Class Invariants
		Changing Internal Implementations
	8.5 Case Study: Designing a Stock Class
		Object-Oriented Design Heuristics
		Stock Fields and Method Headers
		Stock Method and Constructor Implementation
	Chapter Summary
	Self-Check Problems
		Section 8.1: Object-Oriented Programming
		Section 8.2: Object State and Behavior
		Section 8.3: Object Initialization: Constructors
		Section 8.4: Encapsulation
		Section 8.5: Case Study: Designing a Stock Class
	Exercises
	Programming Projects
Chapter 9 Inheritance and Interfaces
	Introduction
	9.1 Inheritance Basics
		Nonprogramming Hierarchies
		Extending a Class
		Overriding Methods
	9.2 Interacting with the Superclass
		Calling Overridden Methods
		Accessing Inherited Fields
		Calling a Superclass’s Constructor
		DividendStock Behavior
		The Object Class
		The equals Method
		The instanceof Keyword
	9.3 Polymorphism
		Polymorphism Mechanics
		Interpreting Inheritance Code
		Interpreting Complex Calls
	9.4 Inheritance and Design
		A Misuse of Inheritance
		Is-a Versus Has-a Relationships
		Graphics2D
	9.5 Interfaces
		An Interface for Shapes
		Implementing an Interface
		Benefits of Interfaces
	9.6 Case Study: Financial Class Hierarchy
		Designing the Classes
		Redundant Implementation
		Abstract Classes
	Chapter Summary
	Self-Check Problems
		Section 9.1: Inheritance Basics
		Section 9.2: Interacting with the Superclass
		Section 9.3: Polymorphism
		Section 9.4: Inheritance and Design
		Section 9.5: Interfaces
		Section 9.6: Case Study: Financial Class Hierarchy
	Exercises
	Programming Projects
Chapter 10 ArrayLists
	Introduction
	10.1 ArrayLists
		Basic ArrayList Operations
		ArrayList Searching Methods
		A Complete ArrayList Program
		Adding to and Removing from an ArrayList
		Initializing an ArrayList
		Using the For-Each Loop with ArrayLists
		Wrapper Classes
	10.2 The Comparable Interface
		Natural Ordering and compareTo
		Implementing the Comparable Interface
	10.3 Case Study: Ranked Choice Voting
		Ballot Class
		Counting Votes
		Multiple Rounds
	Chapter Summary
	Self-Check Problems
		Section 10.1: ArrayLists
		Section 10.2: The Comparable Interface
	Exercises
	Programming Projects
Chapter 11 Java Collections Framework
	Introduction
	11.1 Lists
		Collections
		LinkedList versus ArrayList
		Iterators
		Abstract Data Types (ADTs)
		LinkedList Case Study: Sieve
	11.2 Sets
		Set Concepts
		TreeSet versus HashSet
		Set Operations
		Set Case Study: Lottery
	11.3 Maps
		Basic Map Operations
		Map Views (keySet and values)
		TreeMap versus HashMap
		Map Case Study: WordCount
		Collection Overview
	Chapter Summary
	Self-Check Problems
		Section 11.1: Lists
		Section 11.2: Sets
		Section 11.3: Maps
	Exercises
	Programming Projects
Chapter 12 Recursion
	Introduction
	12.1 Thinking Recursively
		A Nonprogramming Example
		An Iterative Solution Converted to Recursion
		Structure of Recursive Solutions
	12.2 A Better Example of Recursion
		Mechanics of Recursion
	12.3 Recursive Functions and Data
		Integer Exponentiation
		Greatest Common Divisor
		Directory Crawler
		Helper Methods
	12.4 Recursive Graphics
	12.5 Recursive Backtracking
		A Simple Example: Traveling North/East
		8 Queens Puzzle
		Solving Sudoku Puzzles
	12.6 Case Study: Prefix Evaluator
		Infix, Prefix, and Postfix Notation
		Evaluating Prefix Expressions
		Complete Program
	Chapter Summary
	Self-Check Problems
		Section 12.1: Thinking Recursively
		Section 12.2: A Better Example of Recursion
		Section 12.3: Recursive Functions and Data
		Section 12.4: Recursive Graphics
		Section 12.5: Recursive Backtracking
	Exercises
	Programming Projects
Chapter 13 Searching and Sorting
	Introduction
	13.1 Searching and Sorting in the Java Class Libraries
		Binary Search
		Sorting
		Shuffling
		Custom Ordering with Comparators
	13.2 Program Complexity
		Empirical Analysis
		Complexity Classes
	13.3 Implementing Searching and Sorting Algorithms
		Sequential Search
		Binary Search
		Recursive Binary Search
		Searching Objects
		Selection Sort
	13.4 Case Study: Implementing Merge Sort
		Splitting and Merging Arrays
		Recursive Merge Sort
		Complete Program
	Chapter Summary
	Self-Check Problems
		Section 13.1: Searching and Sorting in the Java Class Libraries
		Section 13.2: Program Complexity
		Section 13.3: Implementing Searching and Sorting Algorithms
		Section 13.4: Case Study: Implementing Merge Sort
	Exercises
	Programming Projects
Chapter 14 Stacks and Queues
	Introduction
	14.1 Stack/Queue Basics
		Stack Concepts
		Queue Concepts
	14.2 Common Stack/Queue Operations
		Transferring between Stacks and Queues
		Sum of a Queue
		Sum of a Stack
	14.3 Complex Stack/Queue Operations
		Removing Values from a Queue
		Comparing Two Stacks for Similarity
	14.4 Case Study: Expression Evaluator
		Splitting into Tokens
		The Evaluator
	Chapter Summary
	Self-Check Problems
		Section 14.1: Stack/Queue Basics
		Section 14.2: Common Stack/Queue Operations
		Section 14.3: Complex Stack/Queue Operations
	Exercises
	Programming Projects
Chapter 15 Implementing a Collection Class
	Introduction
	15.1 Simple ArrayIntList
		Adding and Printing
		Thinking about Encapsulation
		Dealing with the Middle of the List
		Another Constructor and a Constant
		Preconditions and Postconditions
	15.2 A More Complete ArrayIntList
		Throwing Exceptions
		Convenience Methods
	15.3 Advanced Features
		Resizing When Necessary
		Adding an Iterator
	15.4 ArrayList
	Chapter Summary
	Self-Check Problems
		Section 15.1: Simple ArrayIntList
		Section 15.2: A More Complete ArrayIntList
		Section 15.3: Advanced Features
		Section 15.4: ArrayList
	Exercises
	Programming Projects
Chapter 16 Linked Lists
	Introduction
	16.1 Working with Nodes
		Constructing a List
		List Basics
		Manipulating Nodes
		Traversing a List
	16.2 A Linked List Class
		Simple LinkedIntList
		Appending add
		The Middle of the List
	16.3 A Complex List Operation
		Inchworm Approach
	16.4 An IntList Interface
	16.5 LinkedList
		Linked List Variations
		Linked List Iterators
		Other Code Details
	Chapter Summary
	Self-Check Problems
		Section 16.1: Working with Nodes
		Section 16.2: A Linked List Class
		Section 16.3: A Complex List Operation
		Section 16.4: An IntList Interface
		Section 16.5: LinkedList
	Exercises
	Programming Projects
Chapter 17 Binary Trees
	Introduction
	17.1 Binary Tree Basics
		Node and Tree Classes
	17.2 Tree Traversals
		Constructing and Viewing a Tree
	17.3 Common Tree Operations
		Sum of a Tree
		Counting Levels
		Counting Leaves
	17.4 Binary Search Trees
		The Binary Search Tree Property
		Building a Binary Search Tree
		The Pattern x = change(x)
		Searching the Tree
		Binary Search Tree Complexity
	17.5 SearchTree
	Chapter Summary
	Self-Check Problems
		Section 17.1: Binary Tree Basics
		Section 17.2: Tree Traversals
		Section 17.3: Common Tree Operations
		Section 17.4: Binary Search Trees
		Section 17.5: SearchTree
	Exercises
	Programming Projects
Chapter 18 Advanced Data Structures
	Introduction
	18.1 Hashing
		Array Set Implementations
		Hash Functions and Hash Tables
		Collisions
		Rehashing
		Hashing Non-Integer Data
		Hash Map Implementation
	18.2 Priority Queues and Heaps
		Priority Queues
		Introduction to Heaps
		Removing from a Heap
		Adding to a Heap
		Array Heap Implementation
		Heap Sort
	Chapter Summary
	Self-Check Problems
		Section 18.1: Hashing
		Section 18.2: Priority Queues and Heaps
	Exercises
	Programming Projects
Chapter 19 Functional Programming with Java 8
	Introduction
	19.1 Effect-Free Programming
	19.2 First-Class Functions
		Lambda Expressions
	19.3 Streams
		Basic Idea
		Using Map
		Using Filter
		Using Reduce
		Optional Results
	19.4 Function Closures
	19.5 Higher-Order Operations on Collections
		Working with Arrays
		Working with Lists
		Working with Files
	19.6 Case Study: Perfect Numbers
		Computing Sums
		Incorporating Square Root
		Just Five and Leveraging Concurrency
	Chapter Summary
	Self-Check Problems
		19.1 Effect-Free Programming
		19.2 First-Class Functions
		19.3 Streams
		19.4 Function Closures
		19.5 Higher-Order Operations on Collections
	Exercises
	Programming Projects
Appendix A Java Summary
	Java Keywords
	Primitive Types
	Arithmetic Operators
	Relational Operators
	Logical Operators
	Operator Precedence
	Wrapper Classes
	Syntax Templates
	Useful Methods of ArrayList Objects
	Useful Methods of the Character Class
	Useful Methods of the Collection Interface
	Useful Methods of the Collections Class
	Useful Methods of DrawingPanel Objects
	Useful Methods of File Objects
	Useful Methods of Graphics Objects
	Useful Methods of Iterator Objects
	Useful Methods of Map Objects
	Constants and Useful Methods of the Math Class
	Useful Methods of the Object Class
	Useful Methods of Point Objects
	Useful Methods of Random Objects
	Useful Methods of Scanner Objects
	Useful Methods of String Objects
Appendix B The Java API Specification and Javadoc Comments
	The Java API Specification
		Parameters
		Returns
		Throws
		Deprecated
	Writing Javadoc Comments
Appendix C Additional Java Syntax
	Primitive Types: byte, short, long, float
	Ternary Operator ? :
	Exiting a Loop: break and continue
	The switch Statement
	The try/catch Statement
	The assert Statement
	Enumerations: enum
	Packages
	Protected and Default Access
Index
	A
	B
	C
	D
	E
	F
	G
	H
	I
	J
	K
	L
	M
	N
	O
	P
	Q
	R
	S
	T
	U
	V
	W
	Y
	Z