# sbktckp/design-and-analysis-of-algorithms architecture

> Architecture diagram of the GitHub repository sbktckp/design-and-analysis-of-algorithms, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-08-03). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/sbktckp/design-and-analysis-of-algorithms
- Repository: https://github.com/sbktckp/design-and-analysis-of-algorithms

## Overview

#### 1. Purpose and Execution Model
This is a C17 algorithms-lab repository: 36 independent command-line programs covering data structures, algorithm design paradigms, graph algorithms, amortization, and file handling. It is not a shared application/library; each numbered `.c` file is a standalone executable with its own `main`.

Primary entry points are the repository orchestrator `run` and root `Makefile`. `./run <question>` selects and executes a full program; `./run compact/<question>` selects its abbreviated counterpart.

#### 2. Repository Organization: Full vs. Compact Implementations
Every lab/assignment directory is a self-contained unit with a local build, documentation, optional input data, full implementations, and a `compact/` alternative. For example:
- `Day 6 - Minimum Cost Spanning Tree/6.1_prim_mst.c`
- `Day 6 - Minimum Cost Spanning Tree/compact/6.1_prim_mst.c`
- `Day 6 - Minimum Cost Spanning Tree/Makefile`

Full versions prioritize robust C practices, dynamic allocation, checked file operations, and appropriate data structures. Compact versions intentionally trade safety and asymptotic efficiency for short, record-book-ready code. They do not form a runtime dependency chain.

#### 3. Build and Launch Boundary
The root build aggregates per-directory Makefiles:
- `Makefile`
- `Day 3 - Divide and Conquer Method/Makefile`
- `Assignment 1 - File Handling/compact/Makefile`

Each local Makefile compiles source files into that directory’s ignored `bin/` output area. The launcher must execute binaries from their owning day directory because programs commonly resolve relative `data/` paths. This working-directory convention is the key runtime boundary between otherwise independent exercises.

Runtime requirements are a POSIX-like shell plus `gcc`/`make`; the stated language target is standard C17. Development-container support is defined in `.devcontainer/devcontainer.json`. No network APIs, databases, or external application services are used.

#### 4. Input, Output, and File-Handling Programs
Programs accept interactive input and/or positional arguments, with local test fixtures under per-topic `data/` folders. File-oriented flows read relative files, transform or analyze content, then print or write results:
- `Assignment 1 - File Handling/1.1_compare_files.c`
- `Assignment 1 - File Handling/1.2_uppercase_convert.c`
- `Assignment 1 - File Handling/data/test.txt`

The launcher forwards arguments after a question identifier, enabling workflows such as source input path to generated output path. Generated files and binaries are excluded from source control.

#### 5. Sequential, Recursive, and Sorting Stages
Early exercises operate over arrays and numeric inputs: traversal, prefix sums, duplicate detection, rotation, decimal conversion, and GCD. Divide-and-conquer implementations provide merge sort and quicksort, including behavior across ordered and random datasets:
- `Day 1 - Revision of Data Structures/1.2_prefix_sum.c`
- `Day 2 - Fundamentals of Algorithmic Problem Solving/2.3_gcd_pairs.c`
- `Day 3 - Divide and Conquer Method/3.1_merge_sort.c`

These are standalone algorithm pipelines: parse input, construct/work over in-memory arrays, emit results.

#### 6. Data-Structure and Greedy Construction
Heap and greedy exercises construct explicit in-memory structures and repeatedly choose or reorder candidates:
- `Day 4 - Heap/4.1_person_heap.c`
- `Day 5 - Greedy Techniques/5.1_fractional_knapsack.c`
- `Day 5 - Greedy Techniques/5.2_huffman_coding.c`

Notably, full versions may use heaps/tree structures where compact versions use fixed arrays or linear selection. This distinction is pedagogical rather than an intermodule API boundary.

#### 7. Graph and Dynamic-Programming Algorithms
Graph programs ingest adjacency matrices or edge lists, then execute canonical optimization flows: Prim/Kruskal produce MSTs, Dijkstra relaxes from one source, and Floyd–Warshall updates all-pairs distances by intermediary vertex. DP programs fill tables bottom-up and reconstruct solutions where applicable:
- `Day 6 - Minimum Cost Spanning Tree/6.2_kruskal_mst.c`
- `Day 7 - Single Source Shortest Path/7.1_dijkstra_shortest_path.c`
- `Day 9 - All Pair Shortest Path/9.1_floyd_warshall.c`

Representative graph-input boundaries are local fixtures such as `Day 6 - Minimum Cost Spanning Tree/data/inEdgeList.dat` and `Day 7 - Single Source Shortest Path/data/inDiAdjMat1.dat`.

