French Flag Version française

Exercise Session 2: Trees. Dynamic programming. DAGs.

Reminders


Exercise 1: Trees

  1. Implement in a new file tree.1.cc the function ParentVectorToChildVector(...) described in file tree.1.h:
    #ifndef __TREE_1_H
    #define __TREE_1_H
    
    #include <vector>
    using namespace std;
    
    // Input: the parent array of a rooted tree (or a forest of rooted trees):
    // parent[i] = -1 if node i is a root, else it's the parent of node i in the
    // tree that contains i.
    //
    // Output: the array of children arrays: element i of the output array is a
    // vector<int> containing all the children of node i (it can be empty
    // if i has no children), in any order.
    //
    // Example:
    //
    //    .3.     vector<int> parents = [3, 2, 3, -1, 3, 1]  // size()=6 = num nodes
    //   .'|'.
    //  2  0  4   vector<vector<int>> children = [ [],
    //  |                                         [5],
    //  1                                         [1],
    //  |                                         [2, 0, 4],
    //  5                                         [],
    //                                            [] ]
    vector<vector<int>> ParentVectorToChildrenVector(const vector<int>& parent);
    
    #endif  // __TREE_1_H
    
    The time complexity must be O(N), where N is the number of nodes of the tree (which is equal to the size of the input vector<int>).

    Test: make tree.1

    TO SUBMIT: tree.1.cc

  2. Implement in a new file tree.2.cc the function Height() described in file tree.2.h:
    #ifndef __TREE_2_H
    #define __TREE_2_H
    
    #include <vector>
    using namespace std;
    
    // Input: a tree, given as a children array (i.e. the output of the function done
    // in the previous question), and a node X of this tree.
    //
    // Output: the height of the subtree of X: 0 if X has no children, 1 if X only has
    // children that don't have children themselves, etc.
    //
    // Hint: the function could be recursive.
    // 
    // Example:
    //    .3.     vector<vector<int>> children = [ [], [], [1], [2, 0, 4], [] ]
    //   .'|'.
    //  2  0  4   -> Height(children, 0) = 0 ;   Height(children, 1) = 0
    //  |         -> Height(children, 2) = 1 ;   Height(children, 3) = 2
    //  1         -> Height(children, 4) = 0
    int Height(const vector<vector<int>>& children, int node);
    
    #endif  // __TREE_2_H
    
    The time complexity must be O(subtree size).

    Test: make tree.2

    TO SUBMIT: tree.2.cc

  3. Implement in a new file tree.3.cc the function AllHeights() described in file tree.3.h:
    #ifndef __TREE_3_H
    #define __TREE_3_H
    
    #include <vector>
    using namespace std;
    
    // Input: a tree, given as a children array (like the output of the first
    // question).
    //
    // Output: the heights of all nodes of the tree, i.e. the array of values of
    // Height(i) for all nodes i in 0..N-1.
    //
    // Time complexity: O(N).
    //
    // Hint: you could use an auxiliary recursive function (declared and defined
    // directly in the .cc: don't touch the .h), which will be very similar to the
    // Height() function done in the previous question, with added memoization.
    // 
    // Exemple:
    //    .3.     vector<vector<int>> children = [ [], [], [1], [2, 0, 4], [] ]
    //  .' | '.
    //  2  0  4   -> AllHeights(children) = [0, 0, 1, 2, 0]
    //  |
    //  1
    vector<int> AllHeights(const vector<vector<int>>& children);
    
    #endif  // __TREE_3_H
    
    The time complexity must be O(N), where N is the total number of nodes.

    Test: make tree.3

    TO SUBMIT: tree.3.cc

  4. Implement in a new file tree.4.cc the function AllSubtreeSizes() described in file tree.4.h:
    #ifndef __TREE_4_H
    #define __TREE_4_H
    
    #include <vector>
    using namespace std;
    
    // Exactement comme la question précédente, mais cette fois on calcule pour
    // chaque noeud i la taille de son sous-arbre (nombre de noeuds, i inclus, qui
    // sont descendants de i).
    // 
    // Indices: le code ressemble beaucoup à la question précédente.
    //
    // Exemple:
    //    .3.     vector<vector<int>> enfants = [ [], [], [1], [2, 0, 4], [] ]
    //  .' | '.
    //  2  0  4   -> AllSubtreeSizes(enfants) = [1, 1, 2, 5, 1]
    //  |
    //  1
    vector<int> AllSubtreeSizes(const vector<vector<int>>& enfants);
    
    #endif  // __TREE_4_H
    
    La complexité devra être O(N), où N est le nombre de noeuds total.

    Test: make tree.4

    TO SUBMIT: tree.4.cc


