[Question 1] Shortest-Path and Minimum Spanning Tree
Fort canning park is just beside SMU, and it is where many SMU students jog to destress. In this question, you are provided with a data file that describes the graph as shown on the right (edge weights are ignored in the figure). The first line describes the number of vertices num-vert and the number of edges num-edge. Each of the next num-vert lines contains two decimals, which are the latitude and longitude of each vertex. This is then followed by num-edge lines on edge weights; each line contains a pair of vertex indices and the distance in meters between the two vertices, as the weight of the edge. You are given a Python code to read the data file and generate a figure like the one on the right. Each of you will be assigned with a vertex v to start with, please
(1) find the shortest paths from v to all other vertices; and
(2) construct a minimum spanning tree rooted at v
Your output (name it '[url removed, login to view]') should be in the following format:
The first line describes the distances from v to any vertex including v, separated by tab '\t', in the sequence of vertex indices. The distances should be all integers.
The second line is a post-order traversal of the minimum spanning tree rooted at v. Child with smaller index should appear first. Vertices are separated by tab '\t'.
No other information should be included, just the two lines mentioned above.
[Question 2] Best Restaurant in a neighborhood
In this exercise, you are employed by a F&B company to investigate existing restaurants in a
neighborhood. With the web crawling skills that you have learnt in class, you are to answer the
following questions from the F&B company with data from foursquare.com.
(1) What are the 5 most commented restaurants in the area?
(2) What are the 5 best restaurants in the area, by looking at the overall ratings?
(3) What are the 5 best restaurants in the area, by judging from the comments?
Each of you are given a different neighborhood to work with, which is a circle centered at one
MRT station with radius 400 meters (If you feel there are too few restaurants, you may increase
this limit to 800 meters). You need to submit both codes and results (the set of restaurants you
crawled, and the set of comments you crawled).