Self-assessment quiz

--- secondary_color: lightgray --- # Heuristics A heuristic algorithm is used to... - [x] More quickly solve problems when classical methods are too slow to find an exact solution. - [ ] Improve the optimal solution produced by an exact algorithm. - [ ] Deteriorate the quality of the solution when it is too good to be true. # Heuristics A good heuristic must... - [ ] Provide no solution when the problem is too complex to be solved. - [x] Provide a gain and be of limited complexity. - [ ] Find the optimal solution, even for the most complex problems, in a few milliseconds.

--- secondary_color: lightgray --- # Greedy algorithms Which statements best describe a greedy algorithm? - [x] It is an algorithm that follows locally optimal solutions. - [ ] It is an algorithm that operates on graphs only. - [ ] It is an algorithm that has very limited complexity. # Greedy algorithms Which of the following statements are true? - [ ] A greedy algorithm is in all cases not optimal. - [x] For some problems, a greedy algorithm can be non-optimal. - [ ] There is only one greedy algorithm to solve a given problem. # Greedy algorithms We consider the greedy algorithm that always choose to jump to the closest unexplored vertex to solve the TSP. Which of the following statements is true? - [ ] The solution found by a greedy algorithm is always optimal. - [x] The solution found by a greedy algorithm may or may not be optimal. - [ ] The solution found by a greedy algorithm is never optimal. # Greedy algorithms Which of the following paths can be obtained when applying a greedy algorithm that jumps to the closest vertex and starts from vertex $v_0$?  - [ ] $(\{v_0, v_1\}, \{v_1, v_2\}, \{v_2, v_3\}, \{v_3, v_4\})$. - [x] $(\{v_0, v_4\}, \{v_1, v_4\}, \{v_1, v_3\}, \{v_2, v_3\})$. - [x] $(\{v_0, v_3\}, \{v_1, v_3\}, \{v_1, v_4\}, \{v_2, v_4\})$. # Greedy algorithms Consider the problem of finding a longest path in a given weighted graph, starting at vertex $u$. To solve it, we can adopt the greedy approach of systematically choosing an unexplored edge $\{v, v'\}$ of maximum weight from the current vertex $v$, then jumping to the corresponding vertex $v'$, until there are no such edges left. Which of the following statements are true? - [ ] This greedy algorithm is optimal (it always outputs the longest path). - [x] This greedy algorithm outputs a path starting at $u$. - [x] This greedy algorithm always finishes (it cannot iterate endlessly).

--- secondary_color: lightgray --- # Approximate solutions An approximate solution is used... - [x] Whenever exact solutions are not feasible in practice. - [x] To speed up the computations compared to exact solutions. # Approximate solutions A Pareto optimal is... - [ ] A solution that minimizes both speed and correctness. - [x] An optimal trade-off between speed and correctness. - [ ] A solution that maximises correctness, irrespective of speed. - [ ] A solution that maximizes both speed and correctness. # Approximate solutions A Pareto frontier... - [ ] Delimits algorithms with high and low complexity. - [x] Delimits trade-offs between complexity and correctness. # Approximate solutions A Pareto optimal is... - [ ] A solution that minimizes both speed and correctness. - [x] An optimal tradeoff between speed and correctness.