This Julia code implements an optimized binary search algorithm designed to find elements in a sorted array. It includes helper functions to specifically find the first and last occurrences of a target element, even when...

The `optimized_binary_search` function implements binary search with a focus on handling duplicates and preventing integer overflow. It iteratively narrows down the search space by comparing the target value with the middle element of the current range. The mid-point calculation `low + div(high - low, 2)` is a standard technique to avoid overflow that can occur with `(low + high) / 2` when `low` and `high` are very large. When a match is found, it adjusts the `high` pointer to `mid - 1` to continue searching in the left half, aiming to find the first occurrence. The `find_first_occurrence` function acts as a wrapper, directly returning the result of the optimized search. The `find_last_occurrence` function uses a modified binary search where it continues searching in the right half (`low = mid + 1`) if `arr[mid] <= target`, ensuring it finds the rightmost index. The time complexity for all these functions is O(log n) because the search space is halved in each iteration. The space complexity is O(1) as it uses a constant amount of extra space. Edge cases like empty arrays and targets not present are handled by returning -1.

function optimized_binary_search(arr, target): if arr is empty: return -1 low = 1 high = length(arr) result_index = -1 while low <= high: mid = low + (high - low) / 2 if arr[mid] == target: result_index = mid high = mid...

This Julia code implements the merge sort algorithm using recursion. It divides the input array into smaller halves, sorts them recursively, and then merges the sorted halves back together. Merge sort is a stable, compar...

The `merge_sort_recursive` function implements the divide-and-conquer strategy of merge sort. It first checks for the base case: if the array has one or zero elements, it's already sorted and returned. Otherwise, it splits the array into two halves, recursively calls itself to sort each half, and then uses the `merge` function to combine the two sorted halves into a single sorted array. The `merge` function takes two sorted arrays and iteratively compares their first elements, adding the smaller one to a new `merged_arr` until one of the input arrays is exhausted. Any remaining elements from the non-exhausted array are then appended. This process guarantees that the `merged_arr` is also sorted. The time complexity of merge sort is O(n log n) in all cases (best, average, and worst) because the array is consistently divided and merged. The space complexity is O(n) due to the creation of temporary arrays during the merge step. Edge cases like empty arrays and arrays with a single element are handled by the base case of the recursion.

function merge_sort_recursive(arr): n = length(arr) if n <= 1: return arr mid = n / 2 left_half = arr[1 to mid] right_half = arr[mid+1 to n] sorted_left = merge_sort_recursive(left_half) sorted_right = merge_sort_recursi...

This Julia function simulates the motion of a simple pendulum using the Euler method, a basic numerical technique for solving ordinary differential equations (ODEs). It tracks the pendulum's angle and angular velocity ov...

The `simulate_pendulum_euler` function models a simple pendulum's motion by discretizing time and applying Euler's method. The state of the pendulum is defined by its angle (`theta`) and angular velocity (`omega`). The core of the simulation involves updating these variables in small time steps (`time_step`) based on the pendulum's differential equations: `d(theta)/dt = omega` and `d(omega)/dt = -(g/L) * sin(theta)`. The Euler method approximates the next state by assuming the rate of change is constant over the time step. Time complexity is O(total_time / time_step), as each time step is processed once. Space complexity is O(total_time / time_step) to store the history of states. Edge cases include invalid physical parameters (non-positive `g`, `L`, `time_step`, `total_time`) and initial angles outside the typical range [-pi, pi], which are handled with errors or warnings.

function simulate_pendulum_euler(initial_angle, initial_omega, g, L, time_step, total_time): if g <= 0 or L <= 0 or time_step <= 0 or total_time <= 0: error theta = initial_angle omega = initial_omega time = 0.0 times =...

This Julia program calculates the minimum number of scalar multiplications required to multiply a chain of matrices and determines the optimal parenthesization. It uses dynamic programming to solve the matrix chain multi...

The `matrix_chain_order` function implements a dynamic programming approach to solve the matrix chain multiplication problem. It computes `m[i, j]`, the minimum cost to multiply matrices A_i through A_j, and `s[i, j]`, the split point `k` that yields this minimum cost. The algorithm iterates through increasing chain lengths `L`, filling the `m` and `s` tables. The time complexity is O(n^3) due to three nested loops, and the space complexity is O(n^2) for storing the `m` and `s` tables. Edge cases include handling fewer than two dimensions (no matrices or one matrix), returning 0 cost, and ensuring all dimensions are positive. The `print_optimal_parens` helper reconstructs the optimal parenthesization from the `s` table.

