Practice Code Typing – SkillsTyping

Choose your language:

ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:

Ready

Exercise Algorithm Area

Correct typos to continue.

1function [x_refined, num_iterations] = iterativeRefinementLU(A, b)
2% Iterative Refinement for solving Ax = b using LU decomposition.
3% Improves the accuracy of the solution by repeatedly correcting it.
4
5[m, n] = size(A);
6
7% Input validation: Ensure A is square and dimensions match b
8if m ~= n
9error('IterativeRefinementLU:MatrixNotSquare', 'Matrix A must be square.');
10end
11if size(b, 1) ~= m || size(b, 2) ~= 1
12error('IterativeRefinementLU:VectorDimensionMismatch', 'Vector b must have dimensions matching A (m x 1).');
13end
14
15% Tolerance for stopping criterion
16tol = 1e-10;
17max_iterations = 10;
18
19% Step 1: Compute initial solution using LU decomposition
20% Perform LU decomposition with partial pivoting for stability
21[L, U, P_perm] = lu(A);
22
23% Check for singularity (or near-singularity)
24if abs(det(A)) < eps('double') * max(m, n)
25warning('IterativeRefinementLU:MatrixSingular', 'Matrix A is singular or near-singular. Results may be inaccurate.');
26% Attempt to proceed, but results might be unreliable.
27end
28
29% Solve Ly = Pb for y (forward substitution)
30Pb = P_perm * b;
31y = linsolve(L, Pb);
32
33% Solve Ux = y for x (backward substitution)
34x_current = linsolve(U, y);
35
36% Initialize refined solution and iteration count
37x_refined = x_current;
38num_iterations = 0;
39
40% Step 2: Iterative Refinement Loop
41for iter = 1:max_iterations
42num_iterations = iter;
43
44% Calculate the residual: r = b - A * x_current
45% Use higher precision if available, or careful calculation
46residual = b - A * x_current;
47
48% Check for convergence
49residual_norm = norm(residual);
50if residual_norm < tol * norm(b)
51break; % Converged
52end
53
54% Step 3: Solve for the correction delta_x
55% Solve L * U * delta_x = residual (using the same LU factors)
56% Solve L * y_corr = residual (forward substitution)
57y_corr = linsolve(L, residual);
58
59% Solve U * delta_x = y_corr (backward substitution)
60delta_x = linsolve(U, y_corr);
61
62% Step 4: Update the solution
63x_current = x_current + delta_x;
64x_refined = x_current; % Update the best estimate
65end
66
67% Handle cases where max_iterations is reached without convergence
68if num_iterations == max_iterations && norm(b - A * x_refined) >= tol * norm(b)
69warning('IterativeRefinementLU:MaxIterationsReached', 'Maximum iterations reached without full convergence.');
70end
71
72end
73
74% Note: MATLAB's built-in lu() and linsolve() are highly optimized and numerically stable.
75% This implementation demonstrates the concept of iterative refinement.
76% For extremely ill-conditioned matrices, higher precision arithmetic (like symbolic math toolbox)
77% might be necessary for significant gains beyond standard double precision solvers.

Algorithm description viewbox

Iterative Refinement for Linear Systems (LU Decomposition)

Algorithm description:

This MATLAB function implements an iterative refinement procedure to enhance the accuracy of solutions to linear systems of equations (Ax = b). It starts with an initial solution obtained via LU decomposition and then iteratively refines this solution by calculating the residual and solving a modified system for a correction term. This method is particularly effective for ill-conditioned matrices where standard direct solvers might produce solutions with significant errors. Iterative refinement is widely used in numerical linear algebra to achieve high-precision solutions in scientific computing and engineering simulations.

Algorithm explanation:

