Data Structures, Algorithms, Memory Layouts, and Heap Analysis

Graph Data Structures and Representations

• Fundamental Definitions:

  • A graph $G$ is mathematically defined as an ordered pair $G = (V, E)$, where $V$ is the set of vertices (also called nodes or points) and $E$ is the set of edges (also called lines or connections).

  • An edge connects two vertices $x$ and $y$. The vertices $x$ and $y$ of an edge $\{x, y\}$ are called the endpoints of the edge.

  • Graphs can contain loops, which are defined as edges that connect a vertex to itself (an edge having the same node twice as its endpoints).

  • A vertex may belong to no edge, existing as an isolated node in $G$.

  • If $V$ is empty, then the graph $G$ is empty.

  • The order of a graph $G$ is denoted by $|V|$, which represents the total number of its vertices.

  • The quantity $|E|$ represents the total number of edges in $G$.

  • The overall size of a graph $G$ is defined as the sum $|V| + |E|$.

  • Two vertices $x$ and $y$ are adjacent if $\{x, y\}$ is an edge in $E$.

• Directed vs. Undirected Graphs:

  • Undirected Graphs: Edges have no orientation. An edge $\{x, y\}$ connects $x$ and $y$ symmetrically.

  • Directed Graphs: Edges possess direction. If an edge connects $x$ and $y$, vertex $x$ is called the tail of the edge and vertex $y$ is called the head of the edge. The edge is said to join $x$ and $y$, or be incident on $x$ and incident on y$.\n\n* **Adjacency-List Representation**:\n * Consists of an array Adj$of$|V|$lists, with one list for each vertex$u \in V.\n * For each vertex u \in V$, the adjacency list$Adj[u]$contains all vertices$v$such that there is an edge in$E$connecting$u$to$v.\n * Adj[u]$consists of all vertices adjacent to$u$in$G.\n * **Memory Usage**: Requires |V| + |E|$memory space for graph$G.\n * **Search Performance**: Determining whether a given edge (u, v)$is present in$G$requires searching for$v$in the list$Adj[u], which is slower than matrix lookup.\n * **Weighted Graphs**: For graphs where each edge has an associated weight given by a weight function w: E \rightarrow \mathbb{R}$, the weight$w(u, v)$of edge$(u, v) \in E$is stored directly with vertex$v$in$u's adjacency list.\n\n* **Adjacency-Matrix Representation**:\n * Consists of an n \times n$square matrix$A = (A_{ij})$, where$n = |V|.\n * The matrix element A_{ij}$specifies the number of connections from vertex$i$to vertex$j.\n * For an undirected graph G$, the adjacency matrix is symmetric, meaning$A_{ij} = A_{ji}.\n * **Memory Usage**: Requires |V| \times |V|$(or$|V|^2) memory space.\n * **Search Performance**: Checking for edge existence takes O(1)$constant time by looking up$A_{uv}, but at the cost of higher memory consumption.\n\n* **Concrete Representation Examples**:\n * **Undirected Graph Example**: An undirected graph G$with$5$vertices and$7 edges.\n * Vertices: {1, 2, 3, 4, 5}.\n * Adjacency-List Representation:\n * 1 \rightarrow 2 \rightarrow 5\n * 2 \rightarrow 1 \rightarrow 5 \rightarrow 3 \rightarrow 4\n * 3 \rightarrow 2 \rightarrow 4\n * 4 \rightarrow 2 \rightarrow 5 \rightarrow 3\n * 5 \rightarrow 4 \rightarrow 1 \rightarrow 2\n * Adjacency-Matrix Representation:\n * Row 1$:$[0, 1, 0, 0, 1]\n * Row 2$:$[1, 0, 1, 1, 1]\n * Row 3$:$[0, 1, 0, 1, 0]\n * Row 4$:$[0, 1, 1, 0, 1]\n * Row 5$:$[1, 1, 0, 1, 0]\n * **Directed Graph Example**: A directed graph G$with$6$vertices and$8 edges.\n * Vertices: {1, 2, 3, 4, 5, 6}.\n * Adjacency-List Representation:\n * 1 \rightarrow 2 \rightarrow 4\n * 2 \rightarrow 5\n * 3 \rightarrow 6 \rightarrow 5\n * 4 \rightarrow 2\n * 5 \rightarrow 4\n * 6 \rightarrow 6\n * Adjacency-Matrix Representation:\n * Row 1$:$[0, 1, 0, 1, 0, 0]\n * Row 2$:$[0, 0, 0, 0, 1, 0]\n * Row 3$:$[0, 0, 0, 0, 1, 1]\n * Row 4$:$[0, 1, 0, 0, 0, 0]\n * Row 5$:$[0, 0, 0, 1, 0, 0]\n * Row 6$:$[0, 0, 0, 0, 0, 1]\n\n# Binary Operations and Bit Masking\n\n* **Bitwise Operations and Truth Tables**:\n * **Bitwise OR (|$)**: Evaluates to$1$if either operand is$1.\n * Rules: A | 1 \implies 1$,$A | 0 \implies A\n * **Bitwise AND ($\&$)**: Evaluates to 1$if both operands are$1.\n * Rules: A \& 1 \implies A$,$A \& 0 \implies 0\n * **Bitwise XOR (\hat{\ }$)**: Evaluates to$1 if operands are different.\n * Rules: A \hat{\ } 1 \implies \sim A$(flips bit$A$),$A \hat{\ } 0 \implies A\n * **Complete Truth Table**:\n * Input (A=1, B=0)$:$A|B = 1$,$A\&B = 0$,$A \hat{\ } B = 1\n * Input (A=0, B=0)$:$A|B = 0$,$A\&B = 0$,$A \hat{\ } B = 0\n * Input (A=1, B=1)$:$A|B = 1$,$A\&B = 1$,$A \hat{\ } B = 0\n * Input (A=0, B=1)$:$A|B = 1$,$A\&B = 0$,$A \hat{\ } B = 1\n\n* **Bit Masking and Integer Representation**:\n * Decimal 15$in binary representation format is$00001111_2 (base-2).\n * Decimal 15$is equal to$\text{0x0F} in hexadecimal format (base-16).\n * **Nibble**: A 4\text{-bit} aggregation or half an octet. It is also termed a half-byte or semi-octet.\n * A single hexadecimal digit (0\text{--}\text{F}, called a hex digit) represents exactly one nibble.\n * **High Nibble**: Contains the more significant bits of a byte. For decimal 15$($00001111_2$),$0000_2$corresponding to$\text{0x0} is the high nibble.\n * **Low Nibble**: Contains the less significant bits of a byte. For decimal 15$($00001111_2$),$1111_2$corresponding to$\text{0xF} is the low nibble.\n\n# Abstract Data Types: Stacks and Queues\n\n* **The Stack Abstract Data Type**:\n * **LIFO Model**: Last-In, First-Out dynamic set where the element deleted from the set is the one most recently inserted.\n * Attributes: Has a top pointer (`S.top`), a base pointer, a length, and a maximum value for length n.\n * **Stack API**:\n * `PUSH(S, x)`: Takes stack S$and element$x$. No return value. Side effect:$x$stored at top of$S, and `S.top` is incremented.\n * `POP(S)`: Takes stack S. Returns the value stored at `S.top`, and `S.top` is decremented.\n * `STACK-EMPTY(S)`: Returns `True` if S is empty (`S.top == 0`), otherwise returns `False`.\n * **Array Implementation**:\n * Implemented using an array A[1..n]$storing at most$n elements.\n * Attribute `S.top` indexes the most recently inserted element.\n * Stack consists of elements S[1..S.\text{top}].\n * S[1]$is the element at the bottom of the stack, and$S[S.\text{top}] is the element at the top.\n * When `S.top == 0`, the stack contains no elements and is empty.\n * **Underflow**: Occurs when attempting to pop an empty stack (`S.top == 0`).\n * **Overflow**: Occurs when attempting to push onto a full stack (`S.top == n`).\n * **Execution Walkthrough Example**:\n * (a) Stack S$has$4$elements$[15, 6, 2, 9]$. Top element is$9, `S.top = 4`.\n * (b) Stack S$after calling `PUSH(S, 17)` and `PUSH(S, 3)` contains$[15, 6, 2, 9, 17, 3], `S.top = 6`.\n * (c) Stack S$after call `POP(S)` returns element$3$(most recently pushed). Although element$3$still physically appears in array index$6$, it is no longer in the stack; top element is$17, `S.top = 5`.\n * **Time Complexity**: All stack operations (`PUSH`, `POP`, `STACK-EMPTY`) run in O(1) constant time.\n\n* **The Queue Abstract Data Type**:\n * **FIFO Model**: First-In, First-Out dynamic set where the element deleted is the one that has been in the set the longest.\n * Attributes: Has a tail pointer (`Q.tail`), a head pointer (`Q.head`), and a length (`Q.length`).\n * **Queue API**:\n * `ENQUEUE(Q, x)`: Takes queue Q$and element$x$. No return value. Side effect:$x$stored at tail of$Q$. Tail pointer is incremented by$1 (wrapping around if necessary).\n * `DEQUEUE(Q)`: Takes queue Q$. Returns the value stored at head. Head pointer is incremented by$1 (wrapping around if necessary).\n * **Array Implementation Algorithms**:\n * Implemented using array Q[1..n]$(e.g.,$Q[1..12]).\n * `ENQUEUE(Q, x)` algorithm:\n 1. `Q[Q.tail] = x`\n 2. `if Q.tail == Q.length`\n 3. ` Q.tail = 1`\n 4. `else Q.tail = Q.tail + 1`\n * `DEQUEUE(Q)` algorithm:\n 1. `x = Q[Q.head]`\n 2. `if Q.head == Q.length`\n 3. ` Q.head = 1`\n 4. `else Q.head = Q.head + 1`\n 5. `return x`\n * **Time Complexity**: All queue operations (`ENQUEUE`, `DEQUEUE`) run in O(1) constant time.\n\n# Array Memory Layouts, Multi-Dimensional Arrays, and Sparse Matrices\n\n* **Multi-Dimensional Array Access Patterns**:\n * **Row-Major Order**:\n * Mapping function maps base address and indices to memory address.\n * Elements of row 0$listed in order from left to right, followed by elements of row$1$, row$2, etc.\n * If the array is a matrix, it is stored by rows.\n * **Column-Major Order**:\n * Mapping function obtains offset by evaluating j \times r + i$, requiring one multiplication and one addition (where$r$is row size,$i$is row index,$j is column index).\n * If the array is a matrix, it is stored by columns.\n * **General Element Locating Formula**:\n * \text{Address}(\text{Array}[i, j]) = \text{Base Address} + ((\text{Rows above}) \times \text{Row size} + \text{Elements to left}) \times \text{Element size}\n * Formal layout: \text{Address}([i, j]) = \text{Base}([0, 0]) + (((i - \text{low}_1) \times \text{size}_2) + (j - \text{low}_2)) \times \text{element_size}\n * **Three-Dimensional Array Indexing Example**:\n * Matrix size Z[100, 100, 100].\n * First element of first column in first matrix: Z[1, 1, 1].\n * The first 100$elements of$h$are stored under the first column in matrix$1$of$Z[:, 1, 1].\n * First matrix accessed with 3rd index: Z[:, :, 1]$, up to$Z[:, :, 100].\n\n* **Arrays of Arrays Implementation**:\n * **C Language Code Structure**:\n * Array declarations:\n * `int a[6] = {20, 6, 6, 20, 14, 7};`\n * `int b[6] = {11, 22, 120, 1, 8};` (last element uninitialized, defaults to 0)\n * `int c[6] = {0};` (all elements initialized to 0)\n * Pointer-array declaration: `int* TwoD1[3] = {a, b, c};`\n * Fixed 2D array declaration: `int TwoD2[3][6];`\n * Iterative copy assignment: `TwoD2[i][j] = TwoD1[i][j]`\n * Data sizes: `sizeof(int*)` evaluates to pointer size (e.g., 8\,\text{bytes}$on 64-bit systems), whereas `sizeof(int)` evaluates to$4\,\text{bytes}.\n * **Java Language Code Structure**:\n * Array declarations:\n * `int[] a = {20, 6, 6, 20, 14, 7};`\n * `int[] b = {11, 22, 120, 1, 8, 0};` (padded to match size)\n * `int[] c = {0, 0, 0, 0, 0, 0};`\n * Pointer-array equivalent: `int[][] TwoD1 = {a, b, c};` (array of references to 1D arrays)\n * Fixed size allocation: `int[][] TwoD2 = new int[3][6];`\n * Memory estimation: Primitive `int` is 4\,\text{bytes}; array references estimated using `Integer.BYTES * 6`.\n\n* **Rectangular vs. Irregular (Jagged) Arrays**:\n * **Rectangular Array**: A multi-dimensional array in which all rows have identical numbers of elements, and all columns have identical numbers of elements.\n * **Jagged (Irregular) Array**: An array in which two or more rows have different numbers of elements, represented physically via an array of arrays.\n * **Language Support**:\n * C, C++, and Java support jagged arrays.\n * C# supports both rectangular arrays and jagged arrays.\n\n* **Array Slices**:\n * A slice is a substructure of an array; it acts strictly as a referencing mechanism.\n * Slices are useful in languages that provide native built-in array operations.\n * **Python Examples**:\n * `vector = [2, 4, 6, 8, 10, 12, 14, 16]`\n * `vector[3:6]` creates a three-element array `[8, 10, 12]`.\n * `mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]`\n * `mat[0][0:2]` selects the first and second elements of the first row of `mat` (`[1, 2]`).\n\n* **Sparse Matrices**:\n * Sparse matrices store non-zero elements only, skipping zero entries to conserve memory.\n * **Representation Method 1 (Coordinate Format)**:\n * Uses a struct containing row, column, and value:\n * `struct Element { int row; int col; int val; };`\n * `struct Element sparse[10];`\n * Assignment: `e1.row = 0; e1.col = 0; e1.val = 1; sparse[0] = e1;`\n * **Representation Method 2 (Column-Value Format)**:\n * Uses a struct containing column and value:\n * `struct Element { int col; int val; };`\n * `struct Element sparse[5];`\n\n# Heap Data Structure, Heapsort, and Priority Queues\n\n* **The Binary Heap Data Structure**:\n * A binary heap is an array object A that can be viewed as a nearly complete binary tree.\n * Each node of the tree corresponds to an element of array A\n * The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point.\n * Heap Object Attributes:\n * `A.length`: Gives the total number of elements in array A\n * `A.heap-size`: Represents how many valid elements of the heap are stored within array A\n * A[1..A.\text{length}]$may contain numbers, but only elements in$A[1..A.\text{heap-size}]$are valid heap elements ($0 \le A.\text{heap-size} \le A.\text{length}).\n * Element Requirements: Element types must allow a total ordering comparison, and elements must be at least ordinal 1$.

  • Root of the tree is stored at index $A[1]$.

