Self-assessment quiz

--- secondary_color: lightgray --- # Addressing a computational problem To formalize means... - [ ] To identify algorithms that solve the problem at hand. - [x] To express a problem using adapted terminology and concepts. - [ ] To write formulas to determine the time you will need to solve the problem. # Addressing a computational problem To specify means... - [ ] To determine if you will play the rat or the python in a PyRat game. - [x] To identify algorithms or methods that are well suited to solve the formalized problem. - [ ] To identify problems that can be solved with a given algorithm. # Addressing a computational problem Order the steps you should follow to address a computational problem. 1. Formalize. 2. Specify. 3. Code. # Addressing a computational problem Consider the following problem: we are given a list of routers and proximities between some of these routers. Each router can be associated with one frequency, with the limit that two routers that are in proximity should not be associated with the same frequency. The aim is to find the minimum number of distinct frequencies that have to be chosen in order to solve the problem. What would be the good way to go about solving this problem? - [x] Find a way to formalize the problem, find a solution to solve the formalized problem, then code the solution. - [ ] Find a solution to solve the problem, code it, then search for possible other solutions in the literature. - [ ] Code a first solution, write its specification, then find an adequate formalism to express the problem.

--- secondary_color: lightgray --- # Graphs and paths A graph is composed of two key elements. What are they? - [x] A set of vertices. - [ ] A set of circles. - [ ] A set of lines. - [x] A set of edges. # Graphs and paths Edges in graphs and in digraphs are different. What do they respectively correspond to? - [ ] Couples / pairs. - [x] Pairs / couples. - [ ] Pairs / pairs. - [ ] Couples / couples. # Graphs and paths Consider the edge sequence $( \{v_1, v_2\}, \{v_2, v_4\}, \{v_4, v_6\} )$ in a complete graph with vertices $V = \{v_1, v_2, v_3, v_4, v_5, v_6\}$. Which of the following statements are true? - [x] It is a path. - [ ] It is a cycle. - [x] It is a walk. # Graphs and paths Consider $V = \{v_1, v_2, v_3, v_4\}$. For which following values of $E$ is $G = (V, E)$ a tree? - [ ] $\{ \{v_1, v_2\}, \{v_2, v_3\}, \{v_3, v_4\}, \{v_1, v_4\} \}$. - [x] $\{ \{v_1, v_2\}, \{v_2, v_3\}, \{v_3, v_4\} \}$. - [ ] $\{ \{v_1, v_2\}, \{v_3, v_4\} \}$. - [x] $\{ \{v_1, v_2\}, \{v_1, v_3\}, \{v_1, v_4\} \}$. # Graphs and paths What is the size of a complete graph with an order of $n$? - [x] $\frac{n(n-1)}{2}$. - [ ] $n^2$. - [ ] $2n$. # Graphs and paths Can a complete graph be a tree? - [ ] No, never. - [ ] Yes, if the order of the graph is an odd number. - [x] Yes, if the order of the graph is 1 or 2. # Graphs and paths Consider a graph G that contains the edges $\{u, v\}$, $\{u, w\}$ and $\{v, w\}$. What can you say about the sequence $( \{u, v\}, \{v, w\}, \{w, u\} )$? - [ ] It is not a cycle, because a cycle is a sequence of vertices, not of edges. - [ ] It is not a cycle, because $\{w, u\}$ is not an edge of the graph. - [x] It is a cycle. # Graphs and paths What is the size of a graph with the following adjacency matrix? $$\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$ - [x] 3. - [ ] 4. - [ ] 6.

--- secondary_color: lightgray --- # Representing graphs Which data structures need the number of elements to be defined beforehand? - [x] An array. - [ ] A list. - [ ] A dictionary. # Representing graphs We store the adjacency matrix of a graph of order 20 in an array. How many elements does this array contain? - [ ] 4. - [ ] 40. - [x] 400. # Representing graphs Let's consider a list with 10 elements. How many elements have to be accessed to reach the 6th element? - [ ] 1. - [x] 6. - [ ] 10. # Representing graphs We use lists to store the neighbors of vertices of a cycle graph of order 25. How many elements does such structure contain? - [ ] 25. - [x] 50. - [ ] 625. # Representing graphs Imagine that we want to represent a graph containing many vertices in memory. We know that this graph has very few edges. What data structures are adapted? - [ ] An array. - [x] A list. - [x] A dictionary.

