HW10. TSP, NN Set Cover (24th of Nov, 23.59)
All assisting code is in here:
https://colab.research.google.com/drive/1Se42paPw5WAJ_Z2dY-pKj-w7ow_gN1eM#scrollTo=v_WfLJMM7uMT
T1: Let’s first study “an impossible” task of recovering a scrambled image.
We have scrambled the rows of two images. Try to recover the original images. What is in these images? Hint: perform a greedy search to find the most similar rows. Experiment on other images; provide some examples in the report, how well your method would work on them. Note, the natural images have usually easier solutions.
T2: Solve the TSP on instances of size 50, 200, 1000 random points placed on a 2048x2048 pixel plane.
Files: Attach:TSP_50.txt Attach:TSP_200.txt Attach:TSP_1000.txt
Background image for TSP visualisation: HW10_TSP.png
Describe your chosen method and provide the best solution you could achieve for each case in the report (include the image (with or without the “underlying map”, and the total distance)
T3: A sparse random graph and graph coverage by “landmarks”.
Let’s take the TSP_1000 city instance (Attach:TSP_1000.txt , feel free to experiment also with smaller ones first). While in TSP task (T2) we assumed a complete graph - every node is connected to every other one, let’s change this in here. Make a subgraph such that for every node there will remain only the chosen nr of closest neighbours. Vary NN value - 5, 10, 20 - interpret the impact.
Study the kNN-graphs first. Next, analyse by breadth first search, how big are the 2, 3 and 4-hop neighbourhoods of such graphs. In each case. Plot a frequency histogram, showing that distribution. E.g. in a 3x3 table (5, 10, 20 NN times 2, 3, and 4-hop neighbourhood size distributions). Provided code has visualisations of graphs, chosen nodes, and BFS subgraph.
T4: Find a smallest nr of nodes that together would cover the entire sparse graphs (10-closest neighbourhood) from T3. Create the covers for 2, 3 and 4 hop neighbourhoods. Highlight the placement of these nodes on the underlying graph (with bright yellow stars). Vary the color of each set randomly.
Hint: study the Minimum Set Cover from the lectures. Apply the greedy set cover. Each node defines a set of the node plus its 3-hop neighbourhood. Report the nr of needed points and visualise the entire set cover by their “center points” on the respective sparse graph. In code there is an example cell that runs it for a nr of randomly chosen points. Illustrate the greedy set cover; and if possible, provide ideas for improvements.
T5: After selecting an article for your essay (Exercise 7 in HW8), you are required to provide feedback on two essays written by your classmates.
Please note that only students who submitted an essay (EX7 in HW8) need to submit feedback on two other essays.
Each of you who has submitted an essay should have received two emails, each containing: an attached essay for review and the corresponding information/details for that essay. If you have not received these emails, please check your Spam/Junk folder.
Feedback should be submitted via the Google Form. In the Google Form, please write the author's pseudonym exactly as it appears in the email you received.
All guidelines for reviewing can be found here
T6: (1p or 2p) Compete with fellow students on 1000-city TSP - Attach:TSP_1000.txt
Announce your best on Slack channel #general for improving the so far best 1000-city TSP score and visual evidence (the image). In the report add the same (and possibly more), as on the Slack homework channel. Provide that evidence in your report - with image. Everyone gets 1 p here; but another one for (even being temporarily) the best result so far, as announced to the #general channel of the Slack.
T7: (1p) - Modify the TSP algorithm to work on the sparse graph (not every order is possible anymore). Report the results for the 1000-node TSP task. Illustrate the chosen path overlaid on the underlying sparse graph. Describe your method and discuss the computational complexity of your method now; compare the best results to the best results from the complete 1000 node graph version.