Self-assessment quiz

--- secondary_color: lightgray --- # The traveling salesman problem In graph theory, the TSP corresponds to... - [ ] A problem in which we aim to find the shortest path from a vertex u to a vertex v in a weighted graph. - [ ] The Team Supporting PyRat (TSP). - [x] A problem in which we aim to find the shortest route going through all vertices of a weighted graph from an initial vertex. # The traveling salesman problem Reducing a problem $P$ to a problem $Q$ involves... - [ ] Finding the entries of problem $P$ for which $Q$ gives the same outputs. - [ ] Keeping the part of $P$ that is simpler than $Q$. - [x] Finding a way to solve $P$ using any algorithm designed to solve $Q$. # The traveling salesman problem The TSP processes an input that is best described as... - [x] A complete weighted graph and an initial vertex. - [ ] An unweighted tree and a root vertex. - [ ] A tetrahedron. # The traveling salesman problem Which of the following statements define the Traveling Salesman Problem? - [ ] To find the shortest cycle in a weighted graph from an initial vertex. - [x] To find the shortest route going through all vertices of a weighted graph from an initial vertex. - [ ] To find a minimum spanning tree on a weighted graph from an initial vertex. # The traveling salesman problem Consider a situation in which we are interested in the complexity of algorithms that operate on graphs as a function of the order $n$ of these graphs. Check the following problems that can be reduced to finding a shortest path between two vertices $u$ and $v$ in a weighted graph: - [x] Finding a shortest path between two vertices $u$ and $v$ in an unweighted graph. - [ ] The TSP. - [x] Checking if there is a path between two vertices $u$ and $v$ in a weighted graph.

--- secondary_color: lightgray --- # Bruteforce and backtracking to solve NP-complete problems A bruteforce algorithm... - [x] Is an algorithm that finds solutions by testing all possibilities exhaustively. - [x] Is guaranteed to find exact solutions. - [ ] Is an algorithm that finds the least complex solution without checking if it is correct. # Bruteforce and backtracking to solve NP-complete problems A backtracking algorithm for the TSP... - [x] Iteratively examines the lengths of routes and immediately aborts examination of a route that is longer than the shortest found so far. - [x] Is guaranteed to find the shortest route. - [ ] Randomly explores only a subset of all routes and outputs the shortest route of the subset, but is not guaranteed to find the shortest route among all possible ones. # Bruteforce and backtracking to solve NP-complete problems We consider using a backtracking algorithm for the TSP. Which of the following are true? - [x] The complexity of backtracking may be linear for some graphs. - [x] The order in which vertices are explored has an important influence on overall execution time. - [ ] Backtracking is based on a BFS. # Bruteforce and backtracking to solve NP-complete problems When solving the TSP using backtracking, which of the following statements are true? - [x] The exploration of the current branch is aborted if the length of the partial route is greater than the best route found so far. - [x] In the best case, only the first branch has been fully explored. - [x] If branches are explored in decreasing length order, then we explore as many solutions as the simple exhaustive search. # Bruteforce and backtracking to solve NP-complete problems We consider the use of a backtracking algorithm to solve the TSP. Which of the following statements are true? - [x] On a weighted graph in which all weights are equal, backtracking will be at least as costly as a bruteforce search. - [ ] If interrupted before the end, a solution estimated by backtracking will always be strictly inferior to the true answer. - [x] The order in which vertices are explored has an important influence on overall execution time.

--- secondary_color: lightgray --- # Problem complexity & NP-completeness The complexity of a problem is defined as... - [x] The minimum complexity of the algorithms used to solve the problem. - [ ] The maximum complexity of the algorithms used to solve the problem. - [ ] The average complexity of the algorithms used to solve the problem. # Problem complexity & NP-completeness To solve NP problems, you often need to use algorithms with... - [ ] Linear complexity. - [ ] Quadratic complexity. - [x] Exponential complexity. # Problem complexity & NP-completeness The traveling salesman problem is an NP-Complete problem. - [x] True. - [ ] False. # Problem complexity & NP-completeness Consider a problem for which we have a solution algorithm with complexity $O(n^2)$. Select the correct statements: - [x] The complexity of the problem cannot be higher than $n^2$. - [ ] There is not an algorithm that can solve the problem with complexity $O(n)$. - [ ] The complexity of the problem is $O(n^2)$. - [ ] The problem is at least as difficult as the TSP. # Problem complexity & NP-completeness The complexity of a problem is... - [ ] The maximum complexity of an algorithm used to solve it. - [x] The minimum complexity of an algorithm used to solve it.