--- secondary_color: lightgray --- # Graph traversal A graph traversal is a way to... - [ ] Split the graph in half. - [x] Explore the graph, one vertex at a time, using knowledge about the neighbors of explored vertices. - [x] Obtain the list of accessible vertices from an initial one. # Graph traversal Let's say we use a DFS from vertex $v_1$ on an unweighted graph. Which of the following propositions are true? - [x] We obtain a spanning tree, covering the accessible vertices from $v_1$. - [ ] We obtain shortest paths from v1 to the accessible vertices of the graph. - [x] We follow a trail, as long as there are unexplored vertices to jump to. - [x] We go through each edge of the graph exactly one time. # Graph traversal Let's say we use a BFS from vertex $v_1$ on an unweighted graph. Which of the following propositions are true? - [ ] We go through each edge of the graph exactly one time. - [ ] We follow a trail, as long as there are unexplored vertices to jump to. - [x] We obtain shortest paths from $v_1$ to the accessible vertices of the graph. - [x] We obtain a spanning tree, covering the accessible vertices from $v_1$. # Graph traversal Imagine a graph where $u$ and $v$ are vertices, and there is no path for which $u$ and $v$ are extremities. If we run a DFS from $u$, which of the following propositions are true? - [x] At the end of the DFS, $v$ has not been explored. - [ ] The DFS is not well defined and cannot be processed. - [ ] The resulting tree is made exclusively of shortest paths from $u$ to the accessible vertices of the graph. # Graph traversal Imagine we run a DFS (respectively a BFS) from any vertex $u$ of a complete graph of order $n$. How many vertices are neighbors of $u$ in the resulting tree? - [ ] $n-1$ (respectively 1). - [ ] $\frac{n(n-1)}{2}$ in both cases. - [x] 1 (respectively $n-1$). # Graph traversal Imagine a graph with vertices $V = \{v_1, v_2, v_3, v_4\}$, in which $\{v_1, v_2\}$, $\{v_1, v_3\}$, and $\{v_1, v_4\}$ are edges. Which of the following are correct? - [x] To traverse this graph using a DFS from $v_1$, we use a LIFO. $v_2$, $v_3$, and $v_4$ (in this order) are added to the LIFO, and none of them have been previously visited. As a consequence, the next vertex to be visited is $v_4$. - [x] To traverse this graph using a BFS from $v_1$, we use a FIFO. $v_2$, $v_3$, and $v_4$ (in this order) are added to the FIFO, and none of them have been previously visited. As a consequence, the next vertex to be visited is $v_2$. - [ ] To traverse this graph using a DFS from $v_1$, we use a LIFO. $v_2$, $v_3$, and $v_4$ (in this order) are added to the LIFO, and none of them have been previously visited. As a consequence, the next vertex to be visited is $v_2$.

--- secondary_color: lightgray --- # Routing tables Routing helps us... - [x] Navigate between any two vertices in a graph. - [ ] Determine if there are any cycles in the spanning tree of a graph. - [ ] Calculate the order of the graph. # Routing tables In a rooted tree... - [x] Every vertex except the root has a unique parent. - [ ] All children have cousins. - [ ] Every vertex has a unique child. # Routing tables In a routing table, we can find... - [ ] The weights of the edges between two vertices of a graph. - [x] The parents of the vertices in a rooted spanning tree of a graph. - [ ] The children of the vertices in a rooted spanning tree of a graph. # Routing tables Imagine a graph with vertices $V = \{v_1, v_2, v_3, v_4, v_5\}$. A graph traversal algorithm from $v_1$ has produced the following routing table: $$\left[\begin{array}{cccccc} \\ \textbf{Vertex} & v_1 & v_2 & v_3 & v_4 & v_5 \\ \textbf{Parent} & \cdot & v_3 & v_1 & v_2 & v_1 \end{array}\right]$$ What is the corresponding path between $v_1$ and $v_4$? - [ ] $(\{v_1, v_2\}, \{v_2, v_3\}, \{v_3, v_4\})$. - [ ] $(\{v_1, v_3\}, \{v_3, v_5\}, \{v_4, v_5\})$. - [ ] $(\{v_1, v_2\}, \{v_2, v_4\})$. - [x] $(\{v_1, v_3\}, \{v_2, v_3\}, \{v_2, v_4\})$.

--- secondary_color: lightgray --- # Queuing structures for graph traversals When removing an element from a FIFO, we get... - [ ] The first element that was added. - [x] The last element that was added. # Queuing structures for graph traversals A DFS can be implemented using... - [x] A LIFO to store the next unexplored vertices to be visited. - [ ] A LIFO to store the list of all neighbors of the starting vertex. - [ ] A FIFO to store the next unexplored vertices to be visited. # Queuing structures for graph traversals We add the elements 10, 25, 52, 40, 20, then 40 to a LIFO (in this order). In which order are they extracted when performing four consecutive removals? - [ ] 40, 20, 40, 10 (first we pop 40). - [x] 40, 20, 40, 52 (first we pop 40). - [ ] 10, 25, 52, 40 (first we pop 10).