Algebraic

Algebraic Algorithms

This repository contains a collection of solutions to diverse algorithmic and mathematical problems. Each task resides in its own directory (Task_0, Task_1, ..., Task_10) and is self-contained, including source code and a dedicated README with specific details and examples.

Overview

The tasks collectively cover a wide range of topics, including:

• Linear algebra and symbolic computation
• Boolean circuit design
• Finite field and modular arithmetic
• Graph algorithms and probabilistic methods
• Coding theory and combinatorial design
• Spectral graph theory
• Lattice reduction techniques
• Quaternion-based geometric transformations

Structure

Each task is designed as a standalone solution with its own documentation and examples. Each folder includes:

• Source code implementing the solution.
• A README describing the problem statement, constraints, and example usage.

Tasks

Task_0 - Adjugate Matrix without Iteration

Computation of the adjugate matrix of integer matrix using purely algebraic expressions - no iterative loops or division operations allowed.

Task_1 - Parallel Prefix Disjunction Circuit

Design of a parallel prefix (DAG-based) circuit for computing cumulative logical ORs with minimal depth (logarithmic) and optimal gate count.

Task_2 - 3-to-2 Compressor Circuit

Implementation of a logic circuit that compresses three binary numbers into two while preserving their sum, optimized for small depth and circuit size.

Task_3 - Polynomial Factorization over Finite Fields

Factorization of polynomials in $\mathbb{F}_p[x]$ into distinct irreducible components of equal degree, using modular arithmetic and field theory methods.

Task_4 - Perfect Matching Detection (Probabilistic)

Verification of perfect matchings in bipartite graphs using a probabilistic algorithm based on the Lipton–DeMillo–Schwartz–Zippel lemma.

Task_5 - Bose–Shrikhande Code Construction

Generation of Bose–Shrikhande codes of the second type via Paley's Hadamard matrix construction, producing codewords with strong distance properties.

Task_6 - Approximation for Minimum Weighted Vertex Cover

Development of a 2-approximation algorithm for the weighted vertex cover problem using linear programming relaxation and sparse matrix optimization.

Task_7 - Minimum Density Cut via Spectral Approximation

Spectral approach to finding a near-optimal minimum density cut in an undirected graph, leveraging eigenvectors of the graph Laplacian.

Task_8 - $3_{\geq 7/8}$-SAT Approximation

Approximation algorithm for 3-SAT ensuring satisfaction of at least $7/8$ of clauses, using structured homogeneous assignments.

Task_9 - Integer Relation via LLL Reduction

Application of the LLL lattice reduction method to discover integer relations among real numbers with high numerical precision.

Task_10 - Composite 3D Rotation using Quaternions

Analysis and computation of composite 3D rotations using quaternion algebra, determining the final rotation axis, angle, and transformed vector.