Data Structures, Abstract Data Types, and Algorithm Analysis

Fundamental Data Structures: Arrays & Object References

• An array is a sequenced, contiguous collection of variables all sharing the exact same data type.

• Each slot or cell in an array is identified by a unique integer position known as an index, which begins at index $0$ and extends to $\text{length} - 1$.

• The values stored within array cells are referred to as elements.

• Array Capacity: The maximum number of elements an array can hold, determined at the time of allocation and remaining fixed throughout its lifecycle.

• In Java, the length of an array named a is accessed via the property a.length.

Array Declaration and Instantiation

• Literal Initialization Syntax:   $\text{elementType}[]\,\text{arrayName} = \{\text{initialValue}_0, \text{initialValue}_1, \dots, \text{initialValue}_{N-1}\};$

• Operator Instantiation Syntax:   $\text{elementType}[]\,\text{arrayName} = \mathbf{new}\,\text{elementType}[\text{length}];$

• Memory for array cells is allocated contiguously in heap memory.

Case Study: Game Entries & High Score Board

• A game high-score collection maintains top scores sorted in descending numerical order.

GameEntry Class Implementation

public class GameEntry {
  private String name; // name of person earning this score
  private int score;   // the score value

  /** Constructs a game entry with given parameters. */
  public GameEntry(String n, int s) {
    name = n;
    score = s;
  }

  /** Returns the name field. */
  public String getName() { return name; }

  /** Returns the score field. */
  public int getScore() { return score; }

  /** Returns a string representation of this entry. */
  public String toString() {
    return "(" + name + ", " + score + ")";
  }
}

Scoreboard Class Implementation

public class Scoreboard {
  private int numEntries = 0;     // number of actual entries
  private GameEntry[] board;      // array of game entries (names & scores)

  /** Constructs an empty scoreboard with given capacity. */
  public Scoreboard(int capacity) {
    board = new GameEntry[capacity];
  }

  /** Attempt to add a new score to the collection (if it is high enough) */
  public void add(GameEntry e) {
    int newScore = e.getScore();
    // is the new entry e really a high score?
    if (numEntries < board.length || newScore > board[numEntries - 1].getScore()) {
      if (numEntries < board.length) {
        numEntries++; // no score drops from the board, so overall number increases
      }
      // shift any lower scores rightward to make room for the new entry
      int j = numEntries - 1;
      while (j > 0 && board[j - 1].getScore() < newScore) {
        board[j] = board[j - 1]; // shift entry from j-1 to j
        j--;                     // and decrement j
      }
      board[j] = e;              // when done, add new entry
    }
  }

  /** Remove and return the high score at index i. */
  public GameEntry remove(int i) throws IndexOutOfBoundsException {
    if (i < 0 || i >= numEntries) {
      throw new IndexOutOfBoundsException("Invalid index: " + i);
    }
    GameEntry temp = board[i]; // save the object to be removed
    for (int j = i; j < numEntries - 1; j++) {
      board[j] = board[j + 1]; // move one cell to the left
    }
    board[numEntries - 1] = null; // null out the old last score
    numEntries--;
    return temp; // return the removed object
  }
}

Object References, Memory Allocation, and Aliasing

• A reference variable holds the memory address location where an object resides, rather than storing the object data inline.

• Default Reference Values:

  • Uninitialized object reference variables defined as instance or class data fields default to null.

  • Local reference variables declared within methods possess no default value and must be explicitly assigned prior to use.

• Trace of Reference Manipulations:

• Step (a): Integer p; Integer q; — Both variables p and q are declared containing uninitialized reference slots.

• Step (b): p = new Integer(5); — Allocates an Integer object with value $5$; reference p points to this instance.

• Step (c): p = new Integer(6); — Allocates a new Integer object with value $6$ and updates p to point to it. The object containing value $5$ becomes unreferenced and eligible for garbage collection.

• Step (d): q = p; — Variable q is assigned the memory reference stored in p. Both p and q now point to the exact same Integer object holding $6$ (aliasing).

• Step (e): q = new Integer(9); — Allocates a distinct Integer object with value $9$ and points q to it; p remains pointing to $6$.

• Step (f): p = null; — Reference p is assigned null. Object holding $6$ loses its reference and becomes candidate for garbage collection.

