Course presentation

Welcome to the Algorithmics and Discrete Mathematics course website, a.k.a. PyRat. This course is intended for the 1st year students of IMT Atlantique. You will find here all the materials associated with the different lessons (which we call Episodes) of the course. Additionally, here are the slides that are presented to you during the starting meeting.

PyRat is a course of algorithmics and graph theory, structured around a maze game, in which you program a character (a rat or a python) to go grab pieces of cheese faster than an opponent.

Example of a PyRat game, in which the rat is one of the program you will learn to produce in this course, and in which the snake is an opponent.

This is obviously not an easy objective. Therefore, we will achieve this goal by reaching smaller objectives of gradually increasing difficulty:

  • In Episode 1, we guide you through the installation of the PyRat software, and remind you some basic Python elements;
  • In Episode 2, we write a simple program to move (slightly better than) randomly in the maze;
  • In Episode 3, we are alone in the maze, and we learn how to grab a single piece of cheese;
  • In Episode 4, we are still alone in the maze, and there is still only one piece of cheese to grab, but we now add mud in the maze, that slows down the character;
  • In Episode 5, we are still alone in the maze, but there are now multiple pieces of cheese. We learn how to grab them all in a minimum number of moves;
  • In Episode 6, we consider again the objective of Episode 5, sacrificing optimality of the path in the maze, in order to reduce the computation time needed to come up with a solution;
  • In Episode 7, we put a second player in the maze! We present you a possible direction for writing an interesting AI for PyRat to beat them, based on more advanced notions;
  • In Episode 8, you develop your own personal and unique AI for PyRat to win the tournament!

Episode 9 is different from the other ones. In this last episode, you will have to present your choices of strategies to beat your opponents in the final PyRat tournament!

Calendar of the course

As introduced previously, the PyRat course consists of 9 Episodes. Typically, the structure of an Episode (2-7) is as follows:

  • Before the scheduled class (which we call Lab), you have to study a certain number of articles on the blog, listed on the page of the associated Episode;
  • Then, each Lab contains the following elements:
    • An evaluated quiz (10mn): The beginning of each Lab will be devoted to a quiz. The aim is not to trap you, but to check that you have acquired the different notions covered in the articles to start the Lab efficiently;
    • A practical session (2h20): You will be given time to work on the Lab, on the PyRat maze game. Here, you will benefit from the help of teachers;
    • A correction of the quiz (10mn): The teacher will then go through the blue questions of the quiz to give a correction (see below for more details on the color system);
    • A quick overview of the next episode (5mn): The teacher will present you briefly what you have to work on for next time.

The practical sessions are made in pairs. You will have to choose a partner during Episode 1. Make sure you pair with someone of approximately the same level in computer science as you (otherwise, one student may end up being overloaded and the other being abandoned).

The evaluation system

The color system

The PyRat course gives you the possibility to customize your implication in the course. On the evaluation sheet below, three different colors are used, to indicate the level associated with each evaluation criterion:

  • Green: This is the minimal level, which every student must understand / be able to apply in order to validate the course. These green concepts will be evaluated in quizzes, and their implementation will be evaluated during two oral interviews, as well as in the final presentation;
  • Blue: This is the advanced level, which includes more complex notions than the green level, but that any student taking the course should be able to assimilate. These notions will also be evaluated during the quizzes and oral assessments, and will allow the students to reach an above-average score;
  • Red: The red level is the most open. It is for students who want to explore other topics than those presented in the website (Wikipedia articles, research papers…). Unlike the green and blue levels, the red level is not assessed in the quizzes or interviews. However, during the final presentation, the efforts of the students to deepen their knowledge and skills will be evaluated.

You will encounter these colors on the blog too. Obviously, there is a correspondence between colors on the blog and what we will assess.

evaluation

Quizzes

The purpose of the quizzes at the beginning of each Lab is to help you to assimilate the concepts that we consider essential, and to guarantee you have the tools to achieve the goals of each Episode.

Each quiz will include both green and blue level questions. All questions will be grouped in pairs (one green, one blue), corresponding to a skill we want to assess. You have to answer correctly to the green question for the blue to be counted in the grade. If your answer to the green question is wrong, the points associated with the blue question of the pair will be dropped, even if it was correct.

Quizzes will be held on Moodle, and will open at the start of the Lab session. 20mn later, the results will be available. If you failed a green question, you have a second chance. You will be given some time to understand why you were wrong (you can check all documents you want or ask a friend to explain to you). The teacher will then ask you to explain (not just correct) your mistake, and will retro-validate the green question if you manage to be convincing.

Remark: If you validate a green question using the second chance system, the associated blue question will not be counted, even if it was correct right from the start.

Oral evaluations

Oral assessments, in Episodes 4 and 6, will be conducted in the form of short 5mn interviews with each team. These interviews are opportunities for you to present to the teacher the in-depth studies you have carried out. Note that the color system also applies to these oral evaluations.

  • The green level is validated if you are able to present your implementation of the algorithms, if your code respects the conventions studied in the first Episode, and if the programs work properly;
  • The blue level is validated if you can illustrate the strengths and weaknesses of your programs using appropriate tools (statistics, analyses…). To help you to achieve the blue level during these evaluations, here are some ideas:
    • Compare your algorithms with other algorithms found on the Internet or elsewhere (don’t forget to cite your sources);
    • Look at the impact of maze parameters (configuration, size…) on the performance of your algorithms;
    • Use deterministic test cases to verify certain properties;
    • Experimentally validate conjectures or intuitions on certain properties of algorithms.

As for quizzes, if you fail to validate a green criterion in an oral evaluation, you have the opportunity to validate it later, during the next oral interview, or in the final presentation. To do so, you should include in that next presentation some elements to show you have performed the needed work to validate the missing green box.

The final presentation

In Episode 9, you are asked to prepare a 10mn oral presentation, followed by 5mn of questions.

You will be evaluated on multiple aspects, including the quality of your slides, the clarity of your presentation, but also the originality of your ideas. The list of evaluated elements can be found in the evaluation sheet above.

As the final presentation occurs in the last Episode, you will not have the opportunity to save some missing green evaluated items there. Therefore, make sure you integrate all necessary elements in your presentation.

The final grade

The skills we evaluate

On the evaluation sheet, all questions are associated with skills, displayed between brackets. The various skills that will be evaluated in the PyRat courses are the following:

  • [CST1] (2 tokens): Analyze, reformulate, structure;
  • [CST2] (1 token): Make decisions;
  • [CST18] (1 token): Promote your skills and results;
  • [INFOS] (2 tokens): Formalize a problem and specify a need;
  • [INFOD] (2 tokens): Realize and validate a piece of software.

The final grade (– / = / +) for a skill is defined as follows:

  • Grade –: You get this grade if some green boxes associated with the skill are left unchecked;
  • Grade =: You get this grade if 100% of the green boxes associated with the skill are checked;
  • Grade +: You get this grade if you achieve grade = and have at least 2/3 of the blue boxes associated with the skill checked;
  • Finally, if you validate the course with A grade and have at least a red box for a skill, you will have an A+ grade.

Keep in mind that the teachers may still make some adjustments to valorize some aspects of your work (strong investment, help to other groups…) or penalize some unwanted behavior (stealing codes without acknowledgment, cheating in quizzes…).

Validating the course

The PyRat course itself is validated if you validate at least 4 skills from the list above, and have a total of at least 7 tokens.