[pull] master from TheAlgorithms:master - #53

* Implement LengthOfLastWord algorithm in strings package

* Add JUnit tests for LengthOfLastWord algorithm

* style: fix import order and spacing for clang-format

)

* Improve QuickSort documentation with detailed comments and explanations

* Format QuickSort documentation and fix JavaDoc layout

* Add recursive factorial implementation with tests

* [STYLE] Apply clang-format

* Move recursive factorial to recursion package and remove duplicate

* Move recursive factorial to recursion package and remove duplicate

* Apply clang-format to factorial recursion tests

* Apply clang-format to factorial recursion tests

---------

Co-authored-by: Koushik Sai <nyamathabadkoushik@gmail.com>
Co-authored-by: Deniz Altunkapan <deniz.altunkapan@outlook.com>

* Add immutable HashMap implementation

* Add immutable HashMap implementation

* Applied clang-format

---------

Co-authored-by: Koushik Sai <nyamathabadkoushik@gmail.com>

* Add StochasticMatrix utility class

This class provides methods to check if a matrix is row-stochastic or column-stochastic, ensuring all elements are non-negative and the sums of rows or columns equal 1.

* Change package from maths to matrix

Updated package declaration for StochasticMatrix class.

* Change package declaration in StochasticMatrixTest

* Delete src/test/java/com/thealgorithms/StochasticMatrixTest.java

* Refactor matrix initialization for test cases

* Fix formatting of matrix initialization in tests

* Remove unnecessary newline in StochasticMatrix

* Add import statement for JUnit in StochasticMatrixTest

* Add additional assertions to StochasticMatrixTest

* Clean up import statements in StochasticMatrixTest

Removed unused import statements for cleaner code.

* Reorder import statements in StochasticMatrixTest

* Remove unused import assertThrows from StochasticMatrixTest

Removed unused import for assertThrows.

* Added 0/1 Knapsack Algorithm using Dynamic Programming in Java

* Fix Checkstyle whitespace issues in Knapsack.java

* Formatted Knapsack.java to pass linter and added 0/1 Knapsack algorithm

* Formatted Knapsack.java to pass linter and added 0/1 Knapsack algorithm

* Formatted Knapsack.java to pass linter and added 0/1 Knapsack algorithm

* Formatted Knapsack.java to pass linter and added 0/1 Knapsack algorithm

---------

Co-authored-by: Deniz Altunkapan <deniz.altunkapan@outlook.com>

Co-authored-by: DenizAltunkapan <DenizAltunkapan@users.noreply.github.com>

* Add checklist item for test class inclusion

* Update pull request template for algorithm tests

