Catch multiple pieces of cheese... more efficiently

Duration2h30 + preparation

Presentation & objectives

In the previous session, you found out that catching all pieces of cheese in a minimum number of actions is a very hard problem to solve. An alternate approach is to use heuristics, i.e., approximate algorithms that will return a solution that is not optimal in general, but sufficiently close to optimal to be acceptable, and that can be computed in a low time. A very classic heuristic is the “greedy” algorithm. Its goal is to approximate the global solution of a problem by a series of locally optimal solutions.

The notions above are covered by a few articles that you have to study before the class. In the practical activity, you will have to approximate a solution to the TSP based on a greedy search.

Important

The content of this session will be evaluated. Check the details at the end of this page.

Before the class

Technical requirements

To be able to start working on the activity, you should meet the following requirements:

Prior knowledge acquisition

To be able to start the practical activity efficiently, we introduced some needed concepts at the end of the previous session. Here are the slides used in class:

These slides only cover the main elements of the course, and many more details are given in the associated articles. Thus, you should study the following articles at home after before the session:

You can verify your understanding of these articles here:

During the class

Quiz

At the very beginning of the session, we start with an evaluated Wooclap quiz to check your understanding of the articles you had to study. The link will be given by the teacher at the beginning of the class. Make sure to be there on time!

Attribute roles

In the previous evaluation, you had to select one role, corresponding to your responsibility in the evaluated deliverable. This time, you have to take a different role. Use the following table to find which is yours:

Your role last time
Your role this time
Code quality Documentation
Documentation Unit tests
Unit tests Code quality

As described at the end of this page, you will have to upload an archive, that includes a README.md file. In this file, you will have to indicate who is responsible of what.

Practical activity

The class is dedicated to a practical activity. Once you are done with all the things above, click on the link below to start:

After the class

Complete the current session

This session is evaluated. The modality of evaluation is described on the project main page. Before the next session, you should thus:

  • Review the contents of the articles above.

  • Complete the non-optional parts of the practical activity.

  • Create an archive named student1_student2_student3.zip, where student1, student2 and student3 are the family names of the members of your group. This archive should be structured as follows:

    student1_student2_student3.zip
|
|_ games
|  |_ # Put your game scripts here
|
|_ players
|  |_ # Put your players here
|
|_ tests
|  |_ # Put your unit tests here
|
|_ utils
|  |_ # Put your additional codes here (if any)
|
|_ data
|  |_ # Put your other files here (if any)
|
|_ README.md

    The README.md should be a text file formatted in Markdown. Download this file to use as a basis, and fill it where asked (replace everything in <...>).

  • The student responsible of the code should upload this archive on Moodle before the start of session 6.

Important

In addition to the quality of the code, the documentation and the unit tests, we will also evaluate your ability to produce a deliverable. In other words, pay attention to the following important elements:

  • We are going to unzip your archive, and use it as a workspace in Visual Studio Code. Your code should work directly, i.e., running a script in the games or tests directories should create a game or perform tests without any intervention on our side. You should ensure that by testing this in a new Visual Studio Code workspace before uploading your code on Moodle.

  • We will evaluate your ability to produce a deliverable according to given directives. Consider that we are a client to which you send a piece of software you had to produce. The name of the archive, the organization of its contents, and the content of the README.md file should match our requirements listed above.

Prepare the next session

  • Check the “Before the class” section of the next session, and make sure you do everything required to prepare it.
  • The next session will start with an evaluated quiz to check that you have understood the articles.