Algorithms.cs

using System;
using System.Collections.Generic;

namespace LabPartIII;

public static class Algorithms
{
    private static string _pattern = "abcab";

    public static object LinearSum(double[] v)
    {
        double s = 0;
        for (int i = 0; i < v.Length; i++) s += v[i];
        return s;
    }

    public static object CountDistinct(double[] v)
    {
        var set = new HashSet<double>();
        foreach (var x in v) set.Add(x);
        return set.Count;
    }

    public static object MergeSortWrapper(double[] v)
    {
        var arr = (double[])v.Clone();
        MergeSort(arr, 0, arr.Length - 1);
        return arr;
    }

    private static void MergeSort(double[] a, int l, int r)
    {
        if (l >= r) return;
        int m = (l + r) / 2;
        MergeSort(a, l, m);
        MergeSort(a, m + 1, r);
        Merge(a, l, m, r);
    }

    private static void Merge(double[] a, int l, int m, int r)
    {
        int n1 = m - l + 1, n2 = r - m;
        double[] L = new double[n1], R = new double[n2];
        Array.Copy(a, l, L, 0, n1);
        Array.Copy(a, m + 1, R, 0, n2);
        int i = 0, j = 0, k = l;
        while (i < n1 && j < n2)
            a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
        while (i < n1) a[k++] = L[i++];
        while (j < n2) a[k++] = R[j++];
    }

    public static object BubbleSort(double[] v)
    {
        var a = (double[])v.Clone();
        int n = a.Length;
        for (int i = 0; i < n - 1; i++)
        {
            bool swapped = false;
            for (int j = 0; j < n - i - 1; j++)
            {
                if (a[j] > a[j + 1])
                {
                    (a[j], a[j + 1]) = (a[j + 1], a[j]);
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
        return a;
    }

    public static object NaivePower(double[] v)
    {
        if (v.Length == 0) return 1.0;
        double baseNum = v[0];
        int exponent = v.Length;
        double result = 1.0;
        for (int i = 0; i < exponent; i++)
            result *= baseNum;
        return result;
    }

    public static object FastPower(double[] v)
    {
        if (v.Length == 0) return 1.0;
        double baseNum = v[0];
        int exponent = v.Length;
        double result = 1.0;
        double currentBase = baseNum;

        while (exponent > 0)
        {
            if (exponent % 2 == 1)
                result *= currentBase;
            currentBase *= currentBase;
            exponent /= 2;
        }
        return result;
    }

    public static object KMPSearch(string text)
    {
        var pattern = _pattern;
        int m = pattern.Length;
        int n = text.Length;

        if (m == 0) return new List<int>();
        if (n < m) return new List<int>();

        int[] lps = ComputeLPSArray(pattern);

        var matches = new List<int>();
        int i = 0, j = 0;

        while (i < n)
        {
            if (pattern[j] == text[i])
            {
                i++;
                j++;
            }

            if (j == m)
            {
                matches.Add(i - j);
                j = lps[j - 1];
            }
            else if (i < n && pattern[j] != text[i])
            {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i++;
            }
        }

        return matches;
    }

    private static int[] ComputeLPSArray(string pattern)
    {
        int m = pattern.Length;
        int[] lps = new int[m];
        int len = 0, i = 1;

        while (i < m)
        {
            if (pattern[i] == pattern[len])
            {
                len++;
                lps[i] = len;
                i++;
            }
            else
            {
                if (len != 0)
                {
                    len = lps[len - 1];
                }
                else
                {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static object NaiveStringSearch(string text)
    {
        var pattern = _pattern;
        var matches = new List<int>();
        int n = text.Length;
        int m = pattern.Length;

        for (int i = 0; i <= n - m; i++)
        {
            int j;
            for (j = 0; j < m; j++)
                if (text[i + j] != pattern[j])
                    break;
            if (j == m)
                matches.Add(i);
        }
        return matches;
    }

    public static object MatrixMultiplication(int m, int n, Random rand)
    {
        var A = GenerateMatrix(m, n, rand);
        var B = GenerateMatrix(n, m, rand);
        var C = new double[m, m];

        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < n; k++)
                    C[i, j] += A[i, k] * B[k, j];

        return C;
    }

    private static double[,] GenerateMatrix(int rows, int cols, Random rand)
    {
        var matrix = new double[rows, cols];
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                matrix[i, j] = rand.NextDouble();
        return matrix;
    }
}