Iterative refinement is a technique to improve the accuracy of a computed solution `x` to a linear system `Ax = b`. The process begins by obtaining an initial solution `x_0` using a direct method like LU decomposition. In each iteration, the residual `r = b - A*x_k` is computed. This residual is then used to find a correction `delta_x` by solving the system `A*delta_x = r` (often using the same factorization of A, e.g., LU). The solution is updated as `x_{k+1} = x_k + delta_x`. This process is repeated until the residual is sufficiently small or a maximum number of iterations is reached. The key to its effectiveness lies in computing the residual using higher precision arithmetic or by carefully managing precision to avoid catastrophic cancellation. This implementation uses MATLAB's double-precision arithmetic and its built-in `lu` and `linsolve` functions. The time complexity is dominated by the initial LU decomposition, which is O(n^3), and each refinement step is O(n^2) for residual calculation and O(n^2) for solving the correction system. The space complexity is O(n^2) for storing the LU factors. The algorithm includes checks for square matrices, dimension mismatches, and near-singularity, and uses a tolerance-based stopping criterion.

Pseudocode:

function iterativeRefinementLU(A, b):
  get dimensions m, n of A
  validate A is square and dimensions match b
  set tolerance `tol` and max_iterations
  
  // Step 1: Initial Solution
  compute LU decomposition of A with pivoting: [L, U, P] = lu(A)
  check if A is singular or near-singular
  Pb = P * b
  y = forward_substitution(L, Pb)
  x_current = backward_substitution(U, y)
  x_refined = x_current
  num_iterations = 0
  
  // Step 2: Iterative Refinement Loop
  for iter from 1 to max_iterations:
    num_iterations = iter
    
    // Calculate residual
    residual = b - A * x_current
    
    // Check for convergence
    if norm(residual) < tol * norm(b):
      break
      
    // Step 3: Solve for correction delta_x
    y_corr = forward_substitution(L, residual)
    delta_x = backward_substitution(U, y_corr)
    
    // Step 4: Update solution
    x_current = x_current + delta_x
    x_refined = x_current
    
  if max_iterations reached and not converged, issue warning
  
  return x_refined, num_iterations

// Helper functions forward_substitution and backward_substitution are assumed to exist and use L, U.

Library

Playable exercises

Choose Exercise

Filter, sort, and preview algorithm before you choose one to play.

Total 19 published items

Pages 3 pages available

Language

Sort by Direction

Browse published coding scenarios with filters, sorting, and pagination.

Published

MATLAB DataAI (matlab)

Implement Binary Search

Difficulty: writing: 3; length: 2
Popularity: 0
Created: 2026-01-28 14:58 UTC
Published: 2026-01-28 15:16 UTC
Author: Damian

#binary search #sorted array #search algorithm #logarithmic time #divide and conquer

goal: Find the index of a target value in a sorted array.

Canonical Algorithm Text

function index = binarySearch(arr, target) % Performs binary search on a sorted array. % Returns the index of the target if found, otherwise -1. low = 1; high = length(arr); index = -1; % Edge case: empty array. if isempty(arr) return; end while low <= high % Calculate mid to pre...

Description Algorithm

This function implements the binary search algorithm to efficiently find a target value within a sorted array. It repeatedly divides the search interval in half. This is a fundamental algorithm used in searching database...

Explanation

Binary search operates on a sorted array by repeatedly dividing the search interval in half. It starts with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, the search narrows to the lower half. Otherwise, it narrows to the upper half. This process is repeated until the value is found or the interval is empty. The time complexity is O(log N), where N is the number of elements in the array, due to the halving of the search space in each step. The space complexity is O(1) as it uses a constant amount of extra space. Key edge cases include an empty array, a target smaller than the smallest element, a target larger than the largest element, and the target being the first or last element. The loop invariant is that if the target exists, it must be within the `arr(low:high)` subarray.

Pseudocode

function binarySearch(arr, target): low = 0 high = length(arr) - 1 index = -1 if arr is empty: return index while low <= high: mid = low + floor((high - low) / 2) if arr[mid] == target: index = mid return index else if a...

Published

MATLAB DataAI (matlab)

Implement Factorial Recursively

Difficulty: writing: 8; length: 1
Popularity: 0
Created: 2026-01-28 14:58 UTC
Published: 2026-01-28 15:16 UTC
Author: Damian

#factorial #recursion #base case #recursive step #mathematical functions

goal: Calculate the factorial of a non-negative integer using recursion.

Canonical Algorithm Text

function result = factorialRecursive(n) % Computes the factorial of a non-negative integer recursively. % Edge case: negative input is undefined. if n < 0 error('Factorial is not defined for negative numbers.'); end % Base case: factorial of 0 is 1. if n == 0 result = 1; else % R...

