template.c :

#include #include #include

#define FILE_PATH_1 "../Desktop/berlin52.txt" // EDIT THIS LINE #define FILE_PATH_2 "../Desktop/burma14.txt" // EDIT THIS LINE

#define SIZE_1 52 // DO NOT EDIT THIS LINE #define SIZE_2 14 // DO NOT EDIT THIS LINE

typedef struct { // DO NOT EDIT THIS LINE int id; // DO NOT EDIT THIS LINE double x; // DO NOT EDIT THIS LINE double y; // DO NOT EDIT THIS LINE }POINT ; // DO NOT EDIT THIS LINE

POINT *read_file(); // DO NOT EDIT THIS LINE double greedy(POINT *problem, int idx); // DO NOT EDIT THIS LINE double get_distance(POINT p1, POINT p2); // DO NOT EDIT THIS LINE

int main() {

clock_t start, end;

POINT *TSP = read_file(); // Read from txt file and initializing TSP instance(array of points) start = clock();

double min_distance = greedy(TSP, 0) // Starting index of the city chosen arbitrarily between 0-SIZE end = clock();

printf(" Minimum distance: %.2f ", min_distance); printf(" Function took %f seconds to execute ",(double)(end - start) / (double)CLOCKS_PER_SEC); return 0; }

POINT *read_file(){ POINT *instance = malloc(sizeof(POINT) * SIZE_1); // DO NOT FORGET TO CHANGE THE SIZE OF INSTANCE !! return instance; }

double get_distance(POINT p1, POINT p2){ return 0.0; }

double greedy(POINT *problem, int idx){ // Don't forget to print your solution before return the total distance! return 0.0; }

Burma.txt

1,16.47,96.10 2,16.47,94.44 3,20.09,92.54 4,22.39,93.37 5,25.23,97.24 6,22.00,96.05 7,20.47,97.02 8,17.20,96.29 9,16.30,97.38 10,14.05,98.12 11,16.53,97.38 12,21.52,95.59 13,19.41,97.13 14,20.09,94.55

Berlin.txt

1,565.0,575.0 2,25.0,185.0 3,345.0,750.0 4,945.0,685.0 5,845.0,655.0 6,880.0,660.0 7,25.0,230.0 8,525.0,1000.0 9,580.0,1175.0 10,650.0,1130.0 11,1605.0,620.0 12,1220.0,580.0 13,1465.0,200.0 14,1530.0,5.0 15,845.0,680.0 16,725.0,370.0 17,145.0,665.0 18,415.0,635.0 19,510.0,875.0 20,560.0,365.0 21,300.0,465.0 22,520.0,585.0 23,480.0,415.0 24,835.0,625.0 25,975.0,580.0 26,1215.0,245.0 27,1320.0,315.0 28,1250.0,400.0 29,660.0,180.0 30,410.0,250.0 31,420.0,555.0 32,575.0,665.0 33,1150.0,1160.0 34,700.0,580.0 35,685.0,595.0 36,685.0,610.0 37,770.0,610.0 38,795.0,645.0 39,720.0,635.0 40,760.0,650.0 41,475.0,960.0 42,95.0,260.0 43,875.0,920.0 44,700.0,500.0 45,555.0,815.0 46,830.0,485.0 47,1170.0,65.0 48,830.0,610.0 49,605.0,625.0 50,595.0,360.0 51,1340.0,725.0 52,1740.0,245.0

Task 1: Implement read_file() function for parsing text data to your POINT struct for both problem instances. This function must return an array of POINT. You have to understand that each array represents a different TSP problem and also their size are different from each other. You can add your utility functions as many as you want Task 2: Implement get_distance() function for calculating the distance between two points using following formula: B(xg.yo) 2 d= V(, - x) + (y; ya) YA "A(XAYA) XB Task 3: Implement greedy() function for solving both two problem instance. Here is your pseudocode of the greedy algorithm: Step 1: Pick an arbitrary city and call it city 1. Step 2: Find a city with the smallest distance from city 1, and call it city 2. Step 3: Find a city in the rest of the n- 2 cities with the smallest distance from city 2. Step 4: Output the total distance of your solution. Your function should print your solution tour and its total distance. After that, you should run your code 10 times for each instance and fill the test results table below: Burma14 Berlin52 Best Run Time (ms) Best Distance Average Run Time (ms) Average Distance Task 4: Write a report that includes the following parts: Time complexity analysis Test results Your report must be in PDF format and a maximum of 1 pages long