Homework Assignment 1

1. Look at exercise 1.2.9, which describes an algorithm for finding the smallest distance between any two elements in an array.
   1. Describe in plain English why the algorithm is correct.
   2. There are at least two improvements we can make to improve this algorithm. What are they? Can you think of more improvements?
   3. Can you think of possibly a different approach to this problem?
2. Look at exercise 1.3.1, which describes a sorting algorithm by performing “comparison counting”, i.e. for each element counting the number of elements that are less than it, and using this information to sort the elements.
   1. Apply the algorithm to sort the list \(60\), \(35\), \(81\), \(98\), \(14\). Show clearly the steps you follow, and make sure to follow the specific algorithm and not some other sorting method.
   2. Is this a stable sorting algorithm? Is it an in-place sorting algorithm? Explain.
3. Exercise 2.2.1: Using the appropriate notation, indicate the time efficiency class of sequential search in the worst case, the best case and the average case.