Skip to content

A pedagogical implementation of common algorithms and data structures

License

Notifications You must be signed in to change notification settings

mwermelinger/m269-library

Repository files navigation

linting: pylint imports: isort code style: black license: MIT

This repo is not yet open for contributions.

This library provides Python implementations of some commonly taught algorithms and data structures (see the sidebar). It was created for M269, the Open University's module on Algorithms, Data Structures and Computability, but is not specific to M269.

The library aims to be pedagogical: simple, readable and documented. It is meant to complement (not replace) the code given in M269 and its textbook, to emphasise that there are many ways of implementing the same algorithms and data structures.

The code aims to follow the official Python coding style, defined in PEP8 and PEP257. In addition, the code only uses full English words in identifiers, i.e. no abbreviations or single letters. The exceptions are: n, x, y, z.

Installation

Make sure you have Python version 3.9 or higher.

Go to the code repository and click on the green 'Code' button to download all files as a single compressed archive. Once downloaded, double-click the archive to extract the files, if your web browser hasn't done so automatically. This will create the M269 Library folder with these subfolders:

  • lib contains the M269 Library
  • examples contains simple applications that use the library
  • docs contains this documentation in HTML format
  • tests contains the test code.

Usage

Put your Python file in the M269 Library folder, i.e. 'above' the lib subfolder. Start your program with, for example, from lib.stack import Stack to use the stack data structure, or from lib.sort import bubble_sort to use the bubble sort algorithm.

You can browse this documentation on your computer by opening file docs/index.html. You can get the same documentation in the Python shell (if run from the M269 Library folder), by typing for example

>>> import lib.stack
>>> help(lib.stack)

There are some suggested exercises at the end of code files. You're welcome to discuss them in the M269 forums and tutorials, unless they are used in the assignments. Please don't post solutions on any public site.

Development

This library was created on Mac OS X with Python 3.6 (Anaconda distribution). In December 2022 I created a virtual environment with the most recent versions:

python3 -m venv venv
source venv/bin/activate
pip install -r requirements-dev.txt

Due to the type annotations, the library requires at least Python 3.9. The library should work on other platforms but they weren't tested.

For each class ADT in file lib/adt.py there is (or will be) a class TestADT in file tests/test_adt.py. The TestADT class has one method setUp and one or more methods test_..., following the unittest framework. The setUp method creates the inputs used by the tests, and each test method tests one method of the ADT class. The setUp method is run before each test method, so that each test can change the inputs without influencing other tests.

Some test files may already be using the pytest framework, which uses simple assert statements and setup_method instead of setUp.

For the example apps, tests follow the doctest framework. Both unit and doc tests are run with pytest.

The documentation is generated with sphinx, using the sphinx-apidoc script to generate an initial set of pages, one per library or example file, in the docsrc folder. The sphinx-build script then generates the HTML files in the docs folder, which is rendered with GitHub Pages.

The code was formatted with black and isort and checked with pylint, flake8 and pydocstyle. File pyproject.toml configures the tools.

About

A pedagogical implementation of common algorithms and data structures

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages