Week 6: Exercises

1. Filter

Write a generic method

T[] filter<T>(T[] a, Predicate<T> p)

that selects only the elements of a for which the given predicate is true.

2. Max By

Write a generic method max_by() that takes an array plus a function f. The method should return the array element x for which f(x) is the greatest, or null if the array is empty. For example:

string[] a = { "red", "yellow", "blue", "green" };
WriteLine(max_by(a, s => s.Length));   // writes "yellow"

The method should work for any array type and for any function that maps the array type to a comparable type.

3. Sort

Write a generic method sort() that can sort an array of elements of any type T that implements the IComparable<T> interface. You may use any sorting algorithm that you like.

4. Sort With Comparer

Write a generic method

void sort<T>(T[] a, Comparison<T> f)

that can sort an array using an arbitrary function to compare elements. The delegate type Comparison<T> is defined in the standard library as follows:

delegate int Comparison<T>(T x, T y);

Given two objects x and y of type T, a Comparison<T> returns

• a negative value if x is less than y
• 0 if x equals y
• a positive value if x is greater than y

You may use any sorting algorithm that you like.

5. Binary Tree

Consider this class holding a set of values in a binary search tree:

class TreeSet<T> where T: IComparable<T> {
    Node? root;

    class Node {
        public T val;
        public Node? left, right;

        public Node(T val, Node? left, Node? right) {
            this.val = val; this.left = left; this.right = right;
        }
    }

    public bool contains(T val) { ...  }
}

a) Write the contains() method.

b) Add a constructor TreeSet(T[] a) that builds a TreeSet from an array a. The resulting tree should be balanced. Do not modify the array.

c) The class orders values by their natural ordering as defined by IComparable<T>. Modify the class so that the caller can specify an alternate ordering. For example, the caller might want to create a TreeSet<string> where the strings are ordered by length, or a TreeSet<int> where integers are ordered by absolute value.

d) Add a method T[] range(T a, T b) that returns a sorted array of all values x such that a ≤ x ≤ b.

e) Add a method void validate() that verifies that the structure satisfies the ordering requirements of a binary tree. If the structure is invalid, throw an exception with the message "invalid".