1)Show that the problem can be solved using sorting.
2)Give a divide and conquer algorithm that does not use sorting. The advantage of this approach is that it generalizes to points in higher dimensions.
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.Part 1 – Sorting
Using sorting, the problem can be solved in two steps:
• we apply a sorting algorithm to order the points by their x-coordinate
• we linearly iterate through the sorted list, compute the distance between adjacent points and update the minimum with every occasion
For this algorithm, the running time complexity is also O(nlogn)+O(n)= O(nlogn) (assuming we use a sorting algorithm which runs in O(nlogn) time like MergeSort or HeapSort)....
By purchasing this solution you'll be able to access the following files: