Chapter 0 Introduction to Software Design¶
- 0.1. Getting Started
- 0.1.1. Installing BlueJ
- 0.1.2. Introducing LightBot
- 0.1.3. From LightBot to Micro Worlds
- 0.1.4. Self Check: Micro-Worlds
- 0.1.5. A Bit More LightBot
- 0.1.6. Textually Representing Programs
- 0.1.7. Self-Check: Turning Micro-Worlds into Code
- 0.1.8. What Does LightBot Say About Programming?
- 0.1.9. A Programmable LightBot in Java
- 0.1.10. Syntax Practice 1a
- 0.1.11. Creating New Objects
- 0.1.12. Calling Methods on an Object
- 0.1.13. Putting it All Together
- 0.1.14. We All Make Mistakes: Errors Happen
- 0.1.15. A Word on Making Code Easy to Read
- 0.1.16. Comparing Visual and Textual Programming
- 0.1.17. Syntax Practice 1b
- 0.1.18. Programming Practice 1
- 0.1.19. Check Your Understanding
- 0.2. Inheritance and Polymorphism: Subclasses and Methods
- 0.2.1. The Jeroos of Santong Island
- 0.2.2. Your Opinions on Course Grading Policies
- 0.2.3. Class Hierarchy and Inheritance
- 0.2.4. Summarizing: What is Inheritance?
- 0.2.5. Syntax Practice 2a: Jeroo Methods
- 0.2.6. Problem Solving and Algorithms
- 0.2.7. Creating and Using Jeroo Methods
- 0.2.8. What is Polymorphism?
- 0.2.9. Syntax Practice 2b: Subclass Constructors
- 0.2.10. Syntax Practice 2c: More Subclass Constructors
- 0.2.11. Programming Practice 2
- 0.2.12. Check Your Understanding
- 0.3. Conditional and Repeating Actions
- 0.3.1. Selection
- 0.3.2. Conditions Using Sensor Methods
- 0.3.3. An Overview of Conditional Statements
- 0.3.4. Java’s Syntax for the If-Then-Else Structure
- 0.3.5. Syntax Practice 3a: If-Then-Else
- 0.3.6. Creating Optional Statements With If-then
- 0.3.7. Java’s Syntax for the If-then Structure
- 0.3.8. Syntax Practice 3b: If-Then
- 0.3.9. Java’s Syntax for the Multi-way Selection Structure (a cascaded if)
- 0.3.10. Syntax Practice 3c: Multi-way If
- 0.3.11. Compound Conditions
- 0.3.12. Syntax Practice 3d: Compound Conditions
- 0.3.13. Repeating Actions
- 0.3.14. Generic Repetition Structures
- 0.3.15. Java’s Syntax for the While Loop
- 0.3.16. Syntax Practice 3e: While Loops
- 0.3.17. Programming Practice 3
- 0.3.18. Check Your Understanding
- 0.4. Software Testing
- 0.4.1. What Is Software Testing?
- 0.4.2. Writing Your First Software Test
- 0.4.3. Check Your Understanding: Software Testing Concepts
- 0.4.4. More About Methods
- 0.4.5. Check Your Understanding: Method Signatures
- 0.4.6. Check Your Understanding: Methods with Parameters
- 0.4.7. Good Habits for Conditionals
- 0.4.8. A Different Type of Complex If-Statement
- 0.4.9. Short Circuit Evaluation
- 0.4.10. Check Your Understanding: Logical Equivalence
- 0.4.11. Syntax Practice 4a: Compound Conditionals
- 0.4.12. Syntax Practice 4b: Conditionals and Relational Operators
- 0.4.13. Programming Practice 4
- 0.4.14. Module Review
- 0.5. Variables, Fields, and Parameters
- 0.5.1. Variables
- 0.5.2. Check Your Understanding: Variables
- 0.5.3. Fields Versus Local Variables
- 0.5.4. Changing Private Variables: Mutator Methods
- 0.5.5. Check your Understanding: Scope
- 0.5.6. Accessor Methods
- 0.5.7. Check Your Understanding: Fields, Getters and Setters
- 0.5.8. Syntax Practice 5a: Fields and Accessors
- 0.5.9. The Return Keyword
- 0.5.10. Check your Understanding: Typed Methods and Return Statements
- 0.5.11. Syntax Practice 5b: Mutators and Return Statements
- 0.5.12. Using Fields in Testing
- 0.5.13. Programming Practice 5a
- 0.5.14. 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. Check Your Understanding: Strings
- 0.7.4. Counter-controlled Loops
- 0.7.5. Check Your Understanding: Counter Controlled Loops
- 0.7.6. Tips on Random Numbers
- 0.7.7. Check Your Understanding: Random Numbers
- 0.7.8. Method Overriding
- 0.7.9. Check Your Understanding: Method Overriding
- 0.7.10. Syntax Practice 7a: For Loops and OO Design
- 0.7.11. Syntax Practice 7b: toString and Returning Values
- 0.7.12. Programming Practice 7a
- 0.7.13. 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. Check Your Understanding: Interfaces
- 0.8.4. Syntax Practice 8a: Strings
- 0.8.5. The List Interface
- 0.8.6. Generics
- 0.8.7. ArrayList
- 0.8.8. Check Your Understanding: ArrayLists
- 0.8.9. Syntax Practice 8b: Lists
- 0.8.10. Nested For Loops
- 0.8.11. Check Your Understanding: Nested For Loops
- 0.8.12. Syntax Practice 8c: Nested Loops
- 0.8.13. Check Your Understanding
- 0.8.14. Programming Practice 8a
- 0.8.15. 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. Check Your Understanding: Loop Idioms
- 0.9.4. Syntax Practice 9a: Loop Idioms
- 0.9.5. Generics Revisited
- 0.9.6. Check Your Understanding: Generics
- 0.9.7. Syntax Practice 9b: Generics
- 0.9.8. The Null Keyword
- 0.9.9. Diagnosing a Null Pointer Exception
- 0.9.10. Check Your Understanding: Null
- 0.9.11. Using BlueJ’s Debugger
- 0.9.12. Using BlueJ’s Code Pad
- 0.9.13. Programming Practice 9a: Loop Idioms
- 0.9.14. Programming Practice 9b: Loops and Generics
- 0.10. Arrays
- 0.10.1. Creating An Array
- 0.10.2. Accessing Items in Arrays
- 0.10.3. Setting Items in an Array
- 0.10.4. Arrays Compared to Lists (or ArrayList)
- 0.10.5. Putting It All Together
- 0.10.6. Check Your Understanding: Arrays
- 0.10.7. Syntax Practice 10a
- 0.10.8. Iterating Over Arrays
- 0.10.9. Check Your Understanding: Iterating with Arrays
- 0.10.10. Syntax Practice 10b
- 0.10.11. Initializing Array Contents
- 0.10.12. Printing Arrays
- 0.10.13. Copying Array Variables
- 0.10.14. Naming Array Variables
- 0.10.15. Writing Test Assertions Involving Arrays
- 0.10.16. Applying Arrays in a Problem
- 0.10.17. Syntax Practice 10c
- 0.10.18. Check Your Understanding
- 0.10.19. Programming Practice 10a
- 0.10.20. Programming Practice 10b
- 0.11. Multi-dimensional Arrays
- 0.11.1. Dimensions in an Array
- 0.11.2. Check Your Understanding: 2D Arrays
- 0.11.3. Syntax Practice: 2D Array Basics
- 0.11.4. Iterating through a 2D Array
- 0.11.5. Check Your Understanding: Iterating with 2D Arrays
- 0.11.6. Syntax Practice: Looping Over 2D Arrays
- 0.11.7. Multi-Dimensional Arrays
- 0.11.8. Syntax Practice: 3D Arrays
- 0.11.9. But Can You Have Multi-dimensional Lists?
- 0.11.10. Integer Division and Modulus
- 0.11.11. Check Your Understanding: Modulus
- 0.11.12. Syntax Practice: Modulus
- 0.11.13. Programming Practice: Multi-dimensional Arrays
- 0.11.14. Programming Practice: Mod
- 0.12. Variable Scoping, Input, and Output
- 0.12.1. Variable Scoping
- 0.12.2. Summarizing Scope Concepts
- 0.12.3. Check Your Understanding: Scope
- 0.12.4. Syntax Practice: Scoping
- 0.12.5. Java Input and Output
- 0.12.6. Output Using PrintWriters
- 0.12.7. Check Your Understanding: Output
- 0.12.8. Input Using Scanners
- 0.12.9. A Complete Input Example
- 0.12.10. Check Your Understanding: Input
- 0.12.11. A Complete Input/Output Example
- 0.12.12. Testing I/O-based Operations
- 0.12.13. Check Your Understanding: Testing
- 0.13. Maps and Sets
- 0.13.1. The Map and Set Interfaces
- 0.13.2. The Map Interface
- 0.13.3. Syntax Practice: Making Maps
- 0.13.4. Adding and Accessing Pairs in a Map
- 0.13.5. Syntax Practice: Adding to Maps
- 0.13.6. Checking for and Removing Pairs in a Map
- 0.13.7. A Visual Summary of Using Map and HashMap
- 0.13.8. Syntax Practice: Map Contains and Remove
- 0.13.9. Looping Over Map Contents
- 0.13.10. Check Your Understanding: Maps
- 0.13.11. Your Opinions on Course Grading Policies
- 0.13.12. The Set Interface
- 0.13.13. Syntax Practice: Making A Set
- 0.13.14. Adding Values to a Set
- 0.13.15. Syntax Practice: Adding to a Set
- 0.13.16. Checking Values in a Set
- 0.13.17. Syntax Practice: Set Contains
- 0.13.18. Removing Values from a Set
- 0.13.19. Syntax Practice: Set Remove
- 0.13.20. Looping Over Sets
- 0.13.21. Check Your Understanding: Sets
- 0.13.22. Programming Practice: Maps
- 0.14. Static, Main, and Exceptions
- 0.14.1. The Main Method
- 0.14.2. Check Your Understanding: Main Methods
- 0.14.3. The Static Keyword
- 0.14.4. Check Your Understanding: The Static Keyword
- 0.14.5. Errors
- 0.14.6. Throwing Exceptions
- 0.14.7. Check Your Understanding: Throwing Exceptions
- 0.14.8. Syntax Practice: Throwing Exceptions
- 0.14.9. Try/Catch Blocks
- 0.14.10. Check Your Understanding: Try/Catch Blocks
- 0.14.11. Syntax Practice: Try-Catch Blocks
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