Description Algorithm

This function calculates the factorial of a non-negative integer using recursion. The factorial of a number `n` (denoted as `n!`) is the product of all positive integers less than or equal to `n`. This recursive implemen...

Explanation

The factorial function `n!` is defined as the product of all positive integers up to `n`. For `n=0`, `0!` is defined as 1. This recursive implementation directly translates this definition. The base case is `n=0`, where the function returns 1. For any `n > 0`, the function calls itself with `n-1` and multiplies the result by `n`. The time complexity is O(N) because each recursive call reduces `n` by 1 until the base case is reached, resulting in N calls. The space complexity is also O(N) due to the call stack depth required to store the intermediate function calls. An important edge case is handling negative input, for which factorial is undefined, and this implementation throws an error. The correctness relies on the base case being correctly handled and the recursive step accurately reducing the problem size.

Pseudocode

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

Published

MATLAB DataAI (matlab)

Implement Dijkstra's Algorithm

Difficulty: writing: 4; length: 6
Popularity: 0
Created: 2026-01-28 14:58 UTC
Published: 2026-01-28 15:16 UTC
Author: Damian

#dijkstra #shortest path #graph algorithms #priority queue #greedy algorithm #weighted graph

goal: Find the shortest paths from a single source node to all other nodes in a weighted graph.

Canonical Algorithm Text

function distances = dijkstra(graph, startNode) % Computes shortest paths from a start node to all other nodes in a weighted graph. % Uses Dijkstra's algorithm with a min-priority queue. numNodes = size(graph, 1); distances = inf(1, numNodes); % Initialize distances to infinity d...

Description Algorithm

Dijkstra's algorithm finds the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. It's a greedy algorithm that iteratively selects the unvisited node with the smallest...

Explanation

Dijkstra's algorithm maintains a set of visited nodes and a distance array, initialized to infinity for all nodes except the start node (which is 0). It uses a priority queue to efficiently select the unvisited node with the smallest tentative distance. In each step, it extracts the node `u` with the minimum distance from the priority queue, marks it as visited, and then relaxes all edges `(u, v)` originating from `u`. Relaxation involves checking if the path through `u` to `v` is shorter than the current shortest path known for `v`. If so, the distance to `v` is updated, and `v` is added to the priority queue. The time complexity is typically O(E log V) or O(E + V log V) using a binary heap, where V is the number of vertices and E is the number of edges. With a Fibonacci heap, it can be O(E + V log V). Space complexity is O(V + E) for storing the graph and O(V) for the priority queue and visited set. Edge cases include disconnected graphs (unreachable nodes remain at infinity distance), graphs with only one node, and graphs with no edges.

Pseudocode

function dijkstra(graph, startNode): numNodes = number of nodes in graph distances = array of size numNodes, initialized to infinity distances[startNode] = 0 priority_queue = empty min-priority queue add (0, startNode) t...

Published

MATLAB DataAI (matlab)

Find All Anagrams in a String

Difficulty: writing: 9; length: 4
Popularity: 0
Created: 2026-01-28 14:58 UTC
Published: 2026-01-28 15:16 UTC
Author: Damian

#sliding window #anagrams #string matching #frequency map #hash map #algorithms

goal: Find all starting indices of anagrams of a pattern string within a text string.

Canonical Algorithm Text

function indices = findAnagrams(s, p) % Finds all start indices of p's anagrams in s. % Uses a sliding window approach. n = length(s); m = length(p); indices = []; % Edge case: if pattern is longer than string, no anagrams possible. if m > n return; end % Frequency maps for patte...

Description Algorithm

This function finds all occurrences of anagrams of a pattern string `p` within a larger text string `s`. It employs a sliding window technique, maintaining frequency counts of characters within the window and comparing t...

Explanation

