References, Dereferencing, and Abstract State Machine

• References do not directly store simple values but hold a reference to an object (pointee).
• Dereferencing involves accessing the value of the pointee through a reference variable, using the dot operator (.) to access fields or methods.
• A reference must be assigned a pointee before dereferencing to avoid a NullPointerException.
• Null refers to a reference value that 'points to nothing'.
• Reference assignment using (=) makes two references point to the same pointee.
• Sharing occurs when two references refer to a single pointee, making each reference an alias for the other.
• A shallow copy results in sharing references, while a deep copy creates a new, independent copy.
• Abstract State Machine (ASM) is a theoretical model illustrating memory allocation during program execution.
• ASM includes a workspace for the code currently executing, a stack for temporary storage, and a heap for objects and data structures.
• The initial ASM state has the program in the workspace and empty stack and heap.
• ASM operates by executing the 'next code statement' from the workspace in each step, potentially modifying the stack or heap, and stops when all code statements are executed.
• Primitive values reside in the stack, and reference values are addresses of data in the heap.
• Objects are allocated in the heap, while the binding of a variable and the object's reference are stored in the stack.
• Object construction involves allocating space in the heap, including slots for fields and the class, running the constructor body after parameter pushing, and updating values in the heap based on assignments.
• Linked nodes are a class containing data fields and a reference to another linked node, forming lists by connecting objects.
• Data in linked nodes can be primitive or an object.
• Linked nodes store extensive data without arrays.
• The final node's next field points to a null reference.
• Iteration involves creating a temporary node pointing to the head of the chain and updating the temporary node's pointee with each iteration until it points to null.

Exceptional Circumstances – Failure: Handle Failure

• Conditions not being met for the arguments
• Imprecise Interfaces
• Remove operation not supported
• Opening a file that does not exits
• Resources exhausted
• Program uses up all memory
• Error Value (NaN , null, -1)
• Optional Result (OCaml, options)
• Pass responsibility to caller
• Exceptions: If exception is not caught, program terminates
• OCaml, Java

Exceptions

• Exceptions are objects representing an abnormal termination condition, with internal states describing the issue (e.g., NullPointerException).
• Own exception classes can be defined.
• Throwing an exception is an emergency exit that propagates up the invocation stack until caught or aborts the program.
• Catching an exception allows the caller to perform actions to handle issues using try/catch blocks.
• Checked exceptions are subtypes of 'exceptions' (excluding RuntimeException) and must be declared using a 'throw' clause.
• Raise checked exceptions by directly throwing the exception or calling a method that throws a checked exception.
• Unchecked exceptions are RuntimeException subtypes and do not need declaration via throws.
• Finally clauses in try/catch/finally statements run regardless of exceptions to release resources.

Recursion

• Recursion involves a function invoking itself.
• Base case: solve without recursive call.
• Recursive part: with calls to function
• Recursive call parameters must be closer to base case
• Tracing recursion involves unwinding recursion.

Run-Time Stack and Activation Frames

• New function information is saved to the run-time stack in the form of an activation frame.
• Activation frames store function arguments, local variables, and the return address.
• A new activation frame is pushed onto the stack for each new method call.

Recursive Array Search

• Linear search, Binary search

Set Notation and Relations

• A set consists 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

• A problem is a task to be performed.
• An algorithm is a method or process to solve a problem.
• A program is an instance of an algorithm in a programming language.
• Asymptotic analysis estimates an algorithm's resource consumption.
• The growth rate is the rate at which an algorithm's cost increases with input size.
• The upper bound is a growth rate greater than or equal to the algorithm's actual growth rate.
• Worst case instances have the greatest cost for a given input size n.
• Table

Big-Oh! - Time Complexity

• Bounds vs cases
• Best case vs worst case
• Upper bound vs lower bound

Formalizing growth rate

• Goal: express runtime of algorithm T as function of size of input n
• Input size examples
  • Parsing strings
  • Sorting a collection
  • Searching in a collection
  • Binary exponentiation

Big-Oh

• Upper bound
• Simplifying rule

Space Complexity:

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

Data structure space requirements

• Overhead: 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 nodes based data structures: Overhead is space used by nodes pointers references to 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)

Explanation of references, dereferencing, null values, and sharing in programming. Includes reference assignment, shallow vs. deep copy. Introduces the Abstract State Machine (ASM) model with workspace, stack, and heap concepts.