Catch a single piece of cheese

Duration2h30 + preparation

Presentation & objectives

In this session, we start doing things more intelligently. We are going to learn about graphs, which are data structures that are practical to model a PyRat maze. Then, we will learn about paths on graphs, and study two algorithms that find such paths: the breadth-first search (BFS) algorithm, and the depth-first search (DFS) algorithm. These algorithms are called “traversals”, and will produce a routing table, that can be used to find paths from a cell to another.

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 these two algorithms, so that your character can move from a location to another in the maze, exploiting the knowledge of the maze map.

Before the class

Technical requirements

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

Prior knowledge acquisition

Before arriving in class, you should study the following articles:

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:

TODO

Créer eval sur moodle.

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:

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.