Reference Types & Abstract State Machine (ASM)

• Reference types store a reference to an object, not the value directly.
• The object the reference points to is called the pointee.
• Dereferencing accesses the pointee's value using the dot operator (.).
• A reference must be assigned a pointee before dereferencing to avoid a NullPointerException.
• Null signifies a reference that 'points to nothing'.
• Assigning one reference to another makes them both point to the same object (pointee).
• Sharing occurs when two references point to the same object, creating aliases.
• Shallow copy creates sharing, while deep copy creates a new, independent copy.

Abstract State Machine (ASM)

• A theoretical model for visualizing memory allocation during program execution.
• Workspace holds the currently executing code.
• Stack is a temporary storage for local variables and saved code.
• Heap stores objects and data structures.
• The initial state has the program in the workspace, and empty stack and heap.
• The machine operates by executing the 'next code statement' in the workspace, potentially altering the stack or heap.
• Execution stops when no code statements remain.
• Primitive values are stored on the stack.
• Reference values, representing object addresses, are stored in the stack.
• Objects themselves are allocated in the heap.
• Binding between a variable and the object's reference occurs in the stack.

Object Construction

• Invoking a constructor allocates space for a new object in the heap.
• This space includes slots for all fields and stores the constructor's class (dynamic type).
• Constructor parameters are pushed onto the stack before the constructor body is run.

Method Calls

• Executing a method call (including constructors) requires loading the code into the workspace.
• The current workspace is saved on the stack.
• Parameters and primitive values are pushed onto the stack. An object is allocated in the heap, and a reference to the object is pushed onto the stack.
• Default values (e.g., 0 for integers) are initially assigned to fields in the heap.
• Assignment to this.x involves looking up the value of this in the stack and writing to the x slot of that object in the heap.

Nodes

• Building blocks that connect objects to form lists
• A class containing data fields (primitive or object) and a reference to another node.
• Useful for storing large amounts of data without fixed-size arrays.
• In a chain of nodes, the last node's next field points to null.
• Iteration: create a temporary node pointing to head of chain, follow the next references with each iteration, update the temporary node and stop when the temporary node points to null.

Handling Failure with Exceptions

• Expect conditions to satisfy arguments
• Interfaces imprecise
• Remove operations not supported
• Failures in external components (e.g. file not found)
• Exhausted resources (e.g. out of memory)
• Instead of reporting error values (NaN, -1, null) use exceptions
• Exceptions are objects representing abnormal termination conditions.
• They contain internal state describing the error.
• Examples includeNullPointerException, IllegalArgumentException, and IOException.
• Exceptions acts as an emergency exit from current method.
• Exceptions propagate up the invocation stack until caught, otherwise the program aborts.
• Catching an exception allows the caller to handle the abnormal situation.

Exception types

• Checked/Declared Exceptions: Subtypes of Exception (excluding RuntimeException), must be declared in the method signature using a throws clause.
• Unchecked/Undeclared Exceptions: Subtypes of RuntimeException, do not require a throws clause (e.g., NullPointerException, IndexOutOfBoundsException).
• The finally clause in a try/catch/finally statement always executes, regardless of exceptions.
• Used to release resources held by the try block.

Recursion

• Functions invoke themselves to solve subproblems.
• Base case: a simple input solved without recursion.
• Recursive part: contains recursive calls.
• Recursive calls bring parameters 'closer' to the base case.
• To trace a recursive function: Draw out all frames of execution until the base case and values are returned and "unwind".

Run-Time Stack and Activation Frames

• The run-time stack stores activation frames.
• Each activation frame holds function arguments, local variables, and the return address.
• A new activation frame is pushed onto the stack with each method call.

Recursive Array Search Algorithms

• Linear search sequentially checks each element.
• Binary search repeatedly divides the search interval in half.

Set Notation and Relations

• Sets are collections of distinguishable members or elements.

Properties of relations

• Reflexive: Every element is related to itself.
• Irreflexive: No element is related to itself.
• Symmetric: If a is related to b, then b is related to a.
• Antisymmetric: If a is related to b and b is related to a, then a and b are the same element.
• Transitive: If a is related to b and b is related to c, then a is related to c.

Other

• Equivalence Relation: Reflexive, symmetric, and transitive.
• Partial Orders:
  • Non-strict: Antisymmetric, reflexive, and transitive.
  • Strict: Antisymmetric, irreflexive, and transitive.
• Total Order: Every pair of distinct elements is comparable.

Time and Space Complexity

• Problem: A task to be performed.
• Algorithm: A method/process to solve a problem.
• Program: An algorithm's representation in a programming language.
• Asymptotic analysis: Estimates algorithm resource consumption.
• Growth rate: How the algorithm's cost increases with input size.
• Upper bound: A growth rate always greater than or equal to the algorithm's growth rate.
• Worst case: The problem instance with the greatest cost for a given input size.

Big-Oh Notation

• Captures the upper bound (worst-case) time complexity.
• Expresses runtime T as a function of input size n.

Space Complexity

• Amount of memory required by an algorithm or data structure.
• Input space: Memory used by the inputs.
• Auxiliary space: Additional memory used during execution.

Data Structure Space Requirements

• Overhead refers to the extra space used, excluding the actual data. Smaller overhead results in better space complexity.
• Array-based structures: Overhead is unused space when the array isn't full.
• Linked node structures: Overhead is space used by node pointers (references to next/previous nodes).
• Space complexities
  • Array based DS : D*E
  • Linked List space complexity : n(P+E)
    • 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

Understand reference types, pointees, dereferencing, and null references. Learn about sharing and copying, and the Abstract State Machine (ASM) model for visualizing program execution, memory allocation, stack and heap.