This project is about graph theory problem and pathfinding problem. See the course to find the correct model.
15 hours (during 5 classes) 2 students per team Please take your time on both quality and contents Associate professor and assistant professors will not answer questions about the project. |
Scale: 50 points
- 10 points
- 10 points
- 15 points
- 15 points
“Just follow me and run like your life depends on it. Because it does.”
Task 1: To form the teams
The number of Gladers grows up from day to day. Your leadership role is challenged and your authority is being questioned. Moreover, you are still locked in the Glade.
The only way to find an exit is to lead with no mercy the Gladers. For this, you are to prove that you have the quality of a great leader. The glands are terrorized at the thought of traversing the labyrinth, and this generates tension. Revolt is coming.
You must build a climate of trust and security. You have to find a way to form some groups of mates according to their preferences. But you don’t want to split the Gladers, so use a minimum amount of group.
Prove that you can form some good team with this first sample of 10 Gladers:
Glader | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Can’t be with | 2,5,6 | 1,3,7 | 2,4,8 | 3,5,9 | 1,4,10 | 1,8,9 | 2,9,10 | 3,6,10 | 4,6,7 | 5,7,8 |
- Draw the corresponding graph (1 point)
- Argue about the value your solving method (1 point)
- Find a solution (2 points)
- Write the algorithm and the flowchart of a greedy algorithm corresponding to your method (3 points)
- Implement the greedy algorithm and show the solution for the following graph (3 points).
Task 2: everything is kept nice
Now that your teams are formed, you need to increase the sense of unity within each group. The union is strength, and as the Vikings said: from a good meal arises a millennial friendship.
To increase the trust between each member of a team, you organize the meal in the following way:
- Each team has its own round table
- You can’t have the same neighbor from one meal to each other
The teams will work fine once every member meets the others.
- Draw the corresponding graph – for example with a team of nine members (1 point)
- How many meals can you do with a team of nine members?
- Show the problem (1 point)
- Show method (2 points)
- Solve the problem (1 point)
- Find a brute force search algorithm to find the organization of a table for the meals
- Show flowchart (3 points)
- Show complexity (2 points)
Task 3: How to escape to the maze?
Your groups have become strong as never. But the fear of the labyrinth and its dangers still paralyzes the Gladers. Only the cold and rigid logic of mathematics can dispel this fog.
However, you can’t lose any time in the maze because it opens a short time every day. You must take care of your mates and to purpose a method to map the maze without to get lost. Once the map is ready, you need to find the proper way to go to the exit.
- Purpose a greedy algorithm and its flowchart to find the exit in a maze. Adapt it to map an unknown/random maze (2 points)
- Construct a graph based on the following maze that shows intersections as vertices (3 points)
- Find how to reach the exit by wasting the least amount of time (3 points)
You don’t have a lot of time to reach the exit. After investing the walls, you find some shortcut thanks to the ivy growing for years. Those shortcuts (in red) take as much time to travel as from the gate to the first turn (three units).
- Construct a graph based on the following maze (4 points)
- Find how to reach the exit by wasting the least amount of time (3 points)
Task 4: you are WICKED
You are over the maze. You remember everything about your past and decide to take control of the maze. You take discreetly contact with WICKED. An hour later, as your comrades continue to demolish the surveillance rooms, thick smoke invades the rooms and puts you to sleep.
You wake up alone. In front of you is a dozen control panels. You understand that the armed forces of WICKED came and rebuilt the checkpoint. A keyboard in front of you wearing strange signs, buttons start blinking while the maze is transformed. One word is left on your right: « Only the best have the right to live, do your job.”
You decide to make it more dynamic and autonomous maze in the way of change. For this you need to create programs that will take care to renew the work hour after hour. WICKED is GOOD.
- Do the randomized prim algorithm
- Show flowchart (3 points)
- Show your program and comment on each function (3 points)
- Show a result and comment it (1 points)
- Do the cellular automaton algorithm
- Show flowchart (3 points)
- Show your program and comment on each function (4 points)
- Show a result and comment it (1 points)
Take a look: https://en.wikipedia.org/wiki/Maze_generation_algorithm
FR 
EN 
ES