• Bitwise Arithmetic for Heap Index Navigation:

  • PARENT(i): Computes $\lfloor i/2 \rfloor$ by shifting binary representation of $i$ right by $1$ bit position (divides by $2$ and takes floor).

  • LEFT(i): Computes $2i$ by shifting binary representation of $i$ left by $1$ bit position.

  • RIGHT(i): Computes $2i + 1$ by shifting binary representation of $i$ left by $1$ bit position and setting low-order bit to 1$.\n\n* **Max-Heaps vs. Min-Heaps**:\n * **Max-Heap Property**: For every node i other than the root:\n * A[\text{PARENT}(i)] \ge A[i]\n * Value of a node is at most the value of its parent.\n * Largest element in a max-heap is stored at the root (A[1]).\n * Subtree rooted at a node has values no larger than that contained at the node itself.\n * **Min-Heap Property**: For every node i other than the root:\n * A[\text{PARENT}(i)] \le A[i]\n * Smallest element in a min-heap is stored at the root (A[1]).\n * **Height Definitions**:\n * Height of a node in a heap: The number of edges on the longest simple downward path from the node to a leaf.\n * Height of a heap: Height of its root, equal to \lfloor \log_2(n) \rfloor$for an$n\text{-element} heap.\n * Basic operations on heaps run in time at most proportional to height of heap: O(\log_2(n)).\n\n* **Maintaining the Max-Heap Property (`MAX-HEAPIFY`)**:\n * Key procedure to maintain max-heap property, running in O(\log_2(n)) time (proportional to heap height).\n * Inputs: Array A$and index$i\n * Precondition: Assumes binary trees rooted at `LEFT(i)` and `RIGHT(i)` are max-heaps, but A[i] might be smaller than its children, violating the max-heap property.\n * Logic: Lets value at A[i]$"float down" in max-heap so subtree rooted at$i satisfies max-heap property.\n * Step-by-step Execution:\n 1. Determine largest of A[i]$,$A[\text{LEFT}(i)]$, and$A[\text{RIGHT}(i)], storing its index in `largest`.\n 2. If A[i]$is `largest`, subtree rooted at node$i is already a max-heap; procedure terminates.\n 3. Otherwise, one child contains `largest`; exchange A[i]$with$A[\text{largest}].\n 4. Call `MAX-HEAPIFY(A, largest)` recursively on affected subtree.\n * **Pseudo-code**:\n ```\n MAX-HEAPIFY(A, i)\n 1 l = LEFT(i)\n 2 r = RIGHT(i)\n 3 if l <= A.heap-size and A[l] > A[i]\n 4 largest = l\n 5 else largest = i\n 6 if r <= A.heap-size and A[r] > A[largest]\n 7 largest = r\n 8 if largest != i\n 9 exchange A[i] with A[largest]\n 10 MAX-HEAPIFY(A, largest)\n    ```\n * Trace Example: `MAX-HEAPIFY(A, 2)` with `A.heap-size = 10`. Node 2$($A[2] = 4$) violates property. Exchanged with$A[4] = 14$. Recursive call `MAX-HEAPIFY(A, 4)` swaps$A[4]$with$A[9] = 8, restoring heap property.\n\n* **Building a Heap (`BUILD-MAX-HEAP`)**:\n * Produces a max-heap from an unordered input array A\n * Subarray elements A[\lfloor n/2 \rfloor + 1 \dots n] are all leaves of the tree (each is a 1-element heap to begin with).\n * Procedure iterates through remaining nodes from \lfloor A.\text{length}/2 \rfloor$downto$1, executing `MAX-HEAPIFY(A, i)` on each node.\n * **Pseudo-code**:\n ```\n BUILD-MAX-HEAP(A)\n 1 A.heap-size = A.length\n 2 for i = floor(A.length / 2) downto 1\n 3 MAX-HEAPIFY(A, i)\n    ```\n * Trace Example: Input array A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]$with$A.\text{length} = 10$. Loop starts at$i = 5$(`MAX-HEAPIFY(A, 5)`), progressing through$i = 4, 3, 2, 1$to produce max-heap$A = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1].\n * **Time Complexity**: Runs in linear time O(n).\n\n* **The Heapsort Algorithm**:\n * `HEAPSORT(A)` sorts array A in place.\n * Worst-case running time is proportional to n \log_2(n)$(asymptotic upper bound$O(n \log_2(n))).\n * Sorts in place: Only a constant number of array elements are stored outside input array at any time.\n\n* **Max-Priority Queues**:\n * Abstract Data Type for maintaining a set S of elements, each with an associated value called a key.\n * **Supported API Operations**:\n * `INSERT(S, x)`: Inserts element x$into set$S$($S = S \cup {x}).\n * `MAXIMUM(S)`: Returns element of S with largest key.\n * `EXTRACT-MAX(S)`: Removes and returns element of S with largest key.\n * `INCREASE-KEY(S, x, k)`: Increases value of element x$'s key to new value$k$(assumed$k \ge \text{current key}).\n * **Real-World Application**: Scheduling jobs on a shared computer.\n * When job finishes or interrupts, scheduler selects highest-priority job using `EXTRACT-MAX`.\n * Scheduler adds new job to queue at any time using `INSERT`.\n * **`HEAP-INCREASE-KEY` Algorithm**:\n * Inputs: Array A$, index$i, new key value `key`.\n * Updates key A[i] = \text{key}.\n * Traverses path toward root, comparing element to parent and exchanging keys if element key is larger.\n * **Pseudo-code**:\n ```\n HEAP-INCREASE-KEY(A, i, key)\n 1 if key < A[i]\n 2 error "new key is smaller than current key"\n 3 A[i] = key\n 4 while i > 1 and A[PARENT(i)] < A[i]\n 5 exchange A[i] with A[PARENT(i)]\n 6 i = PARENT(i)\n      ```\n * Time Complexity: Runs in O(\log_2(n)) time.\n * **`MAX-HEAP-INSERT` Algorithm**:\n * Input: Array A, key of new element.\n * Expands max-heap by adding new leaf with key -\infty (incrementing `A.heap-size`).\n * Calls `HEAP-INCREASE-KEY(A, A.heap-size, key)` to set correct value and maintain max-heap property.\n * Time Complexity: Runs in O(\log_2(n)) time.\n\n# Comprehensive Summary of Data Structures and Operations\n\n* **Abstract Data Types (ADTs)**:\n * Static Set\n * Dynamic Set\n * Stack (LIFO)\n * Queue (FIFO)\n * Priority Queue (Max-Priority Queue)\n* **Concrete Data Structures**:\n * Arrays and Circular Arrays\n * Lists, Circular Lists, and Doubly Linked Lists\n * Trees and Binary Search Trees (BST)\n * Hash Tables (Hash Maps)\n * Heaps (Max-Heap and Min-Heap)\n* **Searching and Sorting Algorithms**:\n * Simple Linear Search\n * Searching a BST\n * Insertion Sort\n * MergeSort\n * Heapsort (O(n \log_2(n))$$ in-place)

• Memory Layouts and Specialized Representations:

  • Sparse Matrices (Coordinate format and Column-value format)

  • Arrays of Arrays and 2-Dimensional Arrays

  • Pointers and Records