3. The example run of the exact solution for the traveling salesperson problem, given in the lecture notes, shows that many of the table cells are not filled in (shown as a dash), because the element corresponding to the cell column does not belong to the set corresponding to the cell row. In a problem with n vertices, the table would have n - 1 columns (because the start vertex is omitted), and 2n-1 1 rows (because the empty set is omitted). How many of the resulting (n 1)(2n-1 1) cells would be filled in, as a function of n? 14 q r q - 1 29 - 21 - 2 15 21 32 - 3 18 L: {p} 18 {q} {p,q} 35 {r} {p.r} 32 {q,r} {p,q,r} 60 0 17 4 S 17 33 5 46 50 6 spar = srap = 18+14+29+17 = 78 46 50 7 1 2 spra = sqrp - 18+15+29+21 = 83 60+18 46+21 50+17 sqpr = srpa = 21+14+15+17 = 67