DiscreteU

A C++ discrete mathematics library written during my second semester of computer science. It implements core mathematical structures and algorithms from scratch without relying on Standard Template Library (STL) containers.

---

Overview

This repository contains implementations of foundational concepts covered in undergraduate Discrete Mathematics, coupled with low-level manual memory management and object lifecycle techniques in C++.

Instead of using standard containers like std::vector, std::queue, or std::set, each data structure is implemented using raw dynamic arrays (new and delete[]). All managing structs implement Resource Acquisition Is Initialization (RAII) and the Rule of Three (destructor, copy constructor, and copy assignment operator) to ensure memory safety.

---

Modules

The library is organized into six functional modules:

Module	Source Files	Key Features
Logic	logic.h, logic.cpp	Truth table generation ($2^n$ rows), boolean connectives (implies, biconditional, nand, nor, xor, xnor), tautology and contradiction checks.
Sets	sets.h, sets.cpp	Dynamic sets with 2x growth, set operations (union, intersection, difference, symmetric difference, complement), subset checks, power sets via bitmasks, Cartesian products.
Combinatorics	combinatorics.h, combinatorics.cpp	Factorials, permutations, combinations, Pascal's triangle, special sequences (Fibonacci, Catalan, Bell, Stirling numbers of the second kind, derangements), permutation and combination generation.
Number Theory	number_theory.h, number_theory.cpp	Euclidean and Extended Euclidean algorithms, LCM, divisor analysis, $6k \pm 1$ primality check, Sieve of Eratosthenes, prime factorization, modular exponentiation, modular inverse, Euler's totient, Chinese Remainder Theorem.
Relations	relations.h, relations.cpp	2D boolean relation matrices, relation properties (reflexive, irreflexive, symmetric, antisymmetric, transitive, equivalence, partial order), reflexive/symmetric/transitive closures (Warshall's algorithm), composition.
Graph	graph.h, graph.cpp	Adjacency list representation, dynamic queue ring buffer, BFS and DFS traversals, unweighted shortest path and path reconstruction, bipartite checking (2-coloring), Eulerian path/circuit checks, topological sorting (Kahn's algorithm).

An umbrella header, discreteU.h, is provided to include all modules simultaneously.

---

Directory Structure

DiscreteU/
├── docs/
│   └── implementation_notes.md  # Detailed design and implementation documentation
├── combinatorics.cpp
├── combinatorics.h
├── discreteU.h                  # Umbrella header including all module headers
├── graph.cpp
├── graph.h
├── logic.cpp
├── logic.h
├── main.cpp                     # Test suite and demonstration runner
├── number_theory.cpp
├── number_theory.h
├── relations.cpp
├── relations.h
├── sets.cpp
├── sets.h
├── LICENSE                      # MIT License
└── README.md

---

Building and Running

Prerequisites

• A C++17 compatible compiler (g++ 8+ or clang++ 7+)
• Standard make or a terminal shell

Compilation

To compile the test suite with all modules enabled:

g++ -std=c++17 -Wall -Wextra -o discrete_u main.cpp logic.cpp sets.cpp combinatorics.cpp number_theory.cpp relations.cpp graph.cpp

Running

Execute the compiled binary:

./discrete_u

The output demonstrates each module in sequence, displaying computed truth tables, set relations, combinatorial counts, number-theoretic results, relation matrices, and graph traversals.

---

Memory Management

Every dynamic data structure in this project manages its own heap memory:

• Destructors release buffers with delete[].
• Copy Constructors perform deep copies of dynamic buffers.
• Copy Assignment Operators handle self-assignment, deallocate old memory, and allocate new buffers with deep copies.

For a detailed analysis of the memory layout, algorithm choices, and retrospective design trade-offs, see docs/implementation_notes.md.

---

License

This project is licensed under the MIT License. See the LICENSE file for details.