References, Pointers and Abstract State Machine

References and Pointers

• Rather than directly storing simple values, references store a pointer to an object.
• The object pointed to by a reference is called the pointee.

Dereferencing

• Dereferencing involves accessing the value of a pointee through a reference variable,.
• The dot operator (.) is used to access a field or method of the pointee.
• Before dereferencing, a reference must be assigned to a pointee, otherwise, a NullPointerException occurs.
• Null references 'point to nothing."

Reference Assignment

• Assigning one reference to another makes both point to the same pointee.

Sharing

• Sharing occurs when two references point to a single pointee, making each reference an alias of the other.

Shallow vs. Deep Copying

• Shallow copying results in sharing.
• Deep copying creates a new copy of the pointee.

Abstract State Machine (ASM)

• ASM is a theoretical model that illustrates how memory is allocated during program execution.
• It consists of:
  • Workspace: The code the computer is currently executing.
  • Stack: Temporary storage for local variables and saved work/code.
  • Heap: Storage for objects and data structures.
• The initial state of an ASM has the entire program in the workspace and an empty stack and heap.
• The machine operates by choosing the 'next code statement' from the workspace and executing it.
• Executing the code can change the stack or heap.
• The machine stops when there are no more code statements in the workspace.

Primitive vs. Reference Values

• Primitive values are stored on the stack.
• Reference values, which are the addresses of data in the heap, indicate the location of objects.

Object and Reference Values

• Objects are allocated in the heap.
• The binding of a variable and the reference of an object are allocated in the stack.

Object Construction

• Allocates space for the new object in the heap including all fields
• Invoking a constructor in Java:
  • Allocates space for the new object in the heap, including slots for all fields and the class of the constructor (dynamic type).
  • After pushing parameters onto the stack, it runs the constructor body.
• To execute a method call (constructor code), the code is loaded into the workspace, while the current workspace is saved in the stack.
• The main method code is saved in the stack and parameter/primitive values pushed onto the stack
• An object is allocated in the heap and pushed onto the stack with a reference to the object.
• Then, the value of v is updated in the workspace.
• Assignment into the "this.x" field involves:
  • Looking up the value of "this" in the stack.
  • Writing to the 'x' slot of that object in the heap.

Nodes

• Linked nodes are a class containing data fields that store data and a reference to another linked node.
  • Data can be primitive or an object.
• They connect objects to form a list (chain of nodes), and serve as building blocks for programs storing large amounts of data without using an array.

Node Iteration

• Last node next field points to a null reference.
• Iterate/loop by following the next references with each iteration, update pointee of temporary node
• Create temporary node that points to head of chain (sharing)
• Stop when temporary node points to a null reference

Handling Failure

• Methods to handle failure
  • Error value: NaN, null, -1
  • Optional result: OCaml, options
  • Passes responsibility to caller
  • Exceptions: OCaml, Java

Exceptions

• Exceptions indicate abnormal termination conditions.
• The internal state describes what went wrong.
  • Examples: NullPointerException, IllegalArgumentException, IOException.
• Throwing an exception:
  • Causes an emergency exit from the current method.
  • Propagates up the invocation stack until caught or the program aborts.
• Catching an exception:
  • Allows the caller to handle abnormal circumstances appropriately using try/catch blocks.

Exception Class Hierarchy

• Helps categorize exception handling for different scenarios.

Checked/Declared Exceptions

• These exceptions are subtypes of Exception but not RuntimeException.
• They must be declared using the throw clause in the method type.
• Raising a checked exception can be done by directly throwing the exception or calling another method that might throw a checked exception.

Unchecked/Undeclared Exceptions

• Subtypes of RuntimeException that do not need to be declared via throws.
  • Examples are NullPointerException, IndexOutOfBoundsException, and IllegalArgumentException.

Finally Clause

• A finally clause in a try/catch/finally statement always executes, regardless of whether an exception is thrown, propagated, or caught.
• Used to release resources held by the try block.

Recursion

• When a function invokes itself to do part of the work.
• Consists of:
  • Base Case: A simple input that can be solved without a recursive call.
  • Recursive Part: Contains one or more recursive calls to the function.
• In every recursive call, parameters must be 'closer' to the base case than the original call.

Run-Time Stack and Activation Frames

• When a new method is called, Java pushes a new activation frame to the run-time stack.
• Activation frames store:
  • Function arguments
  • Local variables
  • Return address of the instruction that called the method

Recursive Array Search

• Consists of linear and binary search options which can be used recursively.

Sets and Relations

• Set: A collection of distinguishable members or elements.

Properties of Relations

• Reflexive
• Irreflexive
• Symmetric
• Antisymmetric
• Transitive

Equivalence Relation

• Reflexive
• Symmetric
• Transitive

Partial Orders

• Non-strict partial order:
  • Antisymmetric
  • Reflexive
  • Transitive
• Strict partial order:
  • Antisymmetric
  • Irreflexive
  • Transitive
• Total order:
  • Every pair of distinct elements in a partial order are comparable

Time and Space Complexity

• Problem: A task to be performed.
• Algorithm: A method or process followed to solve a problem.
• Program: An instance or representation of an algorithm in a programming language.
• Asymptotic analysis: Estimating the resource consumption of an algorithm.
• Growth rate: The rate at which the cost of an algorithm grows as the size of the input grows.
• Upper bound: A growth rate that is always greater than or equal to the growth rate of the algorithm being analyzed.
• Worst case: The problem instance from all problem instances for a given input size n that has the greatest cost.

Big-Oh Notation

• Used to represent Time Complexity, providing an upper bound.
• Helps formalize growth rate by expressing the runtime of an algorithm T as a function of the size of the input n.
• Input size examples include parsing strings, sorting, searching, and binary exponentiation.
  • Input size examples
    • Parsing strings
    • Sorting a collection
    • Searching in a collection
    • Binary exponentiation
• Big-Oh gives an upper bound
• Simplifying rules are applied, such as ignoring constants and lower-order terms.

Space Complexity

• This is the memory required by an algorithm or data structure until it executes completely, expressed as a function of the input size.
• Includes:
  • Input space: The memory space used by its inputs.
  • Auxiliary space: Additional memory space used during execution.

Data Structure Space Requirements

• Overhead: The amount of space used by all information stored by a data structure aside from the actual data.
  • Smaller overhead means better space complexity.
• Array-based data structures: Overhead is unused space if the array is not full.
• Linked node-based data structures: Overhead is space used by nodes' pointers/references to the next or previous node.

Space Requirements

• Given:
  • N: number of elements in DS
  • P: size of pointer
  • E: size of data stored
  • D: maximum number of elements that can be stored in the array
• Array-based DS: D*E
• Linked List space complexity: n(P+E)

Explore references, pointers, dereferencing, and reference assignment. Understand sharing, shallow vs. deep copying, and the Abstract State Machine (ASM). Learn how memory is allocated during program execution.