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.
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.
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 learn how to manipulate the PyRat software, and write a simple program to move (slightly better than) randomly;
- In Episode 2, we are alone in the maze, and we learn how to grab a single piece of cheese;
- In Episode 3, 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 4, 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 5, we consider again the objective of Episode 4, sacrificing optimality of the path in the maze, in order to reduce the computation time needed to come up with a solution;
- In Episode 6, we study some concepts of games theory, and start writing a program that can beat an opponent in the maze.
Structure of an Episode
Each PyRat Episode (1-6) is structured as follows:
- Before the scheduled class (which we call Lab), in autonomy, 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:
- A written evaluation (0h10): 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;
- Its correction (~0h10): The teacher will discuss some of the questions in that quiz to clarify the concepts which might have been misunderstood;
- A practical session (~2h00): You will be given time to work on the goal of the Episode, on the PyRat maze game. Here, you will benefit from the help of teachers;
- A quick introduction on the contents of Episode i+1 (~0h10): The teacher will present you briefly the notions of the next Episode.
The practical sessions are made in pairs, that will be made by the teacher at the beginning of Episode 1. These pairs should ideally be composed of students which have more or less the same level of knowledge and skills in computer science.
The evaluation systemevaluation
The color system
The PyRat course gives you the possibility to customize your implication in the course. On the evaluation form, 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;
- Blue: This is the advanced level, which includes more advanced 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 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, etc.). Unlike the green and blue levels, the red level is not assessed in the quizzes. 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.
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.
During the practical session, the teacher will correct the quiz and give it back to you. 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 validate the green question if you manage to do so.
Oral assessments, in episodes 3 and 5, will be conducted in the form of short five-minute 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 works properly;
- The blue level is validated if you can illustrate the strengths and weaknesses of your programs using appropriate tools (statistics, analyses, etc.). 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, etc.) on the performance of your algorithms;
- Use deterministic test cases to verify certain properties;
- Experimentally validate conjectures or intuitions on certain properties of algorithms.
The final presentation
In Episode 7, 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.
The final grade
On the evaluation sheet, all questions are associated with skills, displayed between brackets. Skills are evaluated independently. 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 grade + for a skill and have at least a red box for that skill, it will be evaluated one level higher than normal (see below).
Keep in mind that the teachers may still make some adjustments to valorize some aspects of your work (strong investment, help of other groups, etc.) or penalize some unwanted behavior (stealing codes, cheating in quizes, etc.).
The skills we evaluate
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.
All these skills are evaluated at level N3 (in short, N1 means that you heard about it, and N5 means you are an expert). Note that exceptional work (i.e., what we assess in red) can transform a N3 skill into a N4, which is beneficial for your scholarship (more practically, it has an impact on your GPA).