Chapter 0 Command Line and Git¶
- 0.1. Command Line
- 0.2. Additional Practice Exercises
- 0.3. Git
- 0.4. Exercises
- 0.4.1. git clone
- 0.4.2. git status
- 0.4.3. git add
- 0.4.4. git rm
- 0.4.5. git commit
- 0.4.6. git push
- 0.4.7. git restore
- 0.4.8. git restore –staged
- 0.4.9. git pull
- 0.4.10. git commit -a
- 0.4.11. git commit (path)
- 0.4.12. git branch
- 0.4.13. git switch
- 0.4.14. git switch -c
- 0.4.15. git switch diverged branches
- 0.4.16. Challenge 1
- 0.4.17. Challenge 2
- 0.4.18. Challenge 3
Chapter 1 Introduction to Software Design¶
- 1.1. Getting Started
- 1.1.1. Installing BlueJ
- 1.1.2. Introducing LightBot
- 1.1.3. From LightBot to Micro Worlds
- 1.1.4. Self Check: Micro-Worlds
- 1.1.5. A Bit More LightBot
- 1.1.6. Textually Representing Programs
- 1.1.7. Self-Check: Turning Micro-Worlds into Code
- 1.1.8. What Does LightBot Say About Programming?
- 1.1.9. A Programmable LightBot in Java
- 1.1.10. Syntax Practice 1a
- 1.1.11. Creating New Objects
- 1.1.12. Calling Methods on an Object
- 1.1.13. Putting it All Together
- 1.1.14. A Word on Making Code Easy to Read
- 1.1.15. Syntax Practice 1b
- 1.1.16. Programming Practice 1
- 1.1.17. Check Your Understanding
- 1.2. Inheritance and Polymorphism: Subclasses and Methods
- 1.2.1. The Jeroos of Santong Island
- 1.2.2. Your Opinions on Course Grading Policies
- 1.2.3. Class Hierarchy and Inheritance
- 1.2.4. Summarizing: What is Inheritance?
- 1.2.5. Syntax Practice 2a: Jeroo Methods
- 1.2.6. Problem Solving and Algorithms
- 1.2.7. Creating and Using Jeroo Methods
- 1.2.8. What is Polymorphism?
- 1.2.9. Syntax Practice 2b: Subclass Constructors
- 1.2.10. Syntax Practice 2c: More Subclass Constructors
- 1.2.11. Programming Practice 2
- 1.2.12. Check Your Understanding
- 1.3. Conditional and Repeating Actions
- 1.3.1. Selection
- 1.3.2. Conditions Using Sensor Methods
- 1.3.3. An Overview of Conditional Statements
- 1.3.4. Java’s Syntax for the If-Then-Else Structure
- 1.3.5. Syntax Practice 3a: If-Then-Else
- 1.3.6. Creating Optional Statements With If-then
- 1.3.7. Java’s Syntax for the If-then Structure
- 1.3.8. Syntax Practice 3b: If-Then
- 1.3.9. Java’s Syntax for the Multi-way Selection Structure (a cascaded if)
- 1.3.10. Syntax Practice 3c: Multi-way If
- 1.3.11. Compound Conditions
- 1.3.12. Syntax Practice 3d: Compound Conditions
- 1.3.13. Your Opinions on Learning and Engagement
- 1.3.14. Repeating Actions
- 1.3.15. Generic Repetition Structures
- 1.3.16. Java’s Syntax for the While Loop
- 1.3.17. Syntax Practice 3e: While Loops
- 1.3.18. Programming Practice 3
- 1.3.19. Check Your Understanding
- 1.4. Software Testing
- 1.4.1. What Is Software Testing?
- 1.4.2. Writing Your First Software Test
- 1.4.3. Check Your Understanding: Software Testing Concepts
- 1.4.4. More About Methods
- 1.4.5. Check Your Understanding: Method Signatures
- 1.4.6. Check Your Understanding: Methods with Parameters
- 1.4.7. Good Habits for Conditionals
- 1.4.8. A Different Type of Complex If-Statement
- 1.4.9. Short Circuit Evaluation
- 1.4.10. Check Your Understanding: Logical Equivalence
- 1.4.11. Syntax Practice 4a: Compound Conditionals
- 1.4.12. Syntax Practice 4b: Conditionals and Relational Operators
- 1.4.13. Programming Practice 4
- 1.4.14. Module Review
- 1.5. Variables, Fields, and Parameters
- 1.5.1. Variables
- 1.5.2. Check Your Understanding: Variables
- 1.5.3. Fields Versus Local Variables
- 1.5.4. Changing Private Variables: Mutator Methods
- 1.5.5. Check your Understanding: Scope
- 1.5.6. Accessor Methods
- 1.5.7. Check Your Understanding: Fields, Getters and Setters
- 1.5.8. Syntax Practice 5a: Fields and Accessors
- 1.5.9. The Return Keyword
- 1.5.10. Check your Understanding: Typed Methods and Return Statements
- 1.5.11. Syntax Practice 5b: Mutators and Return Statements
- 1.5.12. Using Fields in Testing
- 1.5.13. Programming Practice 5a
- 1.5.14. Programming Practice 5b
- 1.6. Pictures and For-each Loops
- 1.7. Aggregation, Strings and More Loops
- 1.7.1. Object-Oriented Design: Aggregation, Composition, and Delegation
- 1.7.2. Strings and Characters
- 1.7.3. Check Your Understanding: Strings
- 1.7.4. Counter-controlled Loops
- 1.7.5. Check Your Understanding: Counter Controlled Loops
- 1.7.6. Tips on Random Numbers
- 1.7.7. Check Your Understanding: Random Numbers
- 1.7.8. Method Overriding
- 1.7.9. Check Your Understanding: Method Overriding
- 1.7.10. Syntax Practice 7a: For Loops and OO Design
- 1.7.11. Syntax Practice 7b: toString and Returning Values
- 1.7.12. Programming Practice 7a
- 1.7.13. Programming Practice 7b
- 1.8. Grouping Objects Using Lists and Nested For Loops
- 1.8.1. Collections of Objects
- 1.8.2. Interfaces
- 1.8.3. Check Your Understanding: Interfaces
- 1.8.4. Syntax Practice 8a: Strings
- 1.8.5. The List Interface
- 1.8.6. Generics
- 1.8.7. ArrayList
- 1.8.8. Check Your Understanding: ArrayLists
- 1.8.9. Syntax Practice 8b: Lists
- 1.8.10. Nested For Loops
- 1.8.11. Check Your Understanding: Nested For Loops
- 1.8.12. Syntax Practice 8c: Nested Loops
- 1.8.13. Check Your Understanding
- 1.8.14. Programming Practice 8a
- 1.8.15. Programming Practice 8b
- 1.9. Lists, Loop Idioms, Generics, and the Null Keyword
- 1.9.1. Modelling the Contents of a Library
- 1.9.2. Looping Idioms
- 1.9.3. Check Your Understanding: Loop Idioms
- 1.9.4. Syntax Practice 9a: Loop Idioms
- 1.9.5. Generics Revisited
- 1.9.6. Check Your Understanding: Generics
- 1.9.7. Syntax Practice 9b: Generics
- 1.9.8. The Null Keyword
- 1.9.9. Diagnosing a Null Pointer Exception
- 1.9.10. Check Your Understanding: Null
- 1.9.11. Using BlueJ’s Debugger
- 1.9.12. Using BlueJ’s Code Pad
- 1.9.13. Programming Practice 9a: Loop Idioms
- 1.9.14. Programming Practice 9b: Loops and Generics
- 1.10. Arrays
- 1.10.1. Creating An Array
- 1.10.2. Accessing Items in Arrays
- 1.10.3. Setting Items in an Array
- 1.10.4. Arrays Compared to Lists (or ArrayList)
- 1.10.5. Putting It All Together
- 1.10.6. Check Your Understanding: Arrays
- 1.10.7. Syntax Practice 10a
- 1.10.8. Iterating Over Arrays
- 1.10.9. Check Your Understanding: Iterating with Arrays
- 1.10.10. Syntax Practice 10b
- 1.10.11. Initializing Array Contents
- 1.10.12. Printing Arrays
- 1.10.13. Copying Array Variables
- 1.10.14. Naming Array Variables
- 1.10.15. Writing Test Assertions Involving Arrays
- 1.10.16. Applying Arrays in a Problem
- 1.10.17. Syntax Practice 10c
- 1.10.18. Check Your Understanding
- 1.10.19. Programming Practice 10a
- 1.10.20. Programming Practice 10b
- 1.11. Multi-dimensional Arrays
- 1.11.1. Dimensions in an Array
- 1.11.2. Check Your Understanding: 2D Arrays
- 1.11.3. Syntax Practice: 2D Array Basics
- 1.11.4. Iterating through a 2D Array
- 1.11.5. Check Your Understanding: Iterating with 2D Arrays
- 1.11.6. Syntax Practice: Looping Over 2D Arrays
- 1.11.7. Multi-Dimensional Arrays
- 1.11.8. Syntax Practice: 3D Arrays
- 1.11.9. But Can You Have Multi-dimensional Lists?
- 1.11.10. Integer Division and Modulus
- 1.11.11. Check Your Understanding: Modulus
- 1.11.12. Syntax Practice: Modulus
- 1.11.13. Programming Practice: Multi-dimensional Arrays
- 1.11.14. Programming Practice: Mod
- 1.12. Variable Scoping, Input, and Output
- 1.12.1. Variable Scoping
- 1.12.2. Summarizing Scope Concepts
- 1.12.3. Check Your Understanding: Scope
- 1.12.4. Syntax Practice: Scoping
- 1.12.5. Java Input and Output
- 1.12.6. Output Using PrintWriters
- 1.12.7. Check Your Understanding: Output
- 1.12.8. Input Using Scanners
- 1.12.9. A Complete Input Example
- 1.12.10. Check Your Understanding: Input
- 1.12.11. A Complete Input/Output Example
- 1.12.12. Testing I/O-based Operations
- 1.12.13. Check Your Understanding: Testing
- 1.13. Maps and Sets
- 1.13.1. The Map and Set Interfaces
- 1.13.2. The Map Interface
- 1.13.3. Syntax Practice: Making Maps
- 1.13.4. Adding and Accessing Pairs in a Map
- 1.13.5. Syntax Practice: Adding to Maps
- 1.13.6. Checking for and Removing Pairs in a Map
- 1.13.7. A Visual Summary of Using Map and HashMap
- 1.13.8. Syntax Practice: Map Contains and Remove
- 1.13.9. Looping Over Map Contents
- 1.13.10. Check Your Understanding: Maps
- 1.13.11. Your Opinions on Course Grading Policies
- 1.13.12. The Set Interface
- 1.13.13. Syntax Practice: Making A Set
- 1.13.14. Adding Values to a Set
- 1.13.15. Syntax Practice: Adding to a Set
- 1.13.16. Checking Values in a Set
- 1.13.17. Syntax Practice: Set Contains
- 1.13.18. Removing Values from a Set
- 1.13.19. Syntax Practice: Set Remove
- 1.13.20. Looping Over Sets
- 1.13.21. Check Your Understanding: Sets
- 1.13.22. Programming Practice: Maps
- 1.14. Static, Main, and Exceptions
- 1.14.1. The Main Method
- 1.14.2. Check Your Understanding: Main Methods
- 1.14.3. The Static Keyword
- 1.14.4. Check Your Understanding: The Static Keyword
- 1.14.5. Your Opinions on Learning and Engagement
- 1.14.6. Errors
- 1.14.7. Throwing Exceptions
- 1.14.8. Check Your Understanding: Throwing Exceptions
- 1.14.9. Syntax Practice: Throwing Exceptions
- 1.14.10. Try/Catch Blocks
- 1.14.11. Check Your Understanding: Try/Catch Blocks
- 1.14.12. Syntax Practice: Try-Catch Blocks
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. Mutation Coverage In JUnit
- 4.13. Mutation Testing Examples
- 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: FAQ
- 4.14.1. Frequently Asked Questions
- 4.14.1.1. What is Mutation Testing and why should I use it?
- 4.14.1.2. Does 100% Mutation Score mean 100% Project Correctness?
- 4.14.1.3. Why does writing Mutation Tests take so much time?
- 4.14.1.4. Why should I use Mutation Testing instead of Code Coverage?
- 4.14.1.5. Why are we using this particular set of mutation operators?
- 4.14.1.6. Does 100% Mutation Score mean my code is perfect?
- 4.14.1.7. Why do I have bugs in my code despite having 100% Mutation Score?
- 4.14.1.8. Why do my mutation tests not cover all branches of my code?
- 4.14.1.9. How do I localize the bugs in my code?
- 4.14.1.10. How do I recover the “Mutation List”/”Mutation Summary” tabs?
- 4.14.1. Frequently Asked Questions
- 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. Syntax of the Lambda Calculus
- 5.4. Local Memory
- 5.5. Heap Memory
- 5.6. Link Nodes
- 5.7. Link Nodes Practice Exercises
- 5.8. Pointers Concepts Summary
- 5.2. Additional Practice Exercises
- 5.9. More Practice Exercises
- 5.9.1. AddNodeAfterRef7
- 5.9.2. ChangeHeadNodeValue
- 5.9.3. ConcatenateTwoLists
- 5.9.4. DeleteNode
- 5.9.5. FirstNodeEqualsValue
- 5.9.6. InsertListAfterRef13
- 5.9.7. InsertListInMiddle
- 5.9.8. LastNodeParam5
- 5.9.9. LastNodeRef1
- 5.9.10. LoopInChain15
- 5.9.11. MiddleNodeRef3
- 5.9.12. ReferenceSecondLastNode
- 5.9.13. ReferenceValueNode
- 5.9.14. RemoveRefNext9
- 5.9.15. ReverseUpToRef11
Chapter 6 Mathematical Background¶
Chapter 7 Algorithm Analysis¶
- 7.1. Problems, Algorithms, and Programs
- 7.2. Comparing Algorithms
- 7.3. Best, Worst, and Average Cases
- 7.4. Faster Computer, or Faster Algorithm?
- 7.5. Asymptotic Analysis and Upper Bounds
- 7.6. Lower Bounds and \(\Theta\) Notation
- 7.7. Calculating Program Running Time
- 7.8. Analyzing Problems
- 7.9. Common Misunderstandings
- 7.10. Multiple Parameters
- 7.11. Space Bounds
- 7.12. Code Tuning and Empirical Analysis
- 7.13. Algorithm Analysis Summary Exercises
Chapter 8 Recursion¶
- 8.1. Introduction
- 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. Harder Code Completion Practice Exercises
- 8.6. Writing Practice Exercises
- 8.7. Tracing Recursive Code
- 8.8. Tracing Practice Exercises
- 8.9. Recursion Summary Exercises
Chapter 9 Linear Structures¶
- 9.1. The List ADT
- 9.2. Array-Based List Implementation
- 9.3. Linked Lists
- 9.4. Comparison of List Implementations
- 9.5. Doubly Linked Lists
- 9.6. List Element Implementations
- 9.7. Stacks
- 9.8. Linked Stacks
- 9.9. Freelists
- 9.10. Implementing Recursion
- 9.11. Queues
- 9.12. Linked Queues
- 9.13. Linear Structure Summary Exercises
Chapter 10 Design¶
Chapter 11 Binary Trees¶
- 11.1. Binary Trees
- 11.2. Binary Tree as a Recursive Data Structure
- 11.3. The Full Binary Tree Theorem
- 11.4. Binary Tree Traversals
- 11.5. Implementing Tree Traversals
- 11.6. Information Flow in Recursive Functions
- 11.6.1. Information Flow in Recursive Functions
- 11.6.2. Binary Tree Set Depth Exercise
- 11.6.3. Collect-and-return
- 11.6.4. Binary Tree Check Sum Exercise
- 11.6.5. Binary Tree Leaf Nodes Count Exercise
- 11.6.6. Binary Tree Sum Nodes Exercise
- 11.6.7. Combining Information Flows
- 11.6.8. Binary Tree Check Value Exercise
- 11.6.9. Combination Problems
- 11.6.10. Binary Tree Height Exercise
- 11.6.11. Binary Tree Get Difference Exercise
- 11.6.12. Binary Tree Has Path Sum Exercise
- 11.7. Binary Tree Node Implementations
- 11.8. Composite-based Expression Tree
- 11.9. Binary Tree Space Requirements
- 11.10. Binary Search Trees
- 11.11. Dictionary Implementation Using a BST
- 11.12. Binary Tree Guided Information Flow
- 11.13. Multiple Binary Trees
- 11.14. A Hard Information Flow Problem
- 11.15. Array Implementation for Complete Binary Trees
- 11.16. Heaps and Priority Queues
- 11.17. Huffman Coding Trees
- 11.18. Trees versus Tries
- 11.19. Proof of Optimality for Huffman Coding
- 11.20. 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¶
Chapter 16 Indexing¶
Chapter 17 General Trees¶
Chapter 18 Graphs¶
Chapter 19 Advanced 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 1¶
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 Introduction¶
Chapter 34 Finite Acceptors¶
- 34.1. DFA: Deterministic Finite Acceptor
- 34.2. DFA exercises
- 34.3. DFA exercises
- 34.4. DFA exercises
- 34.5. DFA Complement Exercise
- 34.6. NFA: Non-Deterministic Finite Automata
- 34.7. NFA exercises
- 34.8. More NFA exercises
- 34.9. Minimizing the Number of States in a DFA
- 34.10. DFA Minimization Exercises
Chapter 35 Regular Languages¶
- 35.1. Regular Expressions
- 35.2. Regular Expressions Exercises
- 35.3. More Regular Expressions Exercises
- 35.4. The Power of Regular Expressions
- 35.5. Regular Grammars
- 35.6. Regular Grammars
- 35.7. Regular Grammars Exercises
- 35.8. More Regular Grammar Exercises
- 35.9. Closure Properties of Regular Languages
- 35.10. Properties
