Catch multiple pieces of cheese

Presentation & objectives

In this session, we significantly increase the difficulty, by considering mazes with multiple pieces of cheese. The objective will be to catch them all, in a minimum number of turns. To do so, we will introduce a problem called the “Traveling Salesman Problem (or “Traveling Salesperson Problem”, TSP for short). We will see that this problem is very complex to solve, and that you cannot expect to do it in an acceptable time for large quantities of cheese.

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 program a solution to the TSP based on an exhaustive search. This will allow you to grab all pieces of cheese in a minimum number of turns.

Before the class

Technical requirements

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

• Please bring your own computer.
• Make sure to have a functional network connection.

Submit your deliverable

Don’t forget, you have to submit your deliverable for session 3 before the start of this session!

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:

• Slides of the session.

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:

• Algorithm complexity.
• The traveling salesman problem.
• Bruteforce and backtracking to solve NP-complete problems.
• Problem complexity & NP-completeness.

You can verify your understanding of these articles here:

• Self-assessment quiz.

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:

• Evaluated quiz.

Practical activity

The class is dedicated to a practical activity. When the quiz is over, go sit with your group, and click on the link below to start:

• Practical activity.

After the class

Complete the current session

Before the next session, you should:

• Review the contents of the articles above.
• Complete the non-optional parts of the practical activity.

Prepare the next session

Also, you should:

• 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.