Exercise 2: DAG (Directed Acyclic Graph)

  1. Implement in a new file toposort.cc the function TopologicalSort() described in file toposort.h, which uses the DirectedGraph class seen in Session 1 for directed graphs (a reference implementation is inside the test.tar.gz archive, so it should be readily available in your working directory, but you can also decide to use your own implementation as long as you respected the interface):
    #ifndef __TOPOSORT_H
    #define __TOPOSORT_H
    
    #include "graph.h"
    #include <vector>
    using namespace std;
    
    // Perform a topological sort of the given directed graph, and returns the
    // indices of the nodes, sorted in that topological order: "leaves"
    // (nodes that don't have any outgoing arcs) will be in the beginning.
    // If the graph has a cycle (i.e. it's not a DAG, hence there is no
    // topological order), this function must return the empty vector.
    //
    // HINTS/NOTES:
    // - Often, several different topological orders exist and are valid.
    // - Since the input graph gives you the list of children of a node, and
    //   you need the list of parents in the algorithm, you have 2 options:
    //   a) precompute that list of parents, for each node
    //   b) perform the 'inverse' topological sort, where one start with nodes
    //      that have no parent (instead of nodes with 0 children); then reverse
    //      the final order.
    // - One may precompute the "residual degree" of each node (in-degree or out-
    //   degree, depending on the option you chose before), and initialise a simple
    //   queue (vector<int> for LIFO order, queue<int> for FIFO order)
    //   that'll contain all the node of residual degree 0, and dynamically updated.
    // - The overall time complexity must be O(M+N) (number of arcs + number of nodes).
    //
    // Example:
    //
    // 2-->5-->6-->7   Several valid topological orders (non-exhaustive list):
    //     ^   |   |    - [4, 0, 7, 6, 5, 1, 2, 3]
    //     |   v   v    - [0, 4, 7, 6, 5, 2, 1, 3]
    // 3-->1   0   4    - [4, 7, 0, 6, 5, 1, 3, 2]
    //
    vector<int> TopologicalSort(const DirectedGraph& graph);
    
    #endif  // __TOPOSORT_H
    Test: make toposort

    TO SUBMIT: toposort.cc

  2. Implement in a new file longest_path_dag.cc the function LongestPathInDag() described in file longest_path_dag.h:
    #ifndef __LONGEST_PATH_DAG_H
    #define __LONGEST_PATH_DAG_H
    
    #include "graph.h"
    #include <vector>
    using namespace std;
    
    // Input: a directed, weighted graph: each node has a positive weight
    // given in the "weights" array.
    //
    // Output: if the graph is cyclic, returns -1. Else, returns the sum of the
    // weights of the nodes on the 'heaviest' path, i.e. the path that maximizes
    // the sum of the weights of its nodes.
    //
    // Hints: If you have implemented TopologicalSort(), you can use it in your
    // function; it helps coding the simplest version.
    // If not, think about memoization!
    // In both cases, it might be useful to create an array that'll store, for
    // each node i, the weight of the heaviest path that starts from i.
    //
    // Example (the node weights are in ())
    //
    // 2(4)-->5(5)-->6(1)-->7(2)     The heaviest/longest path is
    //        ^      |      ^        unique in this example: it's
    //        |      v      |        2->5->6->0, whose total weight is 14.
    // 3(2)-->1(1)   0(4)   4(11)
    //
    int LongestPathInDag(const DirectedGraph& graph, vector<int>& weights);
    
    #endif  // __LONGEST_PATH_DAG_H
    Test: make longest_path_dag

    TO SUBMIT: longest_path_dag.cc