• Step (g): q = p; — Reference q is set to null (copied from p). Object holding $9$ becomes unreferenced and eligible for garbage collection.

Reference-Based Linked Lists and Memory Dynamics

• A reference-based linked list consists of discrete node objects linked dynamically via pointer references.

• Unlike arrays, linked lists can dynamically grow or shrink in size on demand and do not require contiguous memory blocks or shifting elements during insertions and deletions.

Node Class Definition

• In Java, a singly linked list node is represented as follows:

package List;

class Node {
  Object item;
  Node next;

  Node(Object item) {
    this.item = item;
    this.next = null;
  }

  Node(Object item, Node next) {
    this.item = item;
    this.next = next;
  }
}

Singly Linked List Operations

• A singly linked list is unidirectional; traversal can only proceed sequentially from the head pointer to the end (null).

Displaying Contents / Traversal

• To display all items in a linked list, iterate using a reference variable curr:

for (Node curr = head; curr != null; curr = curr.next) {
    System.out.println(curr.item);
}

Pointer Determination for Sorted Insertion or Deletion

• To locate insertion or deletion points in a sorted linked list, set prev and curr pointers:

for (prev = null, curr = head; 
     (curr != null) && (newValue.compareTo(curr.item) > 0); 
     prev = curr, curr = curr.next) {
    // Iterates until reaching insertion/deletion position
}

Deleting a Node

1. Locate target node curr and preceding node prev.

2. Disconnect target node: prev.next = curr.next;.

3. Clean up deleted node references: curr.next = null; curr = null;.

4. Special Case (Deleting Head Node): head = head.next;.

Inserting a Node

1. Determine position (prev and curr).

2. Create new node: newNode = new Node(item);.

3. Connect references: newNode.next = curr; prev.next = newNode;.

4. Special Case (Inserting at Head): newNode.next = head; head = newNode;.

Linked List Variations: Tail Pointers, Circular Lists, Dummy Nodes, and Doubly Linked Lists

Tail References

• Maintaining an explicit tail pointer referencing the final node in the list allows constant time $O(1)$ append operations at the end.

• Append Execution: tail.next = new Node(request, null); tail = tail.next;.

Circular Linked Lists

• In a circular linked list, the final node's next pointer references the first node (head) instead of storing null.

• Every node in the circular chain has a defined successor.

Dummy Head Nodes

• A dummy head node (or sentinel node) is a permanent placeholder node placed at index $-1$ that precedes the first actual data node.

• It is present even when the list is empty.

• It eliminates edge cases during head insertions and deletions by guaranteeing that every data-containing node always has a valid preceding node prev.

Doubly Linked Lists

• Nodes in a doubly linked list contain two pointers: next referencing the successor node, and prev referencing the predecessor node.

• Enables bidirectional traversal across the linear structure.

Abstract Data Types: List Collections

• A list is a linear collection that offers greater flexibility than strict stacks or queues, allowing insertion, access, and deletion at either end or at any intermediate point.

Three Primary Types of List Collections

1. Ordered Lists:

   • Elements are sorted automatically based on an inherent characteristic (e.g., names in alphabetical order, scores in ascending numeric order).

   • The elements themselves determine their precise location within the list.

2. Unordered Lists:

   • Elements maintain a specific sequence, but this order is not dictated by element characteristics.

   • The user or program determines position explicitly by inserting at the front, rear, or directly after an existing element.

3. Indexed Lists:

   • Elements are referenced directly by a zero-based numeric index position.

   • Index positions are recalculated and updated automatically whenever elements are added or removed.

Lists in the Java Collections Framework (Java API)

• The Java API supports indexed and unordered list abstractions primarily through the List<E> interface, implemented by ArrayList<E> and LinkedList<E>.

• The standard Java API does not provide a direct class implementing an ordered list ADT out of the box.

• LinkedList<E> Constructors & Key Methods:

  • LinkedList(): Constructs an empty list.

  • LinkedList(Collection<? extends E> c): Constructs a list containing elements of the specified collection in iteration order.

  • add(E e) / addLast(E e): Appends specified element to the end of the list.

  • add(int index, E element): Inserts element at specified index position.

  • addFirst(E e): Inserts element at beginning of the list.

  • clear(): Removes all elements from the list.

  • get(int index): Returns element at specified index position.

  • getFirst() / getLast(): Returns first / last element in the list.

  • indexOf(Object o): Returns index of first occurrence of specified object, or $-1$ if not found.

  • remove() / removeFirst(): Retrieves and removes first element from the list.

  • remove(int index): Removes element at specified index position.

  • removeLast(): Removes and returns final element in the list.

  • iterator(): Returns an Iterator<E> object to traverse list elements sequentially (hasNext() tests for remaining items; next() retrieves the subsequent item).

