Source Code

This page describes how to obtain, build, and test the C source code that accompanies each algorithm¹. Working with the code isn’t a hard requirement for comprehension of this content. However, it’s highly recommended. The content and source code are synergistic. Perusing prose and pseudocode generates conceptual understanding and working with source code builds applied skill which in turn enriches conceptual understanding.

graph LR
    YOU([fas:fa-user])
    STUDY([fas:fa-book Study])
    CON([fas:fa-brain Concepts])
    APP([fas:fa-sign-language Application])
    SKILL([fas:fa-cogs Skill])

    YOU-->STUDY-->CON-->APP-->SKILL-->CON
    CON-->STUDY

It bears to reason that aspirations and time commitments vary. Therefore, listed below are some viable approaches in regard to the source code. You should adopt the approach that best aligns with your goals and availability.

1. Ignore the code. While you’ll no doubt learn a great deal, it’s safe to say that you won’t master the content using this approach.
2. Read the code. This will give you a sense of the divergence between the real and purely theoretical worlds; however, it will not facilitate skill building.
3. Experiment with the code. Thoroughly scrutinize the supplied source code, modify it and try to predict outcomes. This will provide a visceral connection to the concepts and deepen comprehension; however, pupils using this approach may find it difficult to apply algorithms to other contexts.
4. Write your own code. Implement each algorithm in your language of choice using the supplied source code as a “measuring stick” by which to evaluate your implementations. This approach is by far the best way to achieve the skills required to apply algorithms to real-world contexts.

If you chose approach 1 or 2, feel free to skip the rest of this page as well as the Style Guide page because everything you need is available via your browser. Those choosing options 3 and 4 should continue on to learn how to configure a suitable development environment.

PRO TIP: As a bear minimum, all software project should contain build and development environment documentation. This page and the Style Guide page are suitable templates. Make sure this is among your first tasks when setting up a new project.

Operating System

Conceivably, the supplied source code should build and run on any OS capable of hosting the tools outlined in the next section. However, it has only been verified with those listed below.

• Ubuntu 21.04 (Hirsute Hippo)
• Ubuntu 22.04 (Jammy Jellyfish)
• Windows Subsystem for Linux 2 (WSL2)

One of these Operating Systems are recommended; however, users have reported success using Windows PowerShell and various versions of macOS. As a consideration, deviating from the recommendation may require modification of the supplied automation scripts².

Development Tools

There are two local development environment options: containerized³ or configured. The containerized environment option requires much less setup but is more difficult to integrate with a code editor. Either approach is viable. The tables below outline the required tools for both options.

Containerized Environment⁴

Configured Environment

Instructions for setting up the tools is out of scope. Consult the provided links for more information. Alternatively, the included Dockerfile documents how to configure the tools on Ubuntu 22.04.

Finally, you will need a code editor. VIM⁷, Visual Studio Code, and CLion are all popular alternatives. Feel free to use absolutely any editor that you are comfortable with.

Obtaining the Source Code

All the code is located within a single GitHub Repository. Use the bash command below to clone it to your local machine.

git clone https://github.com/dalealleshouse/algorithms.git

The general layout of the repository is shown below⁸.

algorithms/
├── src
│   ├─── [algorithm type]       <- Related algorithms/data structures are grouped into folders
│   │   ├── test_data           <- Optional: folder to hold test data
│   │   │   └── ...
│   │   ├── algo_timer.c        <- Optional: records algorithm execution time with various input sizes
│   │   ├── compare_times.py    <- Optional: arranges data generated by algo_timer.c into charts and tables
│   │   ├── time_charts.sh      <- Automation script for exercising compare_times.py
│   │   ├── [algorithm].c       <- Each algorithm/data structure has one or more dedicated c and header file
│   │   ├── [algorithm].h
│   │   └── [algorithm]_test.c  <- Unit tests files are postfixed with _test
│   └── test_runner.c           <- Coordinates all unit tests
├── .clang-format               <- clang-format configuration file
├── .clang-tidy                 <- clang-tidy configuration file
├── CPPLINT.cfg                 <- cpplint configuration file
├── Dockerfile                  <- Docker build file that specifies the container
├── Makefile                    <- Specifies build parameters
├── build_container.sh          <- Script to build container
├── ci_validate.sh              <- Script executed by the CI server to validate project
├── compile_commands.json       <- Compalation database required for code editor integration and tooling support
├── coverage.sh                 <- Creates a unit test coverage report
├── llvm-gcov.sh                <- Script required by gcov for coverage report
├── prof.sh                     <- Prints gprof performance profile report to stdout
├── run_c.sh                    <- Automation script for executing build/test commands inside the container
├── validate.sh                 <- Runs all validation checks required for code commit
├── validate_format.py          <- Automation script that validates code formatting
└── watch.sh                    <- Watchs source files and run tests when any file changes

