The goal of this assignment is to gain some practice writing searching and sorting functions on arrays. Remember that when we give pre-conditions to functions, you may assume that these conditions hold when your function is called. You do not have to verify that they are true of the arguments, and your functions will only be tested on arguments that meet the pre-conditions. The functions to implement are specified in the interface file that is posted with the assignment. Here is a summary of those functions:
The bin_search() function is similar to the one in the Introduction to Computing text and that we developed in lab. For this version, though, it must return the smallest index i such that xs[i] = x. For full credit, your implementation must have O(lg n) cost. That means no linear searching!
unimodal_search() takes an array of values that strictly increases up to a point, then strictly decreases; the goal is to find the index with the maximum value. There are at least a couple of ways of doing this. One is a fairly direct adaptation of binary search and has cost O(log2 n). A cleverer implementation has cost O(log3 n). It could be the case that the maximum value is the first item in the array (i.e., there is no increasing part) or the last item in the array (i.e., there is no decreasing part).
ins_sort() implements insertion sort algorithm to sort the argument array. The idea behind insertion sort is that it iterates through the initial segments of xs (i.e., indices up to n). At step i, we ensure that xs[0], . . . , xs[i − 1] are rearranged into non-decreasing order (and hence after step n, xs[0], . . . , xs[n − 1] is rearranged into non-decreasing order, which is the goal). So what do we do for step i? At the end of the previous step, xs[0], . . . , xs[i−2] is in non-decreasing order, so the only value that is possibly “out of place” in xs[0], . . . , xs[i−1] is xs[i−1] itself. We can put it into place by comparing it to xs[i−2]. If xs[i−2] ≤ xs[i−1], then xs[i − 1] is not out of place, and so we’re done. Otherwise, swap xs[i − 1] and xs[i − 2]. Now xs[i − 1] is in place, but xs[i − 2] is possibly out of place. Compare it to xs[i − 3] and either stop (if xs[i − 3] is smaller, in which case xs[i − 2] is not out of place) or swap (if xs[i − 3] is bigger) and repeat the process again.
For all functions, include a comment in which you identify the asymptotic cost of your solution, along with a justification for why that is the cost.
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here