The Queue ADT: Operations, Implementations, and Applications

• A Queue is an Abstract Data Type that enforces a First-In, First-Out (FIFO) processing order.

• Elements are added at the rear (back) and removed from the front.

Queue Interface Operations

• Primary Operations:

  • enqueue(object): Inserts an element at the rear of the queue.

  • object dequeue(): Removes and returns the element at the front of the queue.

• Auxiliary Operations:

  • object peek() / first(): Returns the front element without removing it.

  • integer size(): Returns the count of elements currently stored.

  • boolean isEmpty(): Returns true if empty, false otherwise.

• Boundary Conditions: Calling dequeue() or peek() on an empty queue returns null or raises an exception.

Example Operation Sequence

Applications of Queues

• Direct Applications: Print job queues, customer waiting lists, operating system task scheduling, shared resource access.

• Indirect Applications: Breadth-first search algorithms, buffering data streams, components in complex data structures.

Queue Implementations

Naive Array Queue vs. Circular Array Queue

• A naive array implementation shifts the front index rightward during deletions, resulting in "rightward drift" where array slots at lower indices become unusable, making a non-full queue appear prematurely full.

• Circular Array Strategy: Uses an array of size $N$ combined with modular arithmetic.

  • f: Index of the front element.

  • sz: Current total count of stored elements.

  • The index r for inserting a new element is computed as:     $r = (f + sz) \bmod N$

Java Circular Array Queue Implementation (ArrayQueue<E>)

/** Implementation of the queue ADT using a fixed-length array. */
public class ArrayQueue<E> implements Queue<E> {
  private E[] data;      // generic array used for storage
  private int f = 0;     // index of the front element
  private int sz = 0;    // current number of elements
  public static final int CAPACITY = 1000;

  public ArrayQueue() { this(CAPACITY); }

  @SuppressWarnings("unchecked")
  public ArrayQueue(int capacity) {
    data = (E[]) new Object[capacity]; // safe cast; compiler may give warning
  }

  public int size() { return sz; }
  public boolean isEmpty() { return (sz == 0); }

  /** Inserts an element at the rear of the queue. */
  public void enqueue(E e) throws IllegalStateException {
    if (sz == data.length) throw new IllegalStateException("Queue is full");
    int avail = (f + sz) % data.length; // use modular arithmetic
    data[avail] = e;
    sz++;
  }

  /** Returns, but does not remove, the first element of the queue (null if empty). */
  public E first() {
    if (isEmpty()) return null;
    return data[f];
  }

  /** Removes and returns the first element of the queue (null if empty). */
  public E dequeue() {
    if (isEmpty()) return null;
    E answer = data[f];
    data[f] = null; // dereference to help garbage collection
    f = (f + 1) % data.length;
    sz--;
    return answer;
  }
}

Reference-Based Queue Implementation

• Uses a singly linked list maintaining two pointers: firstNode pointing to the front node, and lastNode pointing to the rear node.

• enqueue(o) attaches new nodes after lastNode in $O(1)$ time.

• dequeue() removes nodes from firstNode in $O(1)$ time.

The Stack ADT: Operations, Implementations, and Applications

• A Stack is an Abstract Data Type operating under a Last-In, First-Out (LIFO) protocol.

• Analogous to a spring-loaded cafeteria plate dispenser where the last item pushed onto the stack is the first item popped off.

Stack Operations

• Primary Operations:

  • push(object): Inserts an element onto the top of the stack.

  • object pop(): Removes and returns the top element from the stack.

• Auxiliary Operations:

  • object top() / peek(): Returns the top element without removing it.

  • integer size(): Returns the number of elements contained.

  • boolean isEmpty(): Indicates whether the stack contains zero elements.

Stack Operations Trace

Stack Implementations

Array-Based Stack

• Uses an array S and an integer index variable t representing the top index (initialized to $-1$ when empty).

