sbktckp/design-and-analysis-of-algorithms

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.