Bitmask TSP

Questions 1 to 5 of 7

1. 1. Which expression is the upper bound on the total work for n cities in the bitmask TSP table?

   n!2^n * n * nn * n2^n + n
2. 2. The lesson estimates the dp table for 20 cities at about how much memory?

   about 4 MBabout 21 MBabout 84 MBabout 840 MB
3. 3. Why is it enough to keep only the cheapest route for each (set, end city) pair?

   Routes with the same set always cost the sameThe cheapest route is always the one with the fewest citiesThe parent table already stores every other routeRoutes with the same set and end city have the same cities left to visit, so the cheaper one is never worse
4. 4. In the 4-city example from the lesson, what does the program get if it takes the minimum of dp[full][last] without adding the trip back to city 0?

   65807075
5. 5. What does this program print? ``cpp #include <iostream> int main() { int mask = 0b1011; // cities 0, 1 and 3 std::cout << (mask & (1 << 1)) << " " << (mask | (1 << 2)) << " " << (mask ^ (1 << 3)) << std::endl; } ``

   2 14 31 15 32 15 32 15 11