For this exercise you will be solving the problem [AED058] Node Distance.
Desired time complexity: \(O(|V| + |E|)\) (where V is the set of nodes and E is the set of edges)
In what concerns the continuous evaluation solving exercises during the semester, the exercises you can submit in this class are:
Submission Deadline: December 21st (submit to AED's Mooshak)
You are encouraged to talk to the professor and to your colleagues if you have difficulties. However, any more direct help you have received from other colleagues should be acknowledged in the comments of the code you submit.
After the deadline the problems will still be available on Mooshak, but the submissions will not count towards your grade.
Each class is worth 10 per cent of the grade for this component. As there will be 11 classes with submissions, you can get full marks even if you haven't done everything.
For a problem to count, you have to get all the tests right (i.e. accepted). Even if you solve all the problems, the maximum in a single class is 100 per cent.
it is guaranted that the main exercises on each class will sum to at least 100% of the class grade.
This class is about graphs and essential usages of DFS. It is therefore convenient that you know what was discussed on the lectures:
This set of exercises will involve the graph class that was given on the past practical class, so you are strongly advised to first do the practical class #09 (at least the main exercises) and only then start this practical class #10.
1. Your first exercise with BFS in a graph
For this exercise you will be solving the problem [AED058] Node Distance.
Desired time complexity: \(O(|V| + |E|)\) (where V is the set of nodes and E is the set of edges)
This exercise is directly explained in the lecture slides: 12 - Graphs: Breadth-First Search (DFS) [slides 6 to 8]
If you want you can have a look at a BFS visualization.
Note that the class Graph already has an example implementation of BFS that you can reuse/extend (and that example code for calling it was given on exercise 1 of practical class #09).
- The solutions is essentially in slide 7. Can you understand it?
Hints
- BFS already traverses the nodes in increasing order of distance, so each time you reach a node, you know it was with the shortest distance
- Keep an extra variable on each node to store the distance; update it each time you reach a new node (is w was added as a child of u, then w.distance = u.distance + 1
2. Graph Diameter
For this exercise you will be solving the problem [AED059] Graph Diameter.
Desired time complexity: \(O(|V|\times (|V| + |E|))\) (where V is the set of nodes and E is the set of edges)
Here you need to compute the diameter of a graph, to show you understood distances with BFS 😃
- Just start a BFS from each node, and see what is the maximum distance to another node
- Be careful with the case where there is more than one connected component
3. BFS... on a grid!
For this exercise you will be solving the problem [AED060] 2D Maze.
Desired time complexity: \(O(R \times C)\) (where R is the number of rows and C the number of columns)
This exercise was discussed in lectures: see 12 - Graphs: Breadth-First Search (DFS) [slide 11]
- Do a BFS on a grid: your queue can be a queue of coordinates (e.g. a queue of pair<int, int>)
- Besides this, it is just a normal BFS and the same as [AED058] 😃
4. Strongly Connected Components
For this exercise you will be solving the problem [AED061] Counting Strongly Connected Components.
Desired time complexity: \(O(|V| + |E|)\) (where V is the set of nodes and E is the set of edges)
After BFS, we are now back to (a more advanced) DFS. This exercise is directly explained in the lecture slides: 12 - Graphs: Depth-First Search (DFS) [slides 26 to 34]
Do you understand why Tarjan Algorihtm works? Can you implement the idea in C++ and using the graph class provided?
- You can just implement the code of slide 34 in C++
- Since C++ stacks do not directly implement the operation to know if an element is in the stack, you need to provide an alternativa (e.g. just use an extra set of nodes or a boolean attribute in each node indicating if it or not in the stack)
5. Reconstrucing the path
For this exercise you will be solving the problem [AED062] Shortest Path.
Desired time complexity: \(O(|V| + |E|)\) (where V is the set of nodes and E is the set of edges)
This exercise is an extension of [AED058] and directly explained in the lecture slides: 12 - Graphs: Breadth-First Search (DFS) [slides 9 and 10]
- Keep an extra variable on each node to store the predecessor node; update it each time you reach a new node (is w was added as a child of u, then w.pred = u
- Be careful with computing the lexiographically smaller path: you must update the predecedor if a "smaller" node will give origin to the same distance for the same node, even it was already "visited"
6. Multiple Source BFS
For this exercise you will be solving the problem [AED063] Ash Cloud.
Desired time complexity: \(O(R \times C)\) (where R is the number of rows and C the number of columns)
This exercise is directly explained in the lecture slides: 12 - Graphs: Breadth-First Search (DFS) [slides 12 to 15]
- Start a BFS at the same time on all he clouds
- Output the distance to the first aiport being reached and to the last one
7. Strongly Connected Components
For this exercise you will be solving the problem [AED064] Listing Strongly Connected Components.
Desired time complexity: \(O(|V| + |E|)\) (where V is the set of nodes and E is the set of edges)
This exercise is simply an extension of [AED061] in which you also need to output the components themselves.
- You can use Tarjan algorithm, which is exactly the same of [AED061] and it is explained on the same set of slides
Hints
8. Articulation Points
For this exercise you will be solving the problem [AED065] Articulation Points.
Desired time complexity: \(O(|V| + |E|)\) (where V is the set of nodes and E is the set of edges)
This exercise can be seen as an extension of Tarjan algorithm for SCCs and is directly explained in the lecture slides: 12 - Graphs: Depth-First Search (DFS) [slides 35 to 40]
- The pseudo-code for this exercise is directly given in slide 40
The main idea of the challenge problems is to give you the opportunity of improving your problem solving abilities.
For this exercise you will be solving the problem [AED066] Magic Squares.
For this class, the problem is not really hard, but involves... graphs! (of course 😁)
The main difficulty is that the graph itself is implicit and keeping the visited nodes is slightly trickier.
Since this is a challenge, I will not give you any hints (but we discussed the problem in the lectures and the slides include it), but if you are stuck just contact @PedroRibeiro on Discord. Feel free to also contact @PedroRibeiro to discuss your accepted solution.
Happy coding! 😊