function matrix_chain_order(p): n = length(p) - 1 if n < 1: return 0, empty_matrix initialize m[n, n] and s[n, n] for i from 1 to n: m[i, i] = 0 for L from 2 to n: // chain length for i from 1 to n - L + 1: j = i + L - 1...

This Julia function estimates the value of Pi using a Monte Carlo simulation. It generates a large number of random points within a square that inscribes a circle. By counting how many points fall inside the circle, it a...

The `estimate_pi_monte_carlo` function leverages the Monte Carlo method. It simulates throwing darts randomly at a square target containing an inscribed circle. The probability of a dart landing inside the circle is the ratio of the circle's area (πr²) to the square's area ((2r)²), which simplifies to π/4. By generating `num_samples` random points (x, y) within the square [-1, 1] x [-1, 1] and checking if `x^2 + y^2 <= 1`, we count how many fall inside the unit circle. The estimated value of Pi is then `4 * (points_inside_circle / num_samples)`. The time complexity is O(num_samples) because each sample requires constant time operations. Space complexity is O(1) as it only stores counters. Edge cases include non-positive sample counts, which are handled by an error.

function estimate_pi_monte_carlo(num_samples): if num_samples <= 0: error points_inside_circle = 0 total_points = num_samples for i from 1 to num_samples: generate random x between -1 and 1 generate random y between -1 a...

This Julia function implements the Breadth-First Search (BFS) algorithm to traverse a graph represented by an adjacency list. BFS explores a graph level by level, starting from a given node. It systematically visits all...

The `bfs` function uses a queue to manage nodes to visit and a set to keep track of visited nodes. It starts by adding the `start_node` to the queue and marking it as visited. While the queue is not empty, it dequeues a node, adds it to the `traversal_order`, and then enqueues all its unvisited neighbors, marking them as visited. 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 edge is processed at most once. The space complexity is O(V) in the worst case for storing the queue and visited set. Edge cases include a start node not present in the graph or disconnected components, which are handled by the initial check and the nature of BFS respectively.

function bfs(graph, start_node): if start_node not in graph: error visited = empty set queue = empty queue traversal_order = empty list enqueue start_node into queue add start_node to visited while queue is not empty: cu...

This Julia function performs LU decomposition with partial pivoting on a square matrix. LU decomposition factors a matrix A into three matrices: P (a permutation matrix), L (a lower triangular matrix), and U (an upper tr...

The `lu_decomposition_pivot` function implements Gaussian elimination with partial pivoting to achieve LU decomposition. It iterates through columns, selecting the row with the largest absolute value in the current column (partial pivoting) to ensure numerical stability and swapping rows if necessary. This pivoting is tracked by the permutation matrix `P`. For each column `j`, it then eliminates the entries below the diagonal in `U` by subtracting multiples of row `j` from subsequent rows, storing the multipliers in `L`. The time complexity is O(n^3) due to the three nested loops, and the space complexity is O(n^2) for storing L, U, and P. Edge cases include non-square matrices and singular matrices, which are handled by errors.

function lu_decomposition_pivot(A): n, m = size(A) if n != m: error "Matrix must be square" L = identity_matrix(n) U = copy(A) P = identity_matrix(n) for j from 1 to n: // column find pivot_row in column j from row j dow...

This Julia program implements a Bayesian linear regression model using the Turing.jl probabilistic programming library. It defines a probabilistic model with prior distributions for the regression coefficients and noise,...

The `bayesian_linear_regression` model defines the probabilistic structure: priors for `beta0` (intercept), `beta1` (slope), and `sigma` (noise standard deviation) are set using `Normal` and `Exponential` distributions. The likelihood `y ~ MvNormal(mu, sigma)` specifies that the observed `y` values are normally distributed around the linear predictor `mu = beta0 .+ beta1 .* x` with standard deviation `sigma`. The `infer_bayesian_linear_regression` function uses Turing's NUTS sampler to draw samples from the posterior distribution of the parameters. The time complexity depends heavily on the sampler and the number of samples/chains, but is generally computationally intensive. Space complexity is O(num_samples * num_chains * num_parameters) for storing the MCMC chain. Edge cases include mismatched data lengths and invalid sample/chain counts, which are handled by errors.

function bayesian_linear_regression(x, y): // Priors beta0 ~ Normal(0, 10) beta1 ~ Normal(0, 10) sigma ~ Exponential(1.0) // Linear predictor mu = beta0 + beta1 * x // Likelihood y ~ Normal(mu, sigma) function infer_baye...