Data Structure and Algorithms || EX01: Due to 17th of Feb at 11:59 PM. 1- Several possible algorithms might come to mind to solve this problem. Perhaps the most popular idea is the nearest-neighbor heuristic algorithm is used to solve the shortest tour problem. Starting from some point PO, we walk first to its nearest neighbor P1 . From P1 , we walk to its nearest unvisited neighbor, thus excluding only PO as a candidate. We now repeat this process until we run out of unvisited points, at which time we return to PO to close off the tour. In pseudocode, the nearest-neighbor heuristic looks like this: Figure: A good example for the nearest neighbor heuristic NearestNeighbor TSP(P) Pick and visit an initial point PO from P p = mo i = 0 While there are still unvisited points i=i+1 Select Pi to be the closest unvisited point to Pi-1 Visit Bio Return to from M-1 This algorithm has a lot to recommend it. It is simple to understand and implement. It makes sense to visit nearby points before we visit faraway points if we want to minimize the total travel time. The algorithm works perfectly on the example in Figure v. The nearest neighbor rule is very efficient, for it looks at each pair of points (Pi, Pj) at most twice, once when adding Pi to the tour, the other when adding Pj . Against all these positives there is only one problem. This algorithm is completely wrong. L0L .24 LL Figure: A bad example for the nearest neighbor heuristic Explain how can it be wrong? 2- The knapsack problem is as follows: given a set of integers S= {s1, s2, . sn} and a target number T, find a subset of S which adds up exactly to T. For example, there exists a subset within S = {1, 2, 5, 9, 10} that adds up to T = 22 but not T = 23. Find counterexamples to each of the following algorithms for the knapsack problem. That is, giving an S and T such that the subset is selected using the algorithm does not leave the knapsack completely full, even though such a solution exists. (a) Put the elements of S in the knapsack in left to right order if they fit, i.e. the first-fit algorithm. (b) Put the elements of S in the knapsack from smallest to largest, i.e. the best-fit algorithm. (c) Put the elements of S in the knapsack from largest to smallest. 3- Prove the correctness of the following sorting algorithm. function bubblesort (A : list[1 ...n]) var int i, j for i from n to 1 for j from 1 to i - 1 if (A[j] > A[j + 1]) swap the values of A[j] and A[j + 1] + 4- A sorting algorithm takes 1 second to sort 1,000 items on your local machine. How long will it take to sort 10,000 items. . . (a) if you believe that the algorithm takes time proportional to n2, and (b) if you believe that the algorithm takes time roughly proportional to n log n? Data Structure and Algorithms || EX01: Due to 17th of Feb at 11:59 PM. 1- Several possible algorithms might come to mind to solve this problem. Perhaps the most popular idea is the nearest-neighbor heuristic algorithm is used to solve the shortest tour problem. Starting from some point PO, we walk first to its nearest neighbor P1 . From P1 , we walk to its nearest unvisited neighbor, thus excluding only PO as a candidate. We now repeat this process until we run out of unvisited points, at which time we return to PO to close off the tour. In pseudocode, the nearest-neighbor heuristic looks like this: Figure: A good example for the nearest neighbor heuristic NearestNeighbor TSP(P) Pick and visit an initial point PO from P p = mo i = 0 While there are still unvisited points i=i+1 Select Pi to be the closest unvisited point to Pi-1 Visit Bio Return to from M-1 This algorithm has a lot to recommend it. It is simple to understand and implement. It makes sense to visit nearby points before we visit faraway points if we want to minimize the total travel time. The algorithm works perfectly on the example in Figure v. The nearest neighbor rule is very efficient, for it looks at each pair of points (Pi, Pj) at most twice, once when adding Pi to the tour, the other when adding Pj . Against all these positives there is only one problem. This algorithm is completely wrong. L0L .24 LL Figure: A bad example for the nearest neighbor heuristic Explain how can it be wrong? 2- The knapsack problem is as follows: given a set of integers S= {s1, s2, . sn} and a target number T, find a subset of S which adds up exactly to T. For example, there exists a subset within S = {1, 2, 5, 9, 10} that adds up to T = 22 but not T = 23. Find counterexamples to each of the following algorithms for the knapsack problem. That is, giving an S and T such that the subset is selected using the algorithm does not leave the knapsack completely full, even though such a solution exists. (a) Put the elements of S in the knapsack in left to right order if they fit, i.e. the first-fit algorithm. (b) Put the elements of S in the knapsack from smallest to largest, i.e. the best-fit algorithm. (c) Put the elements of S in the knapsack from largest to smallest. 3- Prove the correctness of the following sorting algorithm. function bubblesort (A : list[1 ...n]) var int i, j for i from n to 1 for j from 1 to i - 1 if (A[j] > A[j + 1]) swap the values of A[j] and A[j + 1] + 4- A sorting algorithm takes 1 second to sort 1,000 items on your local machine. How long will it take to sort 10,000 items. . . (a) if you believe that the algorithm takes time proportional to n2, and (b) if you believe that the algorithm takes time roughly proportional to n log n