Programming 1, 2022-3
Week 9: Exercises

1. Vector Class

Write a class that represents an n-dimensional vector, and includes magic methods __add__ and __mul__. The __mul__ method should compute the dot product of two vectors. Use the zip() function in your implementations of __add__ and __mul__.

2. Matrix Addition

Write a function add() that takes two matrices, represented as lists of lists. You may assume that the matrices have the same dimensions. The function should return the sum of the matrices, again represented as a list of lists. Write the function in a single line, using list comprehensions and the zip() function.

3. 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.

4. First to Pass

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.

5. 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).

6. 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.

7. 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).

8. Power of a Function

Write a function fpower(f, n) that takes a function f(x) of a single variable, and return a function g(x) such that g(x) = f(f(...(f(x)))), where f is applied n times.

9. 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.

10. 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.