Week 9: Exercises

1. Index of Largest

Write a function index_largest(a) that takes a list a and returns the index of the largest element in a. Use the built-in function max() with a key function.

2. First to Pass

a) Write a function first(f, l) that takes a function f and a list l. The function should return the index of the first value x in l such that f(x) is true. If there is no such value, return -1.

b) Using the function you wrote in part (a), write a function first_begin(ss, c) that takes a list of strings ss and a character c, and returns the index of the first string in the list that begins with the character c, or -1 if there is no such string.

3. Bubble Sort with Key

In the lecture we saw this bubble sort implementation with a key function f:

# Sort the list a, where we consider x to be greater than y
# if f(x) > f(y).
def sort_by(a, f):
    n = len(a)
    for i in range(n - 1, 0, -1):  # n - 1, ... 1
        for j in range(i):
            if f(a[j]) > f(a[j + 1]):
                a[j], a[j + 1] = a[j + 1], a[j]

This function will call f up to O(N²) times, where N is the length of a. Rewrite the function so that it calls f only N times. Hint: First generate a list of pairs; each pair will contain an element x from a, plus the value f(x).

4. Time It

a) Write a function time_it(f, n) that calls the function f n times and returns the average time (in seconds) of each call to f. Use the library function time.time() to calculate the elapsed time.

b) Consider these two functions that compute the sum of all integers i in the range 0 ≤ i < 1,000,000:

def sum1():
    return sum(range(1_000_000))

def sum2():
    t = 0
    for x in range(1_000_000):
        t += x
    return t

Use your time_it() function to determine whether one of these functions is significantly faster than the other.

5. Bijective Function

Write a function bijective(f, n) that takes a function f whose domain and range are the integers 0 .. n – 1. The function should return True if f is bijective, i.e. f is both injective (i.e. f(x) ≠ f(y) whenever x ≠ y) and surjective (for every y in the range 0 ≤ y < n, there is some x such that f(x) = y).

6. Recursive Binary Search

Write a function bsearch(a, x) that performs a binary search to look for the value x in the sorted array a. The function should return True if x was found, otherwise false. Perform the search recursively, using a nested recursive helper function. Be sure that your function will run in O(log N) time. (If you use array slices, it probably will not!)

7. Monotonic Search

Write a function search(f, y, lo, hi, epsilon) takes a function f of a single variable, plus values y, lo, hi and epsilon. The function f is guaranteed to be monotonic, i.e. f(x₁) < f(x₂) whenever x₁ < x₂. The function should find some value x in the range lo ≤ x ≤ hi such that |f(x) – y| <= epsilon. The function should return x, or None if there is no such value within the given range lo .. hi. Hint: Use a binary search.

8. Monotonic Search Without Bounds

As a more challenging variant of the previous exercise, write a function search1(f, y, epsilon) that takes a monotonic function f of a single variable, plus values y and epsilon. f is guaranteed to be defined on all real numbers and it is guaranteed that there is some value x such that f(x) = y. The function should return a value x' such that |f(x') – y| <= epsilon.