Main entry points: [`Day 3 - Divide and Conquer Method/Makefile`](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%203%20-%20Divide%20and%20Conquer%20Method/Makefile) (Directory Makefiles), [`run`](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/run) (run launcher), [`Day 6 - Minimum Cost Spanning Tree/data/inEdgeList.dat`](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%206%20-%20Minimum%20Cost%20Spanning%20Tree/data/inEdgeList.dat) (Local data fixtures), [`Makefile`](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Makefile) (Root Makefile)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_build["Build &amp; Launch"]
  node_toolchain{{"POSIX shell, gcc &amp; make<br/>toolchain"}}
  node_root_make["Root Makefile<br/>build orchestrator"]
  node_launcher["run launcher<br/>CLI dispatcher"]
  node_local_makes["Directory Makefiles<br/>local build rules"]
  node_binaries["Local bin executables<br/>compiled programs"]
  node_devcontainer["Development container<br/>development environment<br/>[devcontainer.json]"]
end

subgraph group_full["Full Standalone Programs"]
  node_full_file["File handling<br/>standalone C program"]
  node_full_array["Array &amp; numeric algorithms<br/>standalone C program<br/>[1.2_prefix_sum.c]"]
  node_full_gcd["GCD pair analysis<br/>standalone C program<br/>[2.3_gcd_pairs.c]"]
  node_full_sort["Divide-and-conquer sorting<br/>standalone C program<br/>[3.1_merge_sort.c]"]
  node_full_structures["Heap &amp; greedy algorithms<br/>standalone C program<br/>[4.1_person_heap.c]"]
  node_full_graph["Graph optimization<br/>standalone C program<br/>[6.2_kruskal_mst.c]"]
  node_full_apsp["All-pairs shortest path<br/>standalone C program"]
end

subgraph group_compact["Compact Alternatives"]
  node_compact_sources["Compact program variants<br/>standalone C programs<br/>[6.1_prim_mst.c]"]
  node_compact_make["Compact build rules<br/>local build rules"]
end

subgraph group_io["Local Runtime I/O"]
  node_working_dir["Owning exercise directory<br/>runtime boundary"]
  node_fixtures["Local data fixtures<br/>input files<br/>[inEdgeList.dat]"]
  node_cli_input["Interactive input &amp; arguments<br/>runtime input"]
  node_results["Printed or generated results<br/>program output"]
end

node_devcontainer -->|"provides"| node_toolchain
node_toolchain -->|"runs"| node_root_make
node_toolchain -->|"runs"| node_launcher
node_root_make -->|"aggregates"| node_local_makes
node_local_makes -->|"builds full programs"| node_binaries
node_compact_make -->|"builds compact programs"| node_binaries
node_full_file -->|"compiled by"| node_local_makes
node_full_array -->|"compiled by"| node_local_makes
node_full_gcd -->|"compiled by"| node_local_makes
node_full_sort -->|"compiled by"| node_local_makes
node_full_structures -->|"compiled by"| node_local_makes
node_full_graph -->|"compiled by"| node_local_makes
node_full_apsp -->|"compiled by"| node_local_makes
node_compact_sources -->|"compiled by"| node_compact_make
node_launcher -->|"selects and executes"| node_binaries
node_launcher -->|"sets"| node_working_dir
node_working_dir -->|"resolves relative paths"| node_fixtures
node_cli_input -->|"question and forwarded args"| node_launcher
node_cli_input -->|"interactive input"| node_binaries
node_fixtures -->|"read or transformed"| node_full_file
node_fixtures -->|"graph input"| node_full_graph
node_binaries -->|"prints or writes"| node_results

