Week 6: Exercises

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

2. Binary Tree

In the lecture we began to write a class holding a set of values in a binary search tree:

class TreeSet<T> where T: IComparable<T> {
    class Node {
        public T val;
        public Node? left, right;

        public Node(T val) { this.val = val; }
    }

    Node? root;

    public bool contains(T x) {
        Node? p = root;
        while (p != null) {
            int c = x.CompareTo(p.val);
            if (c == 0)
                return true;
            else if (c < 0)
                p = p.left;
            else
                p = p.right;
        }
                
        return false;
    }

    // more methods here: insert(), delete(), ...
}

a) Write an insert() method, giving it an appropriate type.

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) Add a method T[] range(T a, T b) that returns a sorted array of all values x such that a ≤ x ≤ b.

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

3. Dictionary

Consider a generic class Dictionary<K, V> that stores a dictionary using a hash table:

class Dictionary<K, V> where K : IComparable<K> {
    class Node {
        public K key;
        public V val;
        public Node? next;

        public Node(K key, V val) {
            this.key = key; this.val = val;
        }
    }

    Node?[] a;  // array of hash chains
    
    ...
}

Complete the implementation of this class, including an indexer that lets the caller assign and lookup key/value pairs conveniently.

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

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

6. Sort With Comparer

Write a generic function

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.

7. Euler 1

Solve Project Euler Problem 1 in a single line of code using Linq methods or Linq syntax:

Find the sum of all the multiples of 3 or 5 below 1000.