This Octave code implements the Quickselect algorithm to efficiently find the k-th smallest element in an unsorted array. It's a selection algorithm that, like Quicksort, uses a partitioning strategy but only recurses on...

The `findKthSmallest` function uses the Quickselect algorithm to find the k-th smallest element in an array. It first performs input validation to ensure `k` is within valid bounds and the array is not empty. The core logic resides in the `quickselectHelper` function, which recursively partitions the array. A `partition` helper function rearranges the sub-array such that elements smaller than a chosen pivot are to its left, and larger elements are to its right. The `quickselectHelper` then determines if the pivot is the k-th element, or if the search should continue in the left or right partition. The average time complexity is O(n), as on average, one partition is discarded in each recursive step. The worst-case time complexity is O(n^2), occurring when the pivot selection consistently leads to highly unbalanced partitions (e.g., always picking the smallest or largest element). The space complexity is O(log n) on average due to recursion depth, and O(n) in the worst case. An invariant is that after `partition` completes, `arr(pivotFinalIndex)` is in its correct sorted position, and all elements before it are smaller, and all elements after it are larger.

function findKthSmallest(arr, k): n = length(arr) if n == 0: error 'empty array' if k < 1 or k > n: error 'invalid k' arrCopy = copy of arr return quickselectHelper(arrCopy, 1, n, k) function quickselectHelper(arr, low,...

This Octave function calculates the factorial of a non-negative integer using a recursive approach. The factorial of a number `n` is the product of all positive integers up to `n`. This recursive implementation is a clas...

The `recursiveFactorial` function computes the factorial of a non-negative integer `n`. It first checks for invalid input: if `n` is negative, it throws an error because the factorial is not defined for negative numbers. The function then defines its base case: if `n` is 0, it returns 1, as 0! is defined as 1. For any positive integer `n`, the function enters the recursive step: it returns `n` multiplied by the result of calling itself with `n-1`. This process continues until the base case (`n=0`) is reached, at which point the results are multiplied back up the call stack. The time complexity is O(n) because the function makes `n` recursive calls. The space complexity is also O(n) due to the call stack depth required to store the intermediate function calls. The invariant is that `recursiveFactorial(k)` correctly computes `k!` for all `k` from `n` down to 0.

function recursiveFactorial(n): if n < 0: error 'Factorial not defined for negative numbers' if n == 0: return 1 else: return n * recursiveFactorial(n - 1)

This Octave code defines a singly linked list data structure using classes. It includes a `Node` class to represent individual elements and a `LinkedList` class to manage the list's operations, such as adding nodes and d...

The code defines two classes: `Node` and `LinkedList`. The `Node` class has properties for `data` and a `next` pointer, which refers to the subsequent node. The `LinkedList` class manages the `head`, `tail`, and `count` of the list. The `addNode` method creates a new `Node` and appends it to the end of the list. If the list is empty, the new node becomes both the `head` and `tail`. Otherwise, the `next` pointer of the current `tail` is updated to point to the new node, and the `tail` is updated. The `displayList` method traverses the list from the `head` to the `tail`, printing the `data` of each node. The `toArray` method converts the list into a standard Octave array. The time complexity for `addNode` is O(1) because it directly manipulates the `tail`. The `displayList` and `toArray` methods have a time complexity of O(n), where n is the number of nodes, as they iterate through the entire list. The space complexity is O(n) to store the nodes. An invariant for `addNode` is that after execution, `obj.tail.next` will point to the newly added node, and `obj.tail` will be that new node.

class Node: properties: data next = null methods: constructor(dataValue): this.data = dataValue class LinkedList: properties: head = null tail = null count = 0 methods: constructor(): initialize head, tail to null, count...

This Octave function sorts an array using the Insertion Sort algorithm, employing a helper function for clarity. It iteratively builds a sorted sub-array by inserting each element from the unsorted portion into its corre...

The `insertionSortWithHelper` function sorts an array by iteratively inserting each element into its correct position within the already sorted portion of the array. The outer loop iterates from the second element (`i = 2`) to the end of the array. For each element `arr(i)`, the `insertElement` helper function is called. This helper takes the element `arr(i)` and finds its correct position in the sorted sub-array `arr(1:i-1)`. It does this by shifting elements larger than `arr(i)` one position to the right to make space. Once the correct position is found (either the beginning of the array or an element smaller than `arr(i)`), `arr(i)` is placed there. The time complexity is O(n^2) in the average and worst cases, and O(n) in the best case (when the array is already sorted). The space complexity is O(1) as it sorts in-place. An invariant maintained by `insertElement` is that after its execution, the sub-array `arr(1:index)` is sorted.

function insertionSortWithHelper(arr): n = length(arr) if n <= 1: return arr sortedArr = copy of arr for i from 2 to n: sortedArr = insertElement(sortedArr, i) return sortedArr function insertElement(arr, index): element...

This Octave implementation of Merge Sort sorts an array using a recursive divide-and-conquer strategy. It splits the array into halves, recursively sorts each half, and then merges the sorted halves. Merge Sort is a stab...

The `mergeSort` function sorts an array by recursively dividing it into smaller sub-arrays until each sub-array contains only one element (which is inherently sorted). The `merge` helper function then takes two sorted sub-arrays and merges them into a single sorted array. This process is repeated until the entire array is sorted. The base case for the recursion is an array of length 0 or 1. The `merge` function uses three pointers: one for the left sub-array, one for the right sub-array, and one for the resulting merged array. It iteratively compares elements from the left and right sub-arrays, placing the smaller element into the merged array. After one of the sub-arrays is exhausted, the remaining elements of the other sub-array are appended. The time complexity of Merge Sort is O(n log n) in all cases (best, average, and worst) due to its consistent divide-and-conquer approach. The space complexity is O(n) because of the auxiliary space required for the merged sub-arrays during the merge operation. An invariant for the `merge` function is that at any point, the elements already placed in `mergedArr` are sorted, and the remaining elements in `left` and `right` are also sorted.

function mergeSort(arr): n = length(arr) if n <= 1: return arr mid = floor(n / 2) leftHalf = arr[1 to mid] rightHalf = arr[mid+1 to n] sortedLeft = mergeSort(leftHalf) sortedRight = mergeSort(rightHalf) return merge(sort...

This Octave function sorts an array of numbers using the Bubble Sort algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Bubble Sort is a simple sor...

The `bubbleSort` function sorts an array in ascending order. It takes an array `arr` as input and returns a new sorted array. The algorithm uses two nested loops. The outer loop runs `n-1` times, where `n` is the length of the array, ensuring that each element is compared and potentially moved to its correct position. The inner loop iterates through the unsorted portion of the array, comparing adjacent elements. If an element is greater than the one next to it, they are swapped. This process continues until the array is sorted. The time complexity is O(n^2) in the worst and average cases, and O(n) in the best case (already sorted array) if an optimization is added to detect if any swaps occurred. The space complexity is O(1) if sorting in-place, or O(n) if a copy is made. An invariant is that after the `i`-th pass of the outer loop, the last `i` elements of the array are in their final sorted positions.

function bubbleSort(arr): n = length(arr) if n <= 1: return arr sortedArray = copy of arr for i from 1 to n-1: for j from 1 to n-i: if sortedArray[j] > sortedArray[j+1]: swap sortedArray[j] and sortedArray[j+1] return so...

This Octave code performs a Depth-First Search (DFS) on a graph represented by an adjacency list. DFS explores as far as possible along each branch before backtracking. It's crucial for tasks like finding connected compo...

The `dfsAdjacencyList` function implements Depth-First Search starting from a specified node. It uses a boolean array `visited` to keep track of nodes that have already been explored and a cell array `visitedOrder` to record the sequence of visited nodes. The core of the algorithm is the recursive `dfsRecursive` function. When `dfsRecursive` is called for a `currentNode`, it marks the node as visited and adds it to `visitedOrder`. It then iterates through all the `neighbors` of `currentNode` from the adjacency list. If a `neighborNode` has not yet been visited, `dfsRecursive` is called on that `neighborNode`, effectively going deeper into the graph. This process continues until a node has no unvisited neighbors, at which point the recursion unwinds, and the search backtracks. The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because each vertex and each edge is visited at most once. The space complexity is O(V) in the worst case for the recursion stack and the `visited` array. An invariant is that `visited(node)` is true if and only if `node` has been fully explored or is currently on the recursion stack.

function dfsAdjacencyList(graph, startNode): numNodes = length(graph) visited = array of false(numNodes) visitedOrder = empty list dfsRecursive(startNode) return visitedOrder function dfsRecursive(currentNode): mark curr...

This Octave function performs a Binary Search on a sorted array to find the index of a specific target value. Binary Search is a highly efficient algorithm for searching sorted data structures, significantly outperformin...

The `binarySearch` function efficiently finds a `target` value within a `sortedArr`. It initializes `low` and `high` pointers to the start and end of the array, respectively. In each iteration of the `while` loop, it calculates the middle index `mid`. It then compares the element at `mid` with the `target`. If they match, the index `mid` is returned. If the `target` is smaller than `sortedArr(mid)`, the search space is reduced to the left half by setting `high = mid - 1`. Conversely, if the `target` is larger, the search space is reduced to the right half by setting `low = mid + 1`. This process continues until `low` becomes greater than `high`, indicating that the `target` is not present in the array, in which case `0` is returned. The time complexity is O(log n) because the search space is halved in each step. The space complexity is O(1) as it uses a constant amount of extra space. An invariant is that the `target` element, if present, will always lie within the range `[low, high]` at the beginning of each loop iteration.

function binarySearch(sortedArr, target): n = length(sortedArr) if n == 0: return 0 low = 1 high = n while low <= high: mid = floor((low + high) / 2) midValue = sortedArr[mid] if midValue == target: return mid else if ta...