C++ Structures & Algorithms Showcase

This repository is a curated collection of C++ projects, each demonstrating a fundamental concept in data structures and algorithms. The entire collection is managed by a powerful, self-contained CMake build system that automatically discovers, compiles, and configures tests for each algorithm.

The programs are designed as standard command-line applications that read from standard input and write to standard output, making them easy to test and integrate with other tools.

For more background and code I/O, see: Design and Analysis of Algorithms - rsiddiq.com.

---

📦 Prerequisites

• CMake ≥ 3.25

• C++20 compiler

  • Windows: Visual Studio 2022 (MSVC)
  • macOS: Apple Clang (Xcode CLT)
  • Linux: GCC 12+ or Clang 15+

• No third-party libraries required.

---

📁 Project Structure

Structs_And_Algos/
├─ CMakeLists.txt
├─ README.md
├─ CoinMatrix/
│  ├─ main.cpp
│  ├─ input00.txt  input01.txt  input02.txt  input03.txt
│  └─ output00.txt output01.txt output02.txt output03.txt
├─ FloydMatrix/
│  ├─ main.cpp
│  ├─ input00.txt  input01.txt  input02.txt  input03.txt
│  └─ output00.txt output01.txt output02.txt output03.txt
├─ HashProbe/
│  ├─ main.cpp
│  ├─ input00.txt  input01.txt  input02.txt  input03.txt
│  └─ output00.txt output01.txt output02.txt output03.txt
├─ HeapOps/
│  ├─ main.cpp
│  ├─ input00.txt  input01.txt  input02.txt  input03.txt
│  └─ output00.txt output01.txt output02.txt output03.txt
├─ NearestNeighbor/
│  ├─ main.cpp
│  ├─ input00.txt  input01.txt  input02.txt  input03.txt
│  └─ output00.txt output01.txt output02.txt output03.txt
├─ SignSort/
│  ├─ main.cpp
│  ├─ input00.txt  input01.txt  input02.txt  input03.txt
│  └─ output00.txt output01.txt output02.txt output03.txt
├─ SymmetryScan/
│  ├─ main.cpp
│  ├─ input00.txt  input01.txt  input02.txt  input03.txt
│  └─ output00.txt output01.txt output02.txt output03.txt
├─ TopoSort/
│  ├─ main.cpp
│  ├─ input00.txt  input01.txt  input02.txt  input03.txt
│  └─ output00.txt output01.txt output02.txt output03.txt
├─ TSP_PathFinder/
│  ├─ main.cpp
│  ├─ input00.txt  input01.txt  input02.txt  input03.txt
│  └─ output00.txt output01.txt output02.txt output03.txt
└─ ZipSeq/
   ├─ main.cpp
   ├─ input00.txt  input01.txt  input02.txt  input03.txt
   └─ output00.txt output01.txt output02.txt output03.txt

---

🚀 How to Build and Test

The entire build process is handled by CMake and is designed to be simple and consistent across all platforms.

Step 1: Configure the Build

First, create a build directory. This keeps all compiled files separate from your source code.

cmake -S . -B build

Step 2: Compile the Code

Next, run the build command. This will compile all the algorithm executables.

cmake --build build

(On Visual Studio, you can specify a configuration like Debug or Release by adding --config Debug)

Step 3: Run the Tests

Finally, execute the tests. The build system includes a custom check target that automatically runs all tests with the correct configuration.

cmake --build build --target check

This command will run all executables against their corresponding input*.txt files and verify that the output matches the output*.txt files.

---

One-liner (VS):

cmake -S . -B build; cmake --build build --config Debug; ctest --test-dir build -C Debug --output-on-failure

One-liner (Ninja/Make):

cmake -S . -B build -G Ninja -DCMAKE_BUILD_TYPE=Debug && cmake --build build -j && ctest --test-dir build --output-on-failure

• Filter by subproject:

  # e.g., Floyd
  ctest --test-dir build -C Debug -R "^FloydMatrix__"

• Single case:

  ctest --test-dir build -C Debug -R "^CoinMatrix__input00.txt$" -VV

Tests feed each input*.txt file to the program’s stdin and assert a successful exit.

---

▶️ Run a program manually

# macOS/Linux
./build/CoinMatrix < CoinMatrix/input00.txt

# Windows (PowerShell)
Get-Content CoinMatrix/input00.txt | .\build\Debug\CoinMatrix.exe

---

🔬 Algorithm & Sub-Project Details

Each sub-project implements a specific algorithm. Here is a detailed breakdown of each one:

Sub-Project	Algorithm / Data Structure	Description
CoinMatrix	Dynamic Programming	Solves the classic "coin matrix" problem by finding the path through a 2D grid of numbers that yields the maximum possible sum.
FloydMatrix	Floyd-Warshall Algorithm	An efficient algorithm for finding the shortest paths between all pairs of vertices in a weighted, directed graph.
HashProbe	Hash Table with Linear Probing	Demonstrates the implementation of a hash table, including how to handle hash collisions using the linear probing method.
HeapOps	Binary Heap	Implements the core operations of a binary heap data structure, a specialized tree-based structure that satisfies the heap property.
NearestNeighbor	Divide and Conquer	Finds the pair of points in a set that have the smallest distance between them, using a recursive divide-and-conquer strategy.
SignSort	Array Partitioning	A custom sorting utility that rearranges an array of integers so that all negative numbers precede all positive numbers.
SymmetryScan	Matrix Analysis	A straightforward utility that reads a square matrix and determines whether it is symmetric across its main diagonal.
TopoSort	Topological Sort (Kahn's)	Implements Kahn's algorithm to find a linear ordering of nodes in a directed acyclic graph (DAG), where each node comes before all nodes it points to.
TSP_PathFinder	Brute-Force Permutation	Solves the Traveling Salesperson Problem by generating and evaluating every possible tour (permutation) to find the one with the minimum cost.
ZipSeq	Two-Pointer Merge Algorithm	Efficiently merges two already-sorted arrays into a single, combined sorted array, similar to the merge step in a merge sort.

---

🔧 CMake behavior (what’s automated)

• Auto-discovery: Any subfolder containing a main.cpp becomes an executable target.
• Test harness: For each <Target>/input*.{txt,in,dat,csv}, a per-test CMake script pipes the file to the program’s stdin and fails on non-zero exit.
• Working directory: Tests run in the subproject’s folder (so relative file reads “just work”).
• MSVC friendliness: Uses /W4 /EHsc /permissive- and DLL runtime; non-MSVC uses -Wall -Wextra -Wpedantic.

---

🧰 Tips & Troubleshooting

• Visual Studio: Always pass -C Debug (or Release) to ctest.

• Parallel builds: cmake --build build -j (or set CMAKE_BUILD_PARALLEL_LEVEL).

• Line endings: Inputs are plain text; CRLF vs LF is fine (programs read via std::cin).

• Clean build: If you change CMake logic, blow away the build folder and reconfigure:

  rm -rf build && cmake -S . -B build