VE477 Project (part 2)

Description

1 Setup

1.3 Catalog cover

This part of the project is not mandatory and only based on voluntary participations.

The goal of this project being the creation of a catalog it should feature a front page showing the following information: (i) a name, (ii) the course reference, and (iii) the academic year. All the rest of the design is left to your creativity…

You can freely propose covers by uploading a file on Canvas under the assignment “catalog cover” until the Saturday after the final exam. All the submissions will be made available for voting and the one with the most votes will be used as the official cover of the “Algorithm catalog” for the academic year 2020–2021. The designer(s) of the selected cover will be awarded a bonus.

2 Content

The goal being to construct a catalog listing problems together with their algorithmic solutions it is important that they are all treated following a similar pattern.

2.1 Catalog

A LAT_EX template is available on Canvas. For each problem provide:

• A clear and brief description of the problem as well as of its input and complexity;

• Information on where it occurs or example applications;

• Some precise pseudocode of an efficient algorithm solving it;

• Problems featuring a † should be explained with diagrams or graphs rather than pseudocode;

• References where this problems is described, solved, or discussed;

Note that the goal is to be able to refer to the catalog over a long period of time. It is therefore better to provide several links or references, privileging links which are less likely to disappear (scientific articles, books, wikipedia…)

Important instructions regarding the template file:

• Do not change any line in the preamble unless it is to (un)comment the \def\tcbox{} line;

• Define the problem type on the line \pbtype{type};

• Do not include more than one problem per file;

• Name the file after the problem number (e.g. problem12.tex);

• Name extra files to be included (e.g. pictures) after the problem number (e.g. problem12a.jpg, problem12b.jpg, etc.);

• Do not forget to update the label of the L^AT_EX environments (e.g. Algorithm, figure, etc.);

• When a problem features more than one algorithm write a very short paragraph listing them. Then study each of them sequentially, i.e. complete the presentation of the first one before getting to the description of the second one.

Note: this also requires some manual adjustments to the L^AT_EX labels (\label{alg:11a}, and \label{alg:11b} if a problem features two algorithms);

Failing to comply with the above requirements will lead to a −10% deduction.

2.2 Implementation

For part 1 and 2 of the project the submissions can feature some optional implantations of the studied algorithms. If they respect the following requirements they can bring a large bonus on the project. The implementation

• Must be completed in Python;

• Should take advantage of the specifics of python to achieve better efficiency, cleaner, or more compact code (e.g. lambda functions, decorators, iterators, generators, polymorphism, etc.)

• Should not be a straight-forward rewriting of the algorithm described in the catalog;

• Must be presented during the lab and feature clear explanations regarding what Python specifics were used and why;

Remark: no bonus will be granted if a work is of low quality (e.g. bad coding style or quality, too simple, etc.)

2.3 References

It is of a major importance to include references for each task. Whether writing for the catalog of implementing a work should never be a verbatim copy of any original content.

For the catalog a work is expected to take the form of a summary or a paraphrasing. Never should it be a direct copy of an original content. Not doing so will automatically conduct its author to face the Honor Council. Similarly changing the name of a few variables or adding comments to an available code will be counted as an Honor Code violation.

3.2 Combinatory

Easy to study:

7