Catch a single piece of cheese

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:

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

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:

• Addressing a computational problem.
• Graphs & paths.
• Representing graphs.
• Graph traversal.
• Routing tables.
• Queuing structures for graph traversals.

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.