• Algorithm Push:

  if t == S.length - 1 then throw Exception
  t = t + 1
  S[t] = o
  ```
- **Algorithm Pop**:

text if isEmpty() then return null o = S[t] S[t] = null t = t - 1 return o   ```

• Performance: Each operation runs in constant time $O(1)$. Space used is $O(n)$.

• Limitation: Fixed capacity allocated upfront; pushing to a full array stack causes overflow.

Reference-Based Stack

• Uses a singly linked list where a single external reference top points to the head node.

• push inserts a new node at the head (head = new Node(o, head)).

• pop removes the node at the head (o = head.item; head = head.next; return o).

• Provides unlimited dynamic capacity limited only by available memory.

Stack Applications

• Direct Applications: Web browser page history back-tracking, text editor undo history chains, Java Virtual Machine (JVM) method execution stack frames.

• Indirect Applications: Expression parsing, depth-first search, compiler syntax parsing.

Expression Conversion and Evaluation using Stacks

Infix to Postfix Conversion

• In an infix expression, operators sit between operands (e.g., $a - b$).

• In a postfix expression, operators follow their operands (e.g., $a\,b\,-$).

• Conversion Rules:

  1. Operands retain their exact original order.

  2. Operators move to the right of their respective operands based on precedence.

  3. All explicit parentheses are removed in postfix form.

Conversion Algorithm Pseudocode

create empty stack to hold Strings / characters
postfix = ""
for next token from infix:
    if token is an operand (not "+", "-", "*", "/", "(", or ")") then
        append token to postfix
    else if token is "(" then
        push "(" onto stack
    else if token is ")" then
        while top of stack is not "(" do
            pop operator from stack and append to postfix
        pop the "(" off the stack
    else // token is an operator
        while stack is not empty and top of stack is operator of equal or greater precedence than token and top is not "(" do
            pop operator from stack and append to postfix
        push token onto stack

while stack is not empty do
    pop remaining operator from stack and append to postfix

Complete Conversion Trace: a - (b + c * d) / e

Postfix Expression Evaluation Algorithm

• Operands are pushed onto a stack when encountered.

• When an operator is encountered, pop the top two operands: operand2 = pop(), operand1 = pop(), apply operation result = operand1 op operand2, and push result back onto stack.

Evaluation Trace for Infix 2 * (3 + 4) (Postfix 2 3 4 + *)

• Final expression evaluation result = $14$.

Fundamentals of Algorithm Analysis

• Algorithm analysis measures resource efficiency, focusing primarily on CPU running time and memory space relative to problem size $n$.

Defining Problem Size $n$

• Searching: Size of search space pool.

• Sorting: Total number of items to sort.

• Text processing: Number of characters in string.

• Dishwashing Example:

  • Problem size $n$: Total dishes to wash.

  • Linear Strategy: Washing = $30\,\text{sec}$, Drying = $30\,\text{sec}$. Total time per dish = $60\,\text{sec}$.     $\text{time}(n) = n\,\text{minutes} = O(n)$

  • Inefficient Quadratic Strategy: Re-dry all previously washed dishes after washing each new dish.     $\text{time}(n) = n \times (30\,\text{seconds wash time}) + \sum_{i=1}^{n} (i \times 30)$     $\text{time}(n) = 30n + \frac{30n(n+1)}{2} = 15n^2 + 45n\,\text{seconds}$

Dishwashing Time Analysis Table

Empirical (Experimental) Studies vs. Theoretical Analysis