Building and Testing

The configured build and test tasks are listed in the table below. Please attempt to run each of them to ensure your system is configured properly⁹. Make sure to execute each bash command from the repository’s root directory and run make clean in between each task to alleviate caching problems.

The clang undefined behavior sanitizer is enabled for all builds except release. It may seem anomalous that each sanitizer has a separate build; however, it’s not technically possible to use the memory, thread, and address sanitizers together. Sanitizers work by instrumenting code and reporting errors during runtime. This is why the unit tests must be run separately for each build. The tests run automatically after build for convenience¹².

Validating the Code

C is an exceptionally powerful language. However, as the Peter Parker principle attests, “with great power come great responsibility”¹³. It’s easy to do something heinously unnatural with C without even knowing it. All languages have idiosyncrasies; however, C’s are particularly prolific. Automated validation¹⁴ is the most effective stop gap for common errors. For this project, automated validation is achieved via four primary means:

1. Static Analysis: Analyse code, without running it, for common error and security problems
   • Tooling: clang-tidy
2. Linting¹⁵: Analyse code for stylistic issues (more on this on the Style Guide page).
   • Tooling: cpplint
3. Unit Tests: Manually written executable tests that verify run-time functionality.
   • Tooling: CUnit
4. Dynamic Analysis: Analyze code for errors and security problems by instrumenting and running it.
   • Tooling: Clang Sanitizers
     • Memory Sanitizer
     • Thread Sanitizer
     • Address Sanitizer
     • Undefined Behavior Sanitizer

The graphic below illustrates all the validation steps that the source code must endure before acceptance of a commit. The previous section has instructions for initiating validation.

PRO TIP: It’s not reasonable to expect developers to remember corner cases and idiosyncrasies. Every project, regardless of language, should have an easy and fast means of validation. This project serves as an acceptable template.

Implementation Quality

This project makes every attempt to demonstrate best practices for C development. It can act as a reasonable starting point for any DevOps enabled production development effort. However, as a disclaimer, this is NOT production hardened code. Before using C in production scenarios, please preform additional research to ensure the safety of your implementation.

Below are some known likely shortcomings, depending on your context.

• There isn’t a production build that excludes test code. This step was purposely omitted because it’s not a requirement.
• There is only one level of testing. Productions scenarios would also utilize integration, end-to-end, and performance tests.
• Several of the implementations utilize recursion. Recursion provides an elegant means of demonstrating algorithms; however, it causes stack overflow exceptions when the input is sufficiently large¹⁶. For many purposes, this is not an issue; however, use in production scenarios should be thoroughly scrutinized.
• The C code makes extensive use of the rand()¹⁷ function without seeding (srand()). This ensures that the actual run time comparisons between algorithms using random data use the exact same inputs.
• There is little to no thought given to C code portability. It is assumed that it will always run in the supplied container on a 64-bit machine.

Actual Run Times

Where appropriate, actual run time data is provided in order to demonstrate the temporal impact of algorithm and data structure choices. This is instrumental for comprehension of asymptotic complexity. The data is generated by two code files, which are located within each target algorithm’s directory¹⁸.

1. algo_timer.c: Determines the run time incurred by performing operations with various input sizes.
2. compare_times.py: Arranges data generated by algo_timer.c into charts and tables

All run time data shown on this site¹⁹ was collected using a container running on a Surface Book 2 Laptop (Intel Core i7, 16 GB RAM). In order to generate the data on your own machine, execute the following commands from the repository’s root directory:

mkdir run_time_data
./run_c.sh "make clean"
./run_c.sh "make shared"
./run_c.sh "python3 <path to target algorithm directory>/compare_times.py"

It may take up to two hours to generate the data. The charts and tables will output to the run_time_data directory created with the first command.

WARNING: It’s easy to erroneously interpret the nuanced meaning of run time charts. It’s highly recommended that you fully grasp Asymptotic Analysis before attempting to decipher the charts.

Pull Requests

I will happily accept pull request that meet the following criteria:

1. The request is made against the dev branch
2. There are associated unit tests
3. ci_validate.sh executes without error

If I accept your pull request, I will provide proper attribution on this site.

Key Takeaways

• Writing code deepens one’s conceptual understanding of algorithms and data structures.
• To get started, clone the code from GitHub to your local machine:

    git clone https://github.com/dalealleshouse/algorithms.git
  

• There are two development options: configuring your own environment or using the supplied containerized environment. Set up the tools for whichever option works best for you.
• All build and test instructions are listed here
• The code is validated via linting, static analysis, unit tests, and dynamic analysis. All validation checks must pass in order to submit a commit.
• It’s quick and easy to repeatably validate the code using the supplied validation scripts.

    # configured environment
    ./validate.sh
  
    # containerized environment
    ./ci_validate.sh