Chapter 0 Introduction to Software Design¶
- 0.1. Objects, Classes, and Micro-Worlds
- 0.1.1. Installing BlueJ
- 0.1.2. Introducing LightBot
- 0.1.3. From LightBot to Micro Worlds
- 0.1.4. A Bit More LightBot
- 0.1.5. Textually Representing Programs
- 0.1.6. What Does LightBot Say About Programming?
- 0.1.7. A Programmable LightBot in Java
- 0.1.8. Creating New Objects
- 0.1.9. Calling Methods on an Object
- 0.1.10. Putting it All Together
- 0.1.11. We All Make Mistakes: Errors Happen
- 0.1.12. A Word on Making Code Easy to Read
- 0.1.13. Comparing Visual and Textual Programming
- 0.1.14. The Jeroos of Santong Island
- 0.1.15. Building Your Skills Through Practice
- 0.1.16. Programming Practice 1
- 0.2. Object-Oriented Inheritance, Overriding, and Interfaces
- 0.2.1. Inheritance Hierarchies & The Object Base Class
- 0.2.2. IS-A vs. HAS-A: Inheritance vs. Composition
- 0.2.3. Method Overriding and the @Override Annotation
- 0.2.4. Polymorphism & Dynamic Method Dispatch
- 0.2.5. Polymorphic Reference Assignments
- 0.2.6. Defining and Implementing Java Interfaces
- 0.2.7. Designing Extensible Game Frameworks
- 0.2.8. Programming Practice 7
- 0.3. Methods, Selection, and Repeating Actions
- 0.3.1. Creating Smarter Jeroos (Subclassing Basics)
- 0.3.2. Summarizing: What is Inheritance?
- 0.3.3. Creating and Using Jeroo Methods
- 0.3.4. Selection
- 0.3.5. Conditions Using Sensor Methods
- 0.3.6. An Overview of Conditional Statements
- 0.3.7. Java’s Syntax for the If-Then-Else Structure
- 0.3.8. Creating Optional Statements With If-then
- 0.3.9. Java’s Syntax for the If-then Structure
- 0.3.10. Java’s Syntax for the Multi-way Selection Structure (a cascaded if)
- 0.3.11. Your Opinions on Course Grading Policies
- 0.3.12. Repeating Actions
- 0.3.13. Generic Repetition Structures
- 0.3.14. Java’s Syntax for the While Loop
- 0.3.15. A First Taste of Testing: Verifying Jeroo Behavior
- 0.3.16. Building Your Skills Through Practice
- 0.3.17. Programming Practice 2
- 0.4. Software Testing Fundamentals & TDD
- 0.5. Variables, Fields, and Parameters
- 0.5.1. Variables
- 0.5.2. Fields Versus Local Variables
- 0.5.3. Changing Private Variables: Mutator Methods
- 0.5.4. Accessor Methods
- 0.5.5. Syntax Practice 5a: Fields and Accessors
- 0.5.6. The Return Keyword
- 0.5.7. Syntax Practice 5b: Mutators and Return Statements
- 0.5.8. Using Fields in Testing
- 0.5.9. Programming Practice 5a
- 0.5.10. Programming Practice 5b
- 0.6. Pictures and For-each Loops
- 0.7. Aggregation, Strings and More Loops
- 0.7.1. Object-Oriented Design: Aggregation, Composition, and Delegation
- 0.7.2. Strings and Characters
- 0.7.3. Counter-controlled Loops
- 0.7.4. Tips on Random Numbers
- 0.7.5. Method Overriding
- 0.7.6. Syntax Practice 7a: For Loops and OO Design
- 0.7.7. Syntax Practice 7b: toString and Returning Values
- 0.7.8. Programming Practice 7a
- 0.7.9. Programming Practice 7b
- 0.8. Grouping Objects Using Lists and Nested For Loops
- 0.8.1. Collections of Objects
- 0.8.2. Interfaces
- 0.8.3. Syntax Practice 8a: Strings
- 0.8.4. The List Interface
- 0.8.5. Generics
- 0.8.6. ArrayList
- 0.8.7. Syntax Practice 8b: Lists
- 0.8.8. Nested For Loops
- 0.8.9. Syntax Practice 8c: Nested Loops
- 0.8.10. Programming Practice 8a
- 0.8.11. Programming Practice 8b
- 0.9. Lists, Loop Idioms, Generics, and the Null Keyword
- 0.9.1. Modelling the Contents of a Library
- 0.9.2. Looping Idioms
- 0.9.3. Syntax Practice 9a: Loop Idioms
- 0.9.4. Generics Revisited
- 0.9.5. Syntax Practice 9b: Generics
- 0.9.6. The Null Keyword
- 0.9.7. Diagnosing a Null Pointer Exception
- 0.9.8. Using BlueJ’s Debugger
- 0.9.9. Using BlueJ’s Code Pad
- 0.9.10. Programming Practice 9a: Loop Idioms
- 0.9.11. Programming Practice 9b: Loops and Generics
- 0.10. Fixed-Size 1D Arrays and Array Idioms
- 0.10.1. Introduction to Fixed-Size 1D Arrays
- 0.10.2. Array Bounds, Indexing, and Default Values
- 0.10.3. Arrays Compared to Lists (ArrayList)
- 0.10.4. Initializing, Printing, and Naming Arrays
- 0.10.5. Array Reference Semantics, Aliasing, and Copying
- 0.10.6. Iterating Over Arrays: Numeric For vs. For-Each Loops
- 0.10.7. Array Index Arithmetic: Circular Wrap-Around & The Modulo Operator
- 0.10.8. Accumulator Idioms: Summing, Averaging, and Counting
- 0.10.9. Frequency Histograms & Array Buckets
- 0.10.10. Linear Search: Finding Values and Indices
- 0.10.11. Extrema Algorithms: Maximum, Minimum & Deterministic Tie-Breaking
- 0.10.12. Writing Test Assertions for Arrays in JUnit
- 0.10.13. Applying Arrays in a Problem
- 0.10.14. Programming Practice 9
- 0.11. Multi-Dimensional Arrays and Matrix Algorithms
- 0.11.1. Introduction to 2D Arrays & Matrices
- 0.11.2. Row-Column Indexing & Array-of-Arrays Model
- 0.11.3. Traversing 2D Grids: Row-Major vs. Column-Major
- 0.11.4. Matrix Algorithms: Searching & Checking Rows
- 0.11.5. Row Shifting & Grid Transformations
- 0.11.6. Coordinate Mapping & Offset Arithmetic
- 0.11.7. Testing 2D Matrix Classes in JUnit
- 0.11.8. Programming Practice 10
- 0.12. Variable Scoping, File Input/Output, and Streams
- 0.12.1. Comprehensive Scope: Blocks, Methods, Fields
- 0.12.2. Your Opinions on Course Grading Policies
- 0.12.3. Reading Text Files with Scanner and File
- 0.12.4. Writing Files with PrintWriter
- 0.12.5. Resource Management & Stream Closing
- 0.12.6. 2D Coordinate Geometry & Spatial Transformations
- 0.12.7. Euclidean Distance & Radial Modulation Formulas
- 0.12.8. Testing File I/O and Spatial Algorithms with TestCase
- 0.12.9. Programming Practice 13
- 0.13. Maps, Sets, and Associative Data Modeling
- 0.13.1. Introduction to Maps: Key-Value Associations
- 0.13.2. Core Map Operations: Storage, Retrieval, and Inspection
- 0.13.3. Sets and Uniqueness: Set & HashSet
- 0.13.4. Eliminating if-else Chains with Map Lookups
- 0.13.5. Modeling Spatial Worlds: Interconnected Locations and Pathway Maps
- 0.13.6. Case-Insensitive String Keys & Normalization
- 0.13.7. Testing Map-Driven Systems with TestCase
- 0.13.8. Programming Practice 12
- 0.14. Static Members, Main Method, and Exception Handling
- 0.14.1. Static Fields: Class-Wide State
- 0.14.2. Static Methods & The Math Class
- 0.14.3. The Standard Application Entry: main
- 0.14.4. The Exception Hierarchy: Checked vs. Unchecked
- 0.14.5. Handling Exceptions with try-catch-finally
- 0.14.6. Throwing Exceptions for Invalid Arguments
- 0.14.7. Systematic Debugging & Defect Isolation with TestCase
- 0.14.8. Programming Practice 14
Chapter 1 Command Line and Git¶
- 1.1. Command Line
- 1.2. Exercises
- 1.3. Git
- 1.4. Exercises
- 1.4.1. git clone
- 1.4.2. git status
- 1.4.3. git add
- 1.4.4. git rm
- 1.4.5. git commit
- 1.4.6. git push
- 1.4.7. git restore
- 1.4.8. git restore –staged
- 1.4.9. git pull
- 1.4.10. git commit -a
- 1.4.11. git commit (path)
- 1.4.12. git branch
- 1.4.13. git switch
- 1.4.14. git switch -c
- 1.4.15. git switch diverged branches
- 1.4.16. Challenge 1
- 1.4.17. Challenge 2
- 1.4.18. Challenge 3
Chapter 2 Introduction for Data Structures and Algorithms Courses¶
Chapter 3 Object-Oriented Programming¶
Chapter 4 Programming Tutorials¶
- 4.1. Command Line Basics
- 4.2. Parsing Command Line Parameters In Your Program
- 4.3. Using Command Line Parameters in Eclipse
- 4.4. Installing the Web-CAT Submission Plug-in for Eclipse
- 4.5. Common Debugging Methods
- 4.6. Debugging In Eclipse
- 4.7. Using the Java Scanner Class
- 4.8. Random Access Files In Java
- 4.9. JUnit Testing And You
- 4.10. Writing JUnit Tests
- 4.11. Code Coverage In JUnit
- 4.12. Using Mutation Coverage In Eclipse
- 4.13. Mutation Testing Basics
- 4.13.1. Types of Mutants
- 4.13.1.1. Arithmetic Operation Mutant
- 4.13.1.2. Example Code 1: Arithmetic Operation Mutant
- 4.13.1.3. Logical Expression Mutant (Remove Conditionals)
- 4.13.1.4. Example Code 2: Logical Expression Mutant (Remove Conditionals)
- 4.13.1.5. Example Code 3: Multiple Mutants in One (EvenOddCheck)
- 4.13.1.6. Example Code 4: Loop Conditions (optional)
- 4.13.1. Types of Mutants
- 4.14. Mutation Coverage Advanced Examples
- 4.15. Testing
- 4.16. Testing for Code Coverage
- 4.17. Bowling Test Coverage Example
- 4.18. Bowling Example: Testing to Code
Chapter 5 Introduction to Pointers in Java¶
- 5.1. Basic References Part 1
- 5.2. Basic References Part 2
- 5.3. Pointers Syntax
- 5.4. Local Memory
- 5.5. Heap Memory
- 5.6. Link Nodes
- 5.7. Link Nodes Practice Exercises
- 5.8. Pointers Concepts Summary
- 5.9. Additional Practice Exercises
- 5.10. More Practice Exercises
- 5.10.1. AddNodeAfterRef7
- 5.10.2. ChangeHeadNodeValue
- 5.10.3. ConcatenateTwoLists
- 5.10.4. DeleteNode
- 5.10.5. FirstNodeEqualsValue
- 5.10.6. InsertListAfterRef13
- 5.10.7. InsertListInMiddle
- 5.10.8. LastNodeParam5
- 5.10.9. LastNodeRef1
- 5.10.10. LoopInChain15
- 5.10.11. MiddleNodeRef3
- 5.10.12. ReferenceSecondLastNode
- 5.10.13. ReferenceValueNode
- 5.10.14. RemoveRefNext9
- 5.10.15. ReverseUpToRef11
Chapter 6 Mathematical Background¶
Chapter 7 Algorithm Analysis¶
- 7.1. Chapter Introduction
- 7.2. Problems, Algorithms, and Programs
- 7.3. Comparing Algorithms
- 7.4. Best, Worst, and Average Cases
- 7.5. Faster Computer, or Faster Algorithm?
- 7.6. Asymptotic Analysis and Upper Bounds
- 7.7. Lower Bounds and \(\Theta\) Notation
- 7.8. Calculating Program Running Time
- 7.9. Analyzing Problems
- 7.10. Common Misunderstandings
- 7.11. Multiple Parameters
- 7.12. Space Bounds
- 7.13. Code Tuning and Empirical Analysis
- 7.14. Algorithm Analysis Summary Exercises
- 7.15. Algorithm Analysis Summary Exercises
Chapter 8 Recursion¶
- 8.1. Introduction to Recursion
- 8.2. Writing a recursive function
- 8.3. Code Completion Practice Exercises
- 8.3.1. Introduction
- 8.3.2. Recursion Programming Exercise: Largest
- 8.3.3. Recursion Programming Exercise: Multiply
- 8.3.4. Recursion Programming Exercise: GCD
- 8.3.5. Recursion Programming Exercise: log
- 8.3.6. Recursion Programming Exercise: Cummulative Sum
- 8.3.7. Recursion Programming Exercise: Add odd values
- 8.3.8. Recursion Programming Exercise: Sum Of the Digits
- 8.3.9. Recursion Programming Exercise: Count Characters
- 8.4. Writing More Sophisticated Recursive Functions
- 8.5. Intermediate Recursion Code Completion Exercises
- 8.6. Writing Practice Exercises
- 8.7. Tracing Recursive Code
- 8.8. Recursion Code Tracing Practice Exercises
- 8.9. Recursion Summary Questions
Chapter 9 Linear Structures¶
- 9.1. Chapter Introduction: Lists
- 9.2. A List ADT
- 9.3. Array-Based List Implementation
- 9.4. Linked Lists
- 9.5. Comparison of List Implementations
- 9.6. Doubly Linked Lists
- 9.7. List Element Implementations
- 9.8. Stacks
- 9.9. Linked Stacks
- 9.10. Freelists
- 9.11. Implementing Recursion
- 9.12. Queues
- 9.13. Linked Queues
- 9.14. Linear Structure Summary Exercises
Chapter 10 Design¶
Chapter 11 Binary Trees¶
- 11.1. Binary Trees Chapter Introduction
- 11.2. Binary Trees
- 11.3. Binary Tree as a Recursive Data Structure
- 11.4. The Full Binary Tree Theorem
- 11.5. Binary Tree Traversals
- 11.6. Implementing Tree Traversals
- 11.7. Information Flow in Recursive Functions
- 11.7.1. Information Flow in Recursive Functions
- 11.7.2. Binary Tree Set Depth Exercise
- 11.7.3. Collect-and-return
- 11.7.4. Binary Tree Check Sum Exercise
- 11.7.5. Binary Tree Leaf Nodes Count Exercise
- 11.7.6. Binary Tree Sum Nodes Exercise
- 11.7.7. Combining Information Flows
- 11.7.8. Binary Tree Check Value Exercise
- 11.7.9. Combination Problems
- 11.7.10. Binary Tree Height Exercise
- 11.7.11. Binary Tree Get Difference Exercise
- 11.7.12. Binary Tree Has Path Sum Exercise
- 11.8. Binary Tree Node Implementations
- 11.9. Composite-based Expression Tree
- 11.10. Binary Tree Space Requirements
- 11.11. Binary Search Trees
- 11.12. Dictionary Implementation Using a BST
- 11.13. Binary Tree Guided Information Flow
- 11.14. Multiple Binary Trees
- 11.15. A Hard Information Flow Problem
- 11.16. Array Implementation for Complete Binary Trees
- 11.17. Heaps and Priority Queues
- 11.18. Huffman Coding Trees
- 11.19. Trees versus Tries
- 11.20. Proof of Optimality for Huffman Coding
- 11.21. Binary Tree Chapter Summary
Chapter 12 Sorting¶
- 12.1. Chapter Introduction: Sorting
- 12.2. Sorting Terminology and Notation
- 12.3. Insertion Sort
- 12.4. Bubble Sort
- 12.5. Selection Sort
- 12.6. The Cost of Exchange Sorting
- 12.7. Optimizing Sort Algorithms with Code Tuning
- 12.8. Shellsort
- 12.9. Mergesort Concepts
- 12.10. Implementing Mergesort
- 12.11. Quicksort
- 12.12. Heapsort
- 12.13. Binsort
- 12.14. Radix Sort
- 12.15. An Empirical Comparison of Sorting Algorithms
- 12.16. Lower Bounds for Sorting
- 12.17. Sorting Summary Exercises
Chapter 13 File Processing¶
Chapter 14 Hashing¶
Chapter 15 Memory Management¶
- 15.1. Chapter Introduction: Memory Management
- 15.2. Dynamic Storage Allocation
- 15.3. Sequential-Fit Methods
- 15.4. First Fit Memory Allocation
- 15.5. Circular First Fit
- 15.6. Best Fit Memory Manager
- 15.7. Worst Fit Memory Manager
- 15.8. Sequential Fit Peformance
- 15.9. Buddy Method and Other Memory Allocation Methods
- 15.10. Failure Policies and Garbage Collection
Chapter 16 Indexing¶
Chapter 17 General Trees¶
Chapter 18 Graphs¶
Chapter 19 Spatial Data Structures¶
Chapter 20 Algorithms Introduction¶
Chapter 21 Analyzing Problems: The Basics¶
Chapter 22 Searching¶
Chapter 23 Lower Bounds¶
Chapter 24 Dynamic Programming¶
Chapter 25 Limits to Computing¶
- 25.1. Limits to Computing
- 25.2. Reductions
- 25.3. NP-Completeness
- 25.4. NP-Completeness Proofs
- 25.5. Circuit Satisfiability
- 25.6. Formula Satisfiability
- 25.7. 3-CNF Satisfiability
- 25.8. Reduction of SAT to 3-SAT
- 25.9. The Clique Problem
- 25.10. The Independent Set Problem
- 25.11. The Vertex Cover Problem
- 25.12. The Hamiltonian Cycle Problem
- 25.13. The Traveling Salesman Problem
- 25.14. Reduction of Circuit SAT to SAT
- 25.15. Reduction of 3-SAT to Clique
- 25.16. Reduction of Independent Set to Vertex Cover
- 25.17. Reduction of 3-SAT to Hamiltonian Cycle
- 25.18. Reduction of Clique to Independent Set
- 25.19. Reduction of Hamiltonian Cycle to Traveling Salesman
- 25.20. Coping with NP-Complete Problems
- 25.21. Unsolvable Problems
Chapter 26 Number Problems¶
Chapter 27 Grammars¶
Chapter 28 Functional Programming¶
- 28.1. List Construction and Deconstruction
- 28.2. Developing Basic, Recursive List-processing Functions
- 28.3. Recurring On Lists That Aren’t Flat
- 28.4. Using Helper Functions with Accumulators
- 28.5. Scope, Closures, Higher-order Functions, Static vs. Dynamic Binding
- 28.6. Procedural Abstraction: Map, Curry, and Compose
- 28.7. Procedural Abstraction: The Filtering and Folding (or Reduce) Patterns
- 28.8. Combining Map and Reduce
- 28.9. Continuations and Continuation Passing
Chapter 29 Lambda Calculus¶
Chapter 30 Interpreting the Functional Language SLang¶
Chapter 31 Variations on Parameter Passing¶
Chapter 32 Type Systems¶
- 32.1. Types in Programming Languages
- 32.1.1. Motivating Examples
- 32.1.2. Type System: Definition
- 32.1.3. Type System: Static Versus Dynamic
- 32.1.4. Type System: Safe Versus Unsafe
- 32.1.5. Type System: Strong Versus Weak
- 32.1.6. Type System: Typed Variables or Values
- 32.1.7. Type System: Explicit Versus Implicit typing
- 32.1.8. The Many Uses of Type Systems
- 32.2. Type Inference
- 32.2.1. Type Environments
- 32.2.2. Typing Rules Expressed as Post Systems
- 32.2.3. Typing in a Scaled-down ML
- 32.2.4. Using Post System Rules to Describe Type Inferencing in ML
- 32.2.5. Parametric Polymorphism in ML
- 32.2.6. Type inferencing in ML
- 32.2.7. Type Inferencing Problem 1
- 32.2.8. Type Inferencing Problem 2
- 32.2.9. Type Inferencing Problem 3
- 32.2.10. Type Inferencing Problem 4
- 32.2.11. Type Inferencing Problem 5
- 32.2.12. Type Inferencing Problem 6
Chapter 33 Formal Languages Course Introduction¶
Chapter 34 Finite Acceptors¶
Chapter 35 Regular Languages¶
Chapter 36 Identifying Non-regular Languages¶
Chapter 37 Context-Free Grammars and Languages¶
- 37.1. Context-Free Grammars Part 1
- 37.2. Context-Free Grammars Part 2
- 37.3. Writing Compilers
- 37.4. CFG exercises
- 37.5. Transforming Grammars
- 37.6. Transforming Grammars Exercises
