Introduction to Computer Programming: Lab 5

10 kinds of searching (and sorting)


Goals


Instructions


Exercises

  1. Complete is_binary(items) so it returns True if items is a sequence consisting entirely of 1's and 0's and, if it has more than one bit in it, its leading bit (the one at the end of the list) is a 1. Otherwise it returns False.

    >>> is_binary([0])
    True
    >>> is_binary([1])
    True
    >>> is_binary([])
    False
    >>> is_binary([1, 1, 1, 0, 0, 0, 0, 1])
    True
    >>> is_binary([1, 0])
    False
  2. Complete from_bits(bits) so that it returns the number corresponding to the sequence of 0s and 1s in the list (or tuple) bits. The order of the bits should be (visually) the opposite of the order we are used to, so that the bit in position 0 corresponds to the one's place, in position 1 the two's place, in position 2, the four's place and so on. Examples:

    >>> from_bits([0])
    0
    >>> from_bits([1])
    1
    >>> from_bits([0, 1, 1, 1])   # which is 1110 in binary: 8 + 4 + 2 = 14
    14
    >>> from_bits([1, 1, 1, 0, 0, 0, 0, 1])   # 10000111: 128 + 4 + 2 + 1 = 135
    135

    You can assume that bits is not empty, consists entirely of 1's and 0's and that if it has more than one bit in it, its leading bit (the one at the end of the list) is a 1. (In other words that it satisfies is_binary.)


  3. Complete make_random_increasing(n, lo, hi) so it returns a list of n randomly increasing numbers, where the difference between any two consecutive numbers in the list is at least lo but less than hi. Examples:

    >>> make_random_increasing(0, 100, 1000)
    []
    >>> make_random_increasing(5, 0, 10)
    [3, 12, 16, 17, 23]
    >>> make_random_increasing(10, 100, 200)
    [186, 373, 486, 650, 837, 1015, 1203, 1325, 1458, 1595]

    (Hint: this might be very similar to make_random_list, which we developed last week, and can also be found in this week's example file.)


  4. Complete the function binary_search(items, x) so that it returns the position of x in the ordered list items if x is in the list; otherwise it returns None. Follow the model of guess_hi_lo in the example file. Be sure to test your function thoroughly.

  5. Examine the functions linear_search_per_sec, binary_search_per_sec, and compare_search. Experiment using the latter to quantify how much more efficient binary search is than linear search.


  6. Insertion sort works similarly to how some people organize a hand of playing cards: for each item (card) picked up, it is inserted into the list (hand) already being formed so as to preserve order. Consider having this sequence of four numbers: 7, 2, 6, 5. If we first just take 7, we can consider that list, [7] to be in order. Then if we insert 2, it must go before the 7, so the 7 has to be slid over one position and the list becomes [2, 7]. To insert 6, we the 7 has to be slid over one more position (but the 2 can remain), so we get [2, 6, 7], to insert 5, the 6 and 7 each need to be slid over (and, again, the 2 can remain) to finally get the ordered list [2, 5, 6, 7].

    Complete insert(items, i, x) so that it inserts x into the initially ordered list items so as to preserve order. i is the position through which at least items is ordered (i.e., the slice items[:i] can be assumed to be in order. You can assume that the length of items is larger than i (in other words, there is already room on the list to insert x without having to perform an append operation. insert is side effecting and does not return anything. Examples:

    >>> ns = [None, None, None, None]   # the None's are just placeholders for this example
    >>> insert(ns, 0, 7)
    >>> ns
    [7, None, None, None]
    >>> insert(ns, 1, 2)
    >>> ns
    [2, 7, None, None]
    >>> insert(ns, 2, 6)
    >>> ns
    [2, 6, 7, None]
    >>> insert(ns, 3, 5)
    >>> ns
    [2, 5, 6, 7]
  7. Complete insertion_sort(items) so that it sorts the list items into increasing order. You can use the is_sorted function from the example file to test your results as in:

    >>> ns = make_random_list(1000, 0, 10000)
    >>> is_sorted(ns)
    False
    >>> insertion_sort(ns)
    >>> is_sorted(ns)
    True
  8. Examine the function compare_random_sorts. Experiment using it to try and measure the relative speeds of selection sort and insertion sort. Which algorithm seems to be faster?

  9. Complete compare_near_sorts so that it is just like compare_random_sorts but that instead of sorting random lists, it sorts lists that are nearly in order meaning they are in order except for a few pieces - you can generate such lists by using make_random_increasing and the supplied shuffle_k (from the example file). Experiment using compare_near_sorts. How do the two algorithms fare on data that is nearly sorted as compared to the previous problem? What can you conclude about the two different sorting algorithms?