Self-assessment quiz

--- secondary_color: lightgray --- # Dijkstra's algorithm When running Dijkstra's algorithm on a weighted graph from vertex $u$, what following conditions are (independently) sufficient to guarantee that Dijktra's algorithm outputs are the shortest paths from vertex $u$ to the accessible vertices of the graph? - [ ] The input graph is connected. - [X] The input graph contains only nonnegative weights. - [ ] The input weighted graph is a tree. # Dijkstra's algorithm What following property best describes the functioning of Dijkstra's algorithm, starting from a vertex $u$? - [ ] We explore vertices as we would do for a BFS. - [ ] We explore vertices by increasing the hops from $u$ in the graph. - [X] We explore vertices by increasing the distance from $u$ in the graph. # Dijkstra's algorithm The Dijkstra's algorithm maintains two data structures along the process. What are they? - [ ] An estimation of the order of the graph and an estimation of the size of the graph. - [X] The list of explored vertices and an estimation of the distances from $u$ to the other vertices of the graph. - [ ] The list of explored vertices and the list of explored edges. # Dijkstra's algorithm Which of the following statements apply to Dijkstra's algorithm? - [ ] It is an algorithm that only operates on trees. - [X] It is an algorithm that is guaranteed to output the shortest paths from an initial vertex when input graph weights are non-negative. - [ ] It is an algorithm that outputs the size of the input graph. - [X] It is a traversal algorithm that explores vertices by increasing the distance from an initial vertex. # Dijkstra's algorithm What is the maximum number of iterations of Dijkstra's algorithm main loop, when applied to a graph with an order of $n$? - [ ] $n/2$. - [X] $n$. - [ ] $n(n-1)/2$. # Dijkstra's algorithm What is the routing table obtained using Dijkstra's algorithm from vertex $v_0$ on the following graph?  - [ ] $$\left[\begin{array}{cccccc} \\ \textbf{Vertex} & v_0 & v_1 & v_2 & v_3 & v_4 \\ \textbf{Parent} & \cdot & v_0 & v_0 & v_2 & v_1 \end{array}\right]$$ - [X] $$\left[\begin{array}{cccccc} \\ \textbf{Vertex} & v_0 & v_1 & v_2 & v_3 & v_4 \\ \textbf{Parent} & \cdot & v_0 & v_1 & v_2 & v_1 \end{array}\right]$$ - [ ] $$\left[\begin{array}{cccccc} \\ \textbf{Vertex} & v_0 & v_1 & v_2 & v_3 & v_4 \\ \textbf{Parent} & \cdot & v_0 & v_1 & v_1 & v_1 \end{array}\right]$$

--- secondary_color: lightgray --- # Min-heaps A min-heap contains the following (key, value) couples: $\{(A, 25), (B, 37), (C, 5) \}$. What is the next couple that will be removed? - [ ] $(B, 37)$. - [X] $(C, 5)$. - [ ] $(A, 25)$. ## Min-heaps A min-heap contains the following (key, value) couples: $\{(A, 55), (B, 22), (C, 32), (D, 87)\}$. Select the correct assertions: - [X] If performing add or replace with $(A, 32)$, the resulting status will be $\{(A, 32), (B, 22), (C, 32), (D, 87)\}$. - [ ] If performing add or replace with $(B, 53)$, the resulting status will be $\{(A, 55), (B, 53), (C, 32), (D, 87)\}$. - [X] The next element to be removed is $(B, 22)$. - [ ] The next element to be removed is $(D, 87)$. - [X] If performing add or replace with $(D, 86)$, the resulting status will be $\{(A, 55), (B, 22), (C, 32), (D, 86)\}$. # Min-heaps The Dijkstra algorithm can be implemented... - [ ] Using a min-heap, by storing vertices as values, and distances to the starting position as keys. - [X] Using a min-heap, by storing vertices as keys, and distances to the starting position as values. - [ ] Using two min-heaps, one for the edges, one for the vertices. # Min-heaps Consider a min-heap with (key, value) couples $ \{ (A, 5), (B, 3), (C, 7) \}$. What is the minimum number of operations (`add_or_replace` or `remove`) to obtain the configuration $\{ (B, 8), (C, 7)\}$? - [ ] 2. - [X] 3. - [ ] 4.

--- secondary_color: lightgray --- # Algorithm complexity The complexity of an algorithm is a measure of the... - [X] Maximum number of elementary operations that are needed for its execution, as a function of the size of the input. - [ ] Minimum number of elementary operations that are needed for its execution, as a function of the size of the input. - [ ] Average number of elementary operations that are needed for its execution, as a function of the size of the input. # Algorithm complexity The big-O notation (or asymptotical behavior) lets us drop... - [ ] Constants and low-order terms because they are too difficult to calculate precisely. - [ ] The mic. - [X] Constants and low-order terms because they do not matter when the problem size becomes large enough. # Algorithm complexity The complexity of the BFS algorithm is... - [X] $O(|E|)$, where $E$ is the set of edges of the graph. - [ ] $O(|V|)$, where $V$ is the set of vertices of the graph. - [ ] $O(|V| \cdot |E|)$, where $V$ is the set of vertices, and $E$ is the set of edges of the graph. # Algorithm complexity Given an input size $n$, a given algorithm performs exactly $3n^2 + 4n + 17$ elementary operations. Which of the following big-O notations are valid for its complexity? - [ ] $O(n)$. - [ ] $O(n \cdot log(n))$. - [X] $O(n^2)$. - [ ] $O(n^3)$. Consider an algorithm that operates on graphs. The number of elementary operations it requires is exactly the number of edges in the graph. What is the complexity of the algorithm, expressed as a function of the order $n$ of the graph? - [ ] Since it depends on the number of edges, it cannot be defined. - [ ] $O(n)$. - [X] $O(n^2)$.