The algorithm uses a sliding window of size equal to the length of the pattern `p`. Two frequency maps (hash maps or dictionaries) are maintained: one for the pattern `p` and one for the current window in `s`. The pattern's frequency map is computed once. The window's frequency map is initialized with the first `m` characters of `s`. Then, the window slides one character at a time. For each slide, the character entering the window is added to `sFreq`, and the character leaving the window is removed. If `sFreq` becomes equal to `pFreq`, it signifies an anagram, and the starting index of the window is recorded. The time complexity is O(N), where N is the length of `s`, because each character is processed a constant number of times. The space complexity is O(K), where K is the size of the character set (e.g., 26 for lowercase English letters), for storing the frequency maps. Edge cases include an empty pattern, an empty string, or a pattern longer than the string, all of which are handled by returning an empty result or early exit.

Pseudocode

function findAnagrams(s, p): n = length(s) m = length(p) result_indices = [] if m > n: return result_indices p_freq = map() s_freq = map() // Initialize p_freq for each char c in p: increment count of c in p_freq // Init...

Published

MATLAB DataAI (matlab)

Implement a Trie (Prefix Tree)

Difficulty: writing: 7; length: 6
Popularity: 0
Created: 2026-01-28 14:18 UTC
Published: 2026-01-28 15:17 UTC
Author: Admin

#trie #prefix tree #string algorithms #data structures #autocomplete

goal: Implement a Trie data structure for efficient string operations. input: Strings for insertion and searching. output: Boolean indicating success of search/startsWith, or void for insert.

Canonical Algorithm Text

classdef TrieNode properties children = containers.Map('char', TrieNode.empty); isEndOfWord = false; end end classdef Trie properties root; end methods function obj = Trie() % Constructor initializes the Trie with a root node. obj.root = TrieNode(); end function insert(obj, word)...

Description Algorithm

This code implements a Trie (prefix tree) data structure in MATLAB, which is efficient for storing and retrieving strings based on their prefixes. It includes methods for inserting words, searching for exact word matches...

Explanation

The Trie is implemented using a `TrieNode` class, where each node can have multiple children (one for each possible character) and a flag indicating if it marks the end of a word. The `insert` method traverses the Trie, creating new nodes as needed, and marks the final node for the word. The `search` method follows the path for the given word and checks the `isEndOfWord` flag. The `startsWith` method checks if a path for the prefix exists. The time complexity for insertion, search, and prefix search is O(L), where L is the length of the word or prefix, as it involves a single traversal. The space complexity depends on the number of nodes, which is proportional to the total number of characters in all inserted words. Edge cases like empty strings and non-existent prefixes are handled. The structure ensures that all prefixes of a valid word are also implicitly represented.

Pseudocode

