The lecture notes show that approximating TSP by an Euler tour of a doubled spanning tree is a \(2\)-approximation. In fact the approximation ratio is slightly better: it is at most \(2(1-1/n)\).
What should you modify on the "Why is this a 2-approximation?" slide of the lecture notes in order to prove this?
Describe a way to choose weights for an \(n\)-vertex complete graph so that the doubled MST weight is equal to \(2(1-1/n)\) times the TSP weight.
In the dynamic programming algorithm for the TSP, on the slide "Pseudocode for shortest tour length", there is an expression "for \(u\) in \(A-v\)". Write a fragment of code in Python or C that loops over all members of the set \(A-v\), using the translations of set notation to Python or C described on the slide "Numbering sets". Your code may assume that integer variables \(A\), \(v\), and \(n\) have already been set, where \(A\) is a subset of the integers from \(0\) to \(n-1\) as described in the slide "Numbering sets" and where \(v\) is one of these integers. It's ok if your code takes time \(O(n)\) instead of the faster time bound \(O(|A|)\).
Among the people nominated for an Academy Award in 1929, the first year they were given (https://www.oscars.org/oscars/ceremonies/1929), use the Oracle of Bacon (https://oracleofbacon.org/) to find one with a finite Bacon number greater than three. (Hint: not nominated in an acting category.)
Suppose we create 5-vertex graphs using the Barabasi-Albert model with \(d=2\). That is, we start with a graph with two vertices and one edge, and repeat three times: add a vertex adjacent to two previous vertices.
How many different graphs could be constructed in this way? Draw each of them.
Find a graph on five vertices, with seven edges, that cannot be constructed in this way.