Programs: algorithms

18 verified Soma programs in the algorithms domain. Each page shows the source and what soma check, soma test, soma verify and soma run printed on it.

Program	Lines	Uses
Breadth-first search on a small directed graph represented as an adjacency	69
Binary search over a sorted List<Int> — returns the index or -1	50
Bubble sort over a list, with the classic early-exit optimization	51
Counting sort — a non-comparison O(n + k) sort for small non-negative integers, plus the Sieve of Eratosthenes for the primes up to n	64
Depth-first search on a directed graph: preorder traversal and cycle detection via the classic white/grey/black coloring	89
Levenshtein edit distance — classic 2D dynamic programming	53
Fibonacci three ways: naive recursion, bottom-up iteration, and a memoized version backed by a [persistent] memory slot	58
Euclid's algorithm: GCD (iterative + recursive), LCM, the extended Euclid algorithm returning Bezout coefficients, and a coprimality check	81
Insertion sort and binary insertion sort on a List<Int>	53
0/1 knapsack — maximize value within a weight budget via 2D DP	55
Longest increasing subsequence (LIS) — O(n^2) dynamic programming	41
Merge sort on a List<Int> — top-down, purely functional	64
Coin change, minimum number of coins to make an amount (unbounded knapsack)	49
A FIFO queue and a sliding-window maximum over a List	48
Quicksort on a List<Int> — Lomuto partition, recursive	42
A stack (LIFO) backed by a List, used to check balanced brackets	69	match
Two-sum with a hash set, and the count of distinct pairs summing to a target	47
Word frequency counting with a Map<String, Int> — the canonical hash-map histogram	54