Bitmask TSP

Questions 1 to 5 of 7

1. 1. What number does this program print? ``python mask = (1 << 1) | (1 << 3) print(mask ^ (1 << 1)) ``

   108211
2. 2. What number does this program print? ``python print(((1 << 4) - 1) ^ (1 << 2)) ``

   1541112
3. 3. What time complexity does the bitmask TSP method in this lesson have for n cities?

   O(n!)O(2^n * n^2)O(n^3)O(2^n)
4. 4. The TSP program keeps two lists, best and parent, with one slot for each (set, last city) pair. For 20 cities each list has 2^20 * 20 slots, and each slot is an 8-byte reference. About how much memory do the two lists need together, ignoring the int objects?

   About 80 MiBAbout 160 MiBAbout 320 MiBAbout 1 GiB
5. 5. Which expression adds city c to the set stored in mask?

   mask & (1 << c)mask >> cmask | (1 << c)mask - c