Sorbonne Université
Department of Computer Science
Academic Year 2018/19
Module: Algorithms (3I003)

Presentation

This repository corresponds to the Algorithms module project. It consists in the theoretical analysis and implementation of three algorithms to solve a particularisation of the change-making problem. In this project, the problem was to find the least number of jars to fully fill given a confiture quantity and a set of jar capacities. The algorithms used were exhaustive search, dynamic programming and greedy algorithm.

Structure

data

This directory includes primarily the data files of the algorithms performance for various instances of the confiture problem. These files are prefixed by the initials of the correspondig algorithm.

The last two files contain some performance measuring for the greedy algorithm.

examples

The algorithms entries must be three parameters, but they can be generated by formatted text files. This directory contains three instance sets.

img

Here is located the university's logo.

report

This directory comprises the report—written in french—files. The report consists of the complexity analysis of the aforementioned algorithms, and the feasibility study of the greedy algorithm.

src

The algorithms implementation are located here. There are also some useful functions in the tools.py file; the performances mesuring in benchmark.py; the assessment of the practicality of the greedy policy in the gp_feasibility.py; and the script run.py to run the algorithms from instance files.