….1 (#7188)

Bumps [com.puppycrawl.tools:checkstyle](https://github.com/checkstyle/checkstyle) from 12.3.0 to 12.3.1.
- [Release notes](https://github.com/checkstyle/checkstyle/releases)
- [Commits](checkstyle/checkstyle@checkstyle-12.3.0...checkstyle-12.3.1)

---
updated-dependencies:
- dependency-name: com.puppycrawl.tools:checkstyle
  dependency-version: 12.3.1
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

Add detailed JavaDoc for AllPathsFromSourceToTarget

….0 (#7193)

Bumps [com.puppycrawl.tools:checkstyle](https://github.com/checkstyle/checkstyle) from 12.3.1 to 13.0.0.
- [Release notes](https://github.com/checkstyle/checkstyle/releases)
- [Commits](checkstyle/checkstyle@checkstyle-12.3.1...checkstyle-13.0.0)

---
updated-dependencies:
- dependency-name: com.puppycrawl.tools:checkstyle
  dependency-version: 13.0.0
  dependency-type: direct:production
  update-type: version-update:semver-major
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

Bumps [org.junit:junit-bom](https://github.com/junit-team/junit-framework) from 6.0.1 to 6.0.2.
- [Release notes](https://github.com/junit-team/junit-framework/releases)
- [Commits](junit-team/junit-framework@r6.0.1...r6.0.2)

---
updated-dependencies:
- dependency-name: org.junit:junit-bom
  dependency-version: 6.0.2
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

…UE (#7604)

…changes (#7606)

ADWIN keeps a window of recent values and, after every sample, looks for a split into an old and a recent part whose means differ by more than a variance sensitive Hoeffding bound. When it finds one the old part is dropped, so the window grows while the stream is stationary and collapses as soon as it moves, and its length becomes an estimate of how long the current regime has lasted rather than a parameter to tune.

The window is stored as an exponential histogram, buckets of 1, 2, 4 ... elements with at most five of each size, so a window of n elements needs O(log n) buckets and cuts are tried only at bucket boundaries. The bucket merge carries the sum and the variance exactly, which the tests check against a direct computation over 2000 samples.

Signed-off-by: alxkm <19151554+alxkm@users.noreply.github.com>
Co-authored-by: alxkm <19151554+alxkm@users.noreply.github.com>

#7609)

* Sigmoid Activation function implementation with simplified batch calculation

* clang formatted

* braces

* private constructor added

* final + clang-format

* Update src/main/java/com/thealgorithms/maths/SigmoidActivation.java

Co-authored-by: Oleksandr Klymenko <alexanderklmn@gmail.com>

* Update src/main/java/com/thealgorithms/maths/SigmoidActivation.java

Co-authored-by: a <19151554+alxkm@users.noreply.github.com>

---------

Co-authored-by: a <19151554+alxkm@users.noreply.github.com>

Grubbs' test asks whether the single most extreme point is an outlier and breaks as soon as there are two of them, because each one inflates the standard deviation the other is measured against. The generalized extreme Studentized deviate test removes the most extreme point, recomputes the statistics on what is left and repeats r times, and the answer is the largest step whose statistic exceeds its critical value rather than the first, which is what defeats that masking.

The critical values need a Student t quantile, which the repository did not have, so the class computes it from the regularized incomplete beta function through a Lentz continued fraction and a Lanczos log gamma, inverted by bisection. No table is needed. The tests check the critical values and the number of outliers against Rosner's published 54 point example.

Signed-off-by: alxkm <19151554+alxkm@users.noreply.github.com>
Co-authored-by: alxkm <19151554+alxkm@users.noreply.github.com>

#7613)

* perf(strings): optimize LongestCommonSubstring DP memory to O(N) and add tests

* fix(strings): fix formatting, unicode characters and update performance test

* style(strings): add trailing newline to fix Checkstyle and Clang-format

* style(strings): inline lambda in testVeryLargeInputsPerformance for clang-format

---------

Co-authored-by: irenemartnez <117649832+irenemartnez@users.noreply.github.com>

…solute reading (#7614)

The classic pair is an accelerometer and a gyroscope measuring the same tilt: one never drifts but picks up every vibration, the other is smooth but has to be integrated, so any bias in it walks away without limit. Their errors live in different parts of the spectrum, and the filter is a high pass on the integrated rate plus a low pass on the absolute reading whose transfer functions sum to unity, so the true signal passes through untouched and no lag is introduced.

The single parameter is exposed as a time constant as well, tau = a * dt / (1 - a), which fixes the price of the trade exactly: a rate with a constant bias b leaves a steady state error of tau * b and no more. The tests check that identity, the geometric convergence onto the reference, the noise reduction of sqrt((1 - a) / (1 + a)), and that a ramp is followed without the lag a plain low pass on the reference would add.

Signed-off-by: alxkm <19151554+alxkm@users.noreply.github.com>
Co-authored-by: alxkm <19151554+alxkm@users.noreply.github.com>

…el (#7615)

The ordinary Kalman filter is optimal only for a linear model, and most things worth tracking are not linear: a bearing is an arctangent of the state, a range a square root of it. The extended filter pushes the state forward through the real functions and the covariance through their Jacobians, evaluated afresh at the current estimate, which keeps the whole machinery and replaces only the step that needed linearity.

The covariance correction is written in Joseph form rather than as the shorter (I - K H) P. The two agree in exact arithmetic, but the short one subtracts nearly equal matrices and can leave a covariance that is no longer symmetric or has a negative variance on its diagonal; the Joseph form is a sum of two products of the form A P A' and stays symmetric by construction. The innovation covariance is inverted with the existing matrix.InverseOfMatrix instead of another copy of Gaussian elimination.

The Javadoc states what the linearisation costs, namely that the filter is no longer optimal and can diverge on a sharp nonlinearity without the covariance warning about it. Tests: one update of a scalar filter is the textbook half way step, a linear model reproduces the scalar Kalman recursion to 1e-12 over 500 steps, the covariance stays symmetric over 500 steps of a three state model, and a target seen only as a range is tracked through the nonlinear measurement more accurately than inverting each reading on its own.

Signed-off-by: alxkm <19151554+alxkm@users.noreply.github.com>
Co-authored-by: alxkm <19151554+alxkm@users.noreply.github.com>

* docs: fix typos in comments

Fix misspellings found with codespell: reccur/reccuring, positon,
choosed, increate, contantating, and "Hava a Eulerian Path". Also
rename the local variable formater to formatter in MathBuilder.

* docs: fix grammar typos in comments

Fix "tho" -> "to", doubled "of of", "than" -> "then", "it's" -> "its",
"in-order to" -> "in order to", and "a" -> "an" before vowel sounds.

* feat(ciphers): add Lamport one-time signature

* Fix for the check

* fixing the bugs

* comments resolved

* Add Perceptron binary classifier

* Fixed related errors

* Fix PMD static import violation and cover Perceptron gaps

Reduce static imports to PMD's limit, assert the learned bias and
weights, and cover the length-mismatch, null-vector, and divergence
paths.

---------

Co-authored-by: Alex <19151554+alxkm@users.noreply.github.com>

…hub/workflows (#7618)

chore(deps): bump github/codeql-action in /.github/workflows

Bumps [github/codeql-action](https://github.com/github/codeql-action) from 4.38.0 to 4.38.1.
- [Release notes](https://github.com/github/codeql-action/releases)
- [Changelog](https://github.com/github/codeql-action/blob/main/CHANGELOG.md)
- [Commits](github/codeql-action@v4.38.0...v4.38.1)

---
updated-dependencies:
- dependency-name: github/codeql-action
  dependency-version: 4.38.1
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

…and (#7619)

The Euclidean distance compares sample i with sample i and nothing else, so two recordings of the same gesture, one performed slightly faster, come out as far apart as two unrelated ones. Dynamic time warping looks for the cheapest way to line the two series up instead: every point of each series is matched to at least one point of the other, the matching never goes backwards, and the cost is the sum over the matched pairs. That alignment is a shortest path through a grid, and the dynamic program has one line.

Left alone the alignment may match one point against an arbitrarily long stretch of the other, so the Sakoe-Chiba band is offered as well: it forbids matches further apart in time than a given width, which rules out those degenerate alignments and narrows the grid that has to be filled. The band has to be at least the difference in length or no alignment exists, and that is rejected rather than returned as infinity.

The distance runs in O(min(n, m)) memory over two rows; the warping path itself needs the whole grid and is returned as index pairs. The Javadoc notes that the result is not a metric, so it ranks candidates but cannot be indexed without further care.

Signed-off-by: alxkm <19151554+alxkm@users.noreply.github.com>
Co-authored-by: alxkm <19151554+alxkm@users.noreply.github.com>

* feat(ciphers): add Winternitz one-time signature (WOTS)

* test(ciphers): add tests for Winternitz one-time signature

…odel instead of differentiating it (#7622)

The extended filter pushes the covariance through a Jacobian, a straight line drawn at one point, which needs the model to be differentiable, needs the derivative written out, and discards everything beyond first order. The unscented filter picks 2n + 1 sigma points whose mean and covariance are exactly those of the estimate, sends each through the real model and reads the new mean and covariance off where they land. The square root that spreads them is a Cholesky factor, so a step costs about what the extended filter does, with no Jacobian anywhere, and the result is right to second order.

The defaults are alpha = 1, beta = 2, kappa = 0. The alpha = 1e-3 often quoted puts the sigma points almost on the mean and compensates with a central weight near minus a million, exact on paper and six digits lost in floating point. After an update the covariance P - K S K' is symmetrised explicitly, and a covariance that is no longer positive definite is refused with an ArithmeticException instead of being given a square root that does not exist. The innovation covariance is inverted with the existing matrix.InverseOfMatrix.

Tests: the sigma points reproduce the mean and covariance of the estimate exactly, the mean and variance of x^2 come out exact where the extended filter misses both, a linear model agrees with the extended filter to 1e-9 over 500 steps, and a target seen only as a range is tracked without writing a derivative.

Signed-off-by: alxkm <19151554+alxkm@users.noreply.github.com>
Co-authored-by: alxkm <19151554+alxkm@users.noreply.github.com>

…7624)

Bumps [org.mockito:mockito-core](https://github.com/mockito/mockito) from 5.23.0 to 5.24.0.
- [Release notes](https://github.com/mockito/mockito/releases)
- [Commits](mockito/mockito@v5.23.0...v5.24.0)

---
updated-dependencies:
- dependency-name: org.mockito:mockito-core
  dependency-version: 5.24.0
  dependency-type: direct:development
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

…hub/workflows (#7625)

chore(deps): bump github/codeql-action in /.github/workflows

Bumps [github/codeql-action](https://github.com/github/codeql-action) from 4.38.1 to 4.38.2.
- [Release notes](https://github.com/github/codeql-action/releases)
- [Changelog](https://github.com/github/codeql-action/blob/main/CHANGELOG.md)
- [Commits](github/codeql-action@v4.38.1...v4.38.2)

---
updated-dependencies:
- dependency-name: github/codeql-action
  dependency-version: 4.38.2
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

…ated arrays (#7626)

The old mid-1/mid+1 comparison indexed out of bounds for a 1-2 element
array and never terminated correctly for an unrotated array. Replaced
with a standard binary search for the rotation pivot.

…1.0 (#7627)

Bumps org.apache.commons:commons-lang3 from 3.20.0 to 3.21.0.

---
updated-dependencies:
- dependency-name: org.apache.commons:commons-lang3
  dependency-version: 3.21.0
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

* feat(ciphers): add LWE (Regev) encryption

* test(ciphers): add tests for LWE encryption

---------

Co-authored-by: Oleksandr Klymenko <19151554+alxkm@users.noreply.github.com>

Descend using the same split direction as insert and search, move remaining left-only children to the right of their minimum replacement, and stop traversal once the selected node is handled.

Cover leaf and subtree deletion, nested successors, left-only replacement reuse, missing and final points, and deletion-order reference checks for bulk-built and inserted 1D/2D/3D trees.

Fixes #7632

* feat(ciphers): add HORS few-time signature scheme

* test(ciphers): add tests for HORS signature

* fix(ciphers): require k as a verify parameter in HORS

….0 (#7636)

Bumps [com.puppycrawl.tools:checkstyle](https://github.com/checkstyle/checkstyle) from 14.1.0 to 14.3.0.
- [Release notes](https://github.com/checkstyle/checkstyle/releases)
- [Commits](checkstyle/checkstyle@checkstyle-14.1.0...checkstyle-14.3.0)

---
updated-dependencies:
- dependency-name: com.puppycrawl.tools:checkstyle
  dependency-version: 14.3.0
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

* Add Fenwick tree implementation and tests

* Fix FenwickTree test filename and add documentation link

* test: add white-box unit tests for Luhn.luhnCheck

Cover the loop (zero, one and many iterations), both outcomes of the
`i % 2 == 0` and `temp > 9` decisions, boundary values (8 / 10 after
doubling), valid and invalid checksums, input immutability and null input.

* test: drop null input case flagged by Infer

Infer reports NULLPTR_DEREFERENCE for passing null to luhnCheck on purpose. The method does not document null handling, so the case is removed.

P2QuantileEstimator tracks one quantile chosen in advance, in constant memory. A t-digest keeps a small list of centroids, each a mean and a weight, sorted by mean, and answers any quantile and the CDF afterwards from the same sketch. A centroid may absorb points only while it spans at most one unit of the scale function k(q) = d / (2 pi) * asin(2q - 1), and asin is steep at both ends, so centroids in the tails stay at one or a few points while those near the median are allowed to grow. The rank error is of the order of 1 / d around the median and shrinks towards q = 0 and q = 1, which is the trade latency percentiles want: p99.9 comes out nearly exact from a sketch of a few kilobytes.

Insertions are buffered and folded into the centroid list in batches, so add is O(log d) amortised; quantile and cdf are O(d) and interpolate linearly between centroids, each treated as sitting at the centre of the weight it carries. The minimum and maximum are tracked separately and returned exactly for q = 0 and q = 1. Two digests merge the way partial sums do, so sketches built on separate shards combine into one. Non-finite samples, invalid weights, quantiles outside [0, 1] and a compression below 10 are refused; queries fold the pending buffer in first, so the class is documented as not thread-safe.

Tests: on 100 000 uniform samples every tested quantile lands within 0.01 of the requested rank; on 200 000 Gaussian samples the rank error stays under a bound that narrows towards the tails, from 0.01 at the median to 0.0005 at q = 0.001 and q = 0.999; three shards merged answer within 0.01 of the true rank, with total weight, minimum and maximum exact; the centroid count stays at or below the compression after 200 000 samples for compressions of 20, 100 and 500; and weighted, sorted, constant and heavily duplicated input are covered.

Signed-off-by: alxkm <19151554+alxkm@users.noreply.github.com>
Co-authored-by: alxkm <19151554+alxkm@users.noreply.github.com>

* Add Duval Lyndon factorization

* Test Lyndon factorization

* Handle null input explicitly in Lyndon factorization

* Align null-input test with explicit validation

…hub/workflows (#7645)

chore(deps): bump github/codeql-action in /.github/workflows

Bumps [github/codeql-action](https://github.com/github/codeql-action) from 4.38.2 to 4.38.3.
- [Release notes](https://github.com/github/codeql-action/releases)
- [Changelog](https://github.com/github/codeql-action/blob/main/CHANGELOG.md)
- [Commits](github/codeql-action@v4.38.2...v4.38.3)

---
updated-dependencies:
- dependency-name: github/codeql-action
  dependency-version: 4.38.3
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>