click node_root_make "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Makefile"
click node_launcher "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/run"
click node_local_makes "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%203%20-%20Divide%20and%20Conquer%20Method/Makefile"
click node_full_file "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Assignment%201%20-%20File%20Handling/1.2_uppercase_convert.c"
click node_full_array "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%201%20-%20Revision%20of%20Data%20Structures/1.2_prefix_sum.c"
click node_full_gcd "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%202%20-%20Fundamentals%20of%20Algorithmic%20Problem%20Solving/2.3_gcd_pairs.c"
click node_full_sort "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%203%20-%20Divide%20and%20Conquer%20Method/3.1_merge_sort.c"
click node_full_structures "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%204%20-%20Heap/4.1_person_heap.c"
click node_full_graph "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%206%20-%20Minimum%20Cost%20Spanning%20Tree/6.2_kruskal_mst.c"
click node_full_apsp "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%209%20-%20All%20Pair%20Shortest%20Path/9.1_floyd_warshall.c"
click node_compact_sources "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%206%20-%20Minimum%20Cost%20Spanning%20Tree/compact/6.1_prim_mst.c"
click node_compact_make "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Assignment%201%20-%20File%20Handling/compact/Makefile"
click node_fixtures "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%206%20-%20Minimum%20Cost%20Spanning%20Tree/data/inEdgeList.dat"
click node_devcontainer "https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/.devcontainer/devcontainer.json"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_toolchain,node_root_make,node_launcher,node_local_makes,node_binaries,node_devcontainer toneBlue
class node_full_file,node_full_array,node_full_gcd,node_full_sort,node_full_structures,node_full_graph,node_full_apsp toneAmber
class node_compact_sources,node_compact_make toneMint
class node_working_dir,node_fixtures,node_cli_input,node_results toneRose
```

## Components

### Build & Launch

- **POSIX shell, gcc & make**: toolchain · C17 build and execution environment.
- [Root Makefile](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Makefile): build orchestrator · Aggregates directory-local builds. · `Makefile`
- [run launcher](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/run): CLI dispatcher · Selects a full or compact question and forwards arguments. · `run`
- [Directory Makefiles](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%203%20-%20Divide%20and%20Conquer%20Method/Makefile): local build rules · Compile each self-contained exercise into its local bin directory. · `Day 3 - Divide and Conquer Method/Makefile`
- **Local bin executables**: compiled programs · Ignored outputs owned by each exercise directory.
- [Development container](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/.devcontainer/devcontainer.json): development environment · `.devcontainer/devcontainer.json`

### Full Standalone Programs

- [File handling](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Assignment%201%20-%20File%20Handling/1.2_uppercase_convert.c): standalone C program · Reads, transforms, compares, or writes local files. · `Assignment 1 - File Handling/1.2_uppercase_convert.c`
- [Array & numeric algorithms](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%201%20-%20Revision%20of%20Data%20Structures/1.2_prefix_sum.c): standalone C program · Parses input, processes in-memory arrays, and prints results. · `Day 1 - Revision of Data Structures/1.2_prefix_sum.c`
- [GCD pair analysis](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%202%20-%20Fundamentals%20of%20Algorithmic%20Problem%20Solving/2.3_gcd_pairs.c): standalone C program · `Day 2 - Fundamentals of Algorithmic Problem Solving/2.3_gcd_pairs.c`
- [Divide-and-conquer sorting](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%203%20-%20Divide%20and%20Conquer%20Method/3.1_merge_sort.c): standalone C program · `Day 3 - Divide and Conquer Method/3.1_merge_sort.c`
- [Heap & greedy algorithms](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%204%20-%20Heap/4.1_person_heap.c): standalone C program · Full variants use dynamic structures where appropriate. · `Day 4 - Heap/4.1_person_heap.c`
- [Graph optimization](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%206%20-%20Minimum%20Cost%20Spanning%20Tree/6.2_kruskal_mst.c): standalone C program · Consumes matrices or edge lists for MST and shortest-path algorithms. · `Day 6 - Minimum Cost Spanning Tree/6.2_kruskal_mst.c`
- [All-pairs shortest path](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%209%20-%20All%20Pair%20Shortest%20Path/9.1_floyd_warshall.c): standalone C program · Updates a distance matrix by intermediary vertex. · `Day 9 - All Pair Shortest Path/9.1_floyd_warshall.c`

### Compact Alternatives

- [Compact program variants](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%206%20-%20Minimum%20Cost%20Spanning%20Tree/compact/6.1_prim_mst.c): standalone C programs · Short alternatives with simplified safety and data-structure choices. · `Day 6 - Minimum Cost Spanning Tree/compact/6.1_prim_mst.c`
- [Compact build rules](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Assignment%201%20-%20File%20Handling/compact/Makefile): local build rules · `Assignment 1 - File Handling/compact/Makefile`

### Local Runtime I/O

- **Owning exercise directory**: runtime boundary · Programs run here so relative data paths resolve correctly.
- [Local data fixtures](https://github.com/sbktckp/design-and-analysis-of-algorithms/blob/main/Day%206%20-%20Minimum%20Cost%20Spanning%20Tree/data/inEdgeList.dat): input files · Per-topic files used by file and graph exercises. · `Day 6 - Minimum Cost Spanning Tree/data/inEdgeList.dat`
- **Interactive input & arguments**: runtime input
- **Printed or generated results**: program output · Generated files are not source-controlled.

## Connections

- Development container → POSIX shell, gcc & make: provides
- POSIX shell, gcc & make → Root Makefile: runs
- POSIX shell, gcc & make → run launcher: runs
- Root Makefile → Directory Makefiles: aggregates
- Directory Makefiles → Local bin executables: builds full programs
- Compact build rules → Local bin executables: builds compact programs
- File handling → Directory Makefiles: compiled by
- Array & numeric algorithms → Directory Makefiles: compiled by
- GCD pair analysis → Directory Makefiles: compiled by
- Divide-and-conquer sorting → Directory Makefiles: compiled by
- Heap & greedy algorithms → Directory Makefiles: compiled by
- Graph optimization → Directory Makefiles: compiled by
- All-pairs shortest path → Directory Makefiles: compiled by
- Compact program variants → Compact build rules: compiled by
- run launcher → Local bin executables: selects and executes
- run launcher → Owning exercise directory: sets
- Owning exercise directory → Local data fixtures: resolves relative paths
- Interactive input & arguments → run launcher: question and forwarded args
- Interactive input & arguments → Local bin executables: interactive input
- Local data fixtures → File handling: read or transformed
- Local data fixtures → Graph optimization: graph input
- Local bin executables → Printed or generated results: prints or writes