• Empirical Studies:

  • Involves writing fully runnable implementations, executing them over varying input sizes $n$, measuring elapsed wall-clock time (System.currentTimeMillis()), and plotting results.

  long startTime = System.currentTimeMillis();
  /* (run the algorithm) */
  long endTime = System.currentTimeMillis();
  long elapsed = endTime - startTime;
  ```

  - **Limitations**: Requires complete implementation effort; results vary across different hardware/software environments; limited to test inputs used.
- **Theoretical Analysis**:
  - Evaluates high-level pseudocode independent of hardware/software environments.
  - Bounds running time mathematically as a function of problem size $n$ across all possible inputs.

# Mathematical Analysis & Primitive Operation Counting

## RAM Model & Primitive Operations

- Calculations assume the Random Access Machine (RAM) model where primitive operations take constant time $O(1)$.
- Primitive operations include:
  - Assigning a value to a variable.
  - Evaluating a arithmetic expression or boolean conditional.
  - Comparing two numerical values.
  - Indexing into an array cell.
  - Calling a method.
  - Returning from a method.

## Detailed Operation Count Analysis (`arrayMax`)

java public static double arrayMax(double[] data) { int n = data.length; // 2 operations (array length, assignment) double currentMax = data[0]; // 2 operations (indexing, assignment) for (int j = 1; j < n; j++) { // 2 + 2n operations (init, loop comparisons, increments) if (data[j] > currentMax) { // 2(n - 1) operations (indexing, comparison) currentMax = data[j]; // 0 to 2(n - 1) operations (conditional assignment) } } return currentMax; // 1 operation }

- **Worst-Case Count**: $5n + 5$ primitive operations.
- **Best-Case Count**: $4n + 5$ primitive operations.
- Bounded by linear growth: Let $a$ be time of fastest operation and $b$ be time of slowest operation:
  $a(4n + 5) \le T(n) \le b(5n + 5)$

# Asymptotic Notations: Big-O, Big-Omega, and Big-Theta

![Display of growth of functions commonly used in big-O estimates](https://assets.knowt.com/pdf-flow-prod/5244169f-7095-452c-9d84-50db9341ff31-figures/23.jpg)

## Formal Definitions

1. **Big-O Notation ($O$ - Upper Bound / Worst-Case)**:
   $f(n) \text{ is } O(g(n)) \iff \exists\, c > 0, n_0 \ge 1 \text{ such that } f(n) \le c \cdot g(n) \quad \forall n \ge n_0$

![Big-O notation plot showing f(n) bounded above by c*g(n)](https://assets.knowt.com/pdf-flow-prod/5244169f-7095-452c-9d84-50db9341ff31-figures/29.jpg)

2. **Big-Omega Notation ($\Omega$ - Lower Bound / Best-Case)**:
   $f(n) \text{ is } \Omega(g(n)) \iff \exists\, c > 0, n_0 \ge 1 \text{ such that } f(n) \ge c \cdot g(n) \quad \forall n \ge n_0$

![Big-Omega notation plot showing f(n) bounded below by c*g(n)](https://assets.knowt.com/pdf-flow-prod/5244169f-7095-452c-9d84-50db9341ff31-figures/30.jpg)

3. **Big-Theta Notation ($\Theta$ - Tight Bound / Average-Case)**:
   $f(n) \text{ is } \Theta(g(n)) \iff \exists\, c' > 0, c'' > 0, n_0 \ge 1 \text{ such that } c' \cdot g(n) \le f(n) \le c'' \cdot g(n) \quad \forall n \ge n_0$

![Big-Theta notation plot showing f(n) bounded between c1*g(n) and c2*g(n)](https://assets.knowt.com/pdf-flow-prod/5244169f-7095-452c-9d84-50db9341ff31-figures/31.jpg)

## Mathematical Proofs for Big-O Bounding

- **Proof 1**: Show $2n + 10$ is $O(n)$.
  - Set inequality: $2n + 10 \le c \cdot n \implies (c - 2)n \ge 10 \implies n \ge \frac{10}{c - 2}$.
  - Select constant $c = 3$, giving $n_0 = 10$. For all $n \ge 10$, $2n + 10 \le 3n$. Thus $2n + 10$ is $O(n)$.
- **Proof 2**: Prove $n^2$ is **not** $O(n)$.
  - Assume $n^2 \le c \cdot n \implies n \le c$. This contradicts the condition that $c$ is a fixed constant across arbitrary $n \ge n_0$. Thus $n^2$ is not $O(n)$.
- **Proof 3**: Show $7n - 2$ is $O(n)$.
  - Satisfied for $c = 7$ and $n_0 = 1$ ($7n - 2 \le 7n$).
- **Proof 4**: Show $3 \log(n) + 5$ is $O(\log(n))$.
  - Satisfied for $c = 8$ and $n_0 = 2$ ($3 \log(n) + 5 \le 8 \log(n)$ for $n \ge 2$).

# Analyzing Code Constructs & Growth Function Comparisons

## Seven Critical Growth Functions

| Function Label | Mathematical Form | Growth Category |
| :--- | :--- | :--- |
| Constant | $1$ / $17$ | $O(1)$ |
| Logarithmic | $\log(n)$ | $O(\log(n))$ |
| Linear | $n$ / $20n - 4$ | $O(n)$ |
| N-Log-N | $n \log(n)$ | $O(n \log(n))$ |
| Quadratic | $n^2$ / $3n^2 + 5n - 2$ | $O(n^2)$ |
| Cubic | $n^3$ / $8n^3 + 3n^2$ | $O(n^3)$ |
| Exponential | $2^n$ | $O(2^n)$ |

### Values of Seven Core Functions across Input Sizes

| $n$ | $\log_2(n)$ | $n$ | $n \log_2(n)$ | $n^2$ | $n^3$ | $2^n$ |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| $8$ | $3$ | $8$ | $24$ | $64$ | $512$ | $256$ |
| $16$ | $4$ | $16$ | $64$ | $256$ | $4,096$ | $65,536$ |
| $32$ | $5$ | $32$ | $160$ | $1,024$ | $32,768$ | $4,294,967,296$ |
| $64$ | $6$ | $64$ | $384$ | $4,096$ | $262,144$ | $1.84 \times 10^{19}$ |
| $128$ | $7$ | $128$ | $896$ | $16,384$ | $2,097,152$ | $3.40 \times 10^{38}$ |
| $256$ | $8$ | $256$ | $2,048$ | $65,536$ | $16,777,216$ | $1.15 \times 10^{77}$ |
| $512$ | $9$ | $512$ | $4,608$ | $262,144$ | $134,217,728$ | $1.34 \times 10^{154}$ |

## Practical Sorting Efficiency: Insertion Sort vs. Merge Sort

- Insertion Sort running time: $T(n) = \frac{n^2}{4}$.
- Merge Sort running time: $T(n) = 2n \log_2(n)$.
- **Sorting 1,000,000 items**:
  - Insertion Sort requires $\approx 70\,\text{hours}$.
  - Merge Sort requires $\approx 40\,\text{seconds}$.
- **On a $100\times$ Faster Processor**:
  - Insertion Sort requires $\approx 40\,\text{minutes}$.
  - Merge Sort requires $< 0.5\,\text{seconds}$.
- Conclusion: Hardware speedups cannot compensate for poor asymptotic growth complexity ($O(n^2)$ vs $O(n \log(n))$).

## Impact of Processor Speedup ($10\times$ Processor Speedup)

| Algorithm | Time Complexity | Max Problem Size Before Speedup | Max Problem Size After $10\times$ Speedup |
| :--- | :--- | :--- | :--- |
| A | $n$ | $s_1$ | $10 s_1$ |
| B | $n^2$ | $s_2$ | $\sqrt{10} s_2 \approx 3.16 s_2$ |
| C | $n^3$ | $s_3$ | $\sqrt[3]{10} s_3 \approx 2.15 s_3$ |
| D | $2^n$ | $s_4$ | $s_4 + \log_2(10) \approx s_4 + 3.3$ |

## Rules for Code Complexity Analysis

1. **Single Loops**:

java for (int count = 0; count < n; count++) { // sequence of O(1) steps }    ```    $n \text{ iterations} \times O(1) = O(n)$.

2. Logarithmic Loops:

   count = 1;
   while (count < n) {
       count *= 2;
       // sequence of O(1) steps
   }
&nbsp;&nbsp;&nbsp;```
&nbsp;&nbsp;&nbsp;Loop executes $\log_2(n)$ times $\implies O(\log(n))$.

3. **Nested Loops**:

java for (int count = 0; count < n; count++) { for (int count2 = 1; count2 < n; count2 *= 2) { System.out.println(count + ", " + count2); } }    ```    Outer loop executes $n$ times; inner loop executes $\log_2(n)$ times. Total efficiency = $O(n \log(n))$.

4. Nested Identical Loops: java for (int count = 0; count < n; count++) { for (int count2 = 0; count2 < n; count2++) { // sequence of O(1) steps } } &nbsp;&nbsp;&nbsp;    $$n \text{ iterations} \times n \text{ iterations} = O(n^2)$.

5. Method Calls inside Loops:

   • To determine inner body complexity, multiply loop iteration count by the Big-O complexity of the method called inside.