class TrieNode: children = map() isEndOfWord = false class Trie: root = TrieNode() function insert(word): currentNode = root for each character in word: if character not in currentNode.children: currentNode.children[char...

Published

MATLAB DataAI (matlab)

Bubble Sort Implementation

Difficulty: writing: 2; length: 4
Popularity: 0
Created: 2026-01-28 14:18 UTC
Published: 2026-01-28 15:17 UTC
Author: Admin

#bubble sort #sorting algorithms #basic algorithms #quadratic time #in-place sort

goal: Sort an array using the Bubble Sort algorithm. input: A numerical array `arr`. output: A new array `sortedArray` containing the elements of `arr` in ascending order.

Canonical Algorithm Text

function sortedArray = bubbleSort(arr) % Implements the Bubble Sort algorithm to sort an array in ascending order. % This is a simple, but generally inefficient, sorting algorithm. % It repeatedly steps through the list, compares adjacent elements and swaps them % if they are in...

Description Algorithm

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted....

Explanation

Bubble Sort works by making multiple passes through the array. In each pass, it compares adjacent elements and swaps them if they are in the wrong order. The largest unsorted element 'bubbles up' to its correct position at the end of the unsorted portion of the array in each pass. The time complexity is O(n^2) in the worst and average cases, where n is the number of elements, due to the nested loops. In the best case (already sorted array), it can be O(n) if an optimization flag is used to detect no swaps. The space complexity is O(1) as it sorts in-place, requiring only a constant amount of extra space for temporary variables. The algorithm is correct because each pass guarantees that at least one more element is placed in its final sorted position.

Pseudocode

function bubbleSort(arr): n = length(arr) for i from 1 to n-1: swapped = false for j from 1 to n-i: if arr[j] > arr[j+1]: swap arr[j] and arr[j+1] swapped = true if not swapped: break return arr

Published

MATLAB DataAI (matlab)

Selection Sort Implementation

Difficulty: writing: 7; length: 5
Popularity: 0
Created: 2026-01-28 14:18 UTC
Published: 2026-01-28 15:17 UTC
Author: Admin

#selection sort #sorting algorithms #in-place sort #quadratic time #comparison sort

goal: Sort an array using the Selection Sort algorithm. input: A numerical array `arr`. output: A new array `sortedArray` containing the elements of `arr` in ascending order.

Canonical Algorithm Text

function sortedArray = selectionSort(arr) % Implements the Selection Sort algorithm to sort an array in ascending order. % This algorithm divides the input list into two parts: a sorted sublist % built from left to right at the front (left) of the list and a % sublist of the rema...

Description Algorithm

Selection Sort is a simple in-place comparison sorting algorithm. It works by repeatedly selecting the smallest element from the unsorted portion of the array and moving it to the beginning of the sorted portion. This pr...

Explanation

Selection Sort divides the array into two parts: a sorted prefix and an unsorted suffix. In each pass, it finds the minimum element in the unsorted suffix and swaps it with the first element of the unsorted suffix. This effectively extends the sorted prefix by one element. The time complexity is O(n^2) in all cases (best, average, and worst) because it always performs n-1 passes, and each pass involves scanning the remaining unsorted portion of the array. The space complexity is O(1) because it sorts the array in-place, using only a constant amount of extra memory for temporary variables during swaps. The algorithm is correct because each pass correctly places the next smallest element into its final sorted position.

Pseudocode

function selectionSort(arr): n = length(arr) for i from 1 to n-1: minIndex = i for j from i+1 to n: if arr[j] < arr[minIndex]: minIndex = j if minIndex != i: swap arr[i] and arr[minIndex] return arr

Published

MATLAB DataAI (matlab)

Find Peak Element in 1D Array

Difficulty: writing: 4; length: 3
Popularity: 0
Created: 2026-01-28 14:18 UTC
Published: 2026-01-28 15:17 UTC
Author: Admin

#binary search #peak finding #array algorithms #logarithmic time #edge cases

goal: Find a peak element in a 1D array. input: A numerical array `nums`. output: The index of a peak element.

Canonical Algorithm Text

function peakIndex = findPeakElement(nums) % Finds the index of a peak element in a 1D array. % A peak element is an element that is strictly greater than its neighbors. % Assumes nums is not empty. n = length(nums); left = 1; right = n; % Handle edge cases for arrays of size 1 o...

Description Algorithm

This function identifies and returns the index of a peak element within a one-dimensional array. A peak element is defined as an element that is strictly greater than its immediate neighbors. This algorithm is useful in...

Explanation

The algorithm uses a binary search approach to efficiently find a peak element. It leverages the property that if an element is not a peak, at least one of its neighbors must be greater, guiding the search towards a peak. The time complexity is O(log n) because the search space is halved in each iteration. The space complexity is O(1) as it only uses a few variables. Edge cases like arrays of size 1 or 2, and peaks at the array boundaries, are explicitly handled. The correctness is ensured by the binary search invariant: a peak element is guaranteed to exist within the current search interval [left, right].

Pseudocode

function findPeakElement(nums): n = length(nums) if n == 1: return 1 if nums[0] > nums[1]: return 0 if nums[n-1] > nums[n-2]: return n-1 left = 1 right = n - 2 while left <= right: mid = floor((left + right) / 2) if nums...

Language (required)

Paste your code (required)

Max 20,000 characters. (Dangerous HTML/script fragments will be blocked)

Normalized preview:

I agree to Publish this, after admin approval (queued for review). (Not required) I confirm this submission is anonymous and does not contain personal data. I grant SkillsTyping a free, non-exclusive, worldwide, and irrevocable license to store, modify, adapt, and publish this content after review. I understand that publication is not guaranteed, that I retain no ownership or usage claims over published versions, and that no compensation will be provided. See Privacy Policy

Publish details

Shown only if you opt to submit for review. Required when consent is checked.

Title (required with consent)

Short description / summary (required with consent)

Algorithm explanation (required with consent)

Pseudocode (required with consent)