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 HashDictionary<K, V> that stores a dictionary using a hash table:

class HashDictionary<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. Frequent Words

Write a function

string[] topWords(string filename, int n)

that reads a file and returns an array of the n most frequent words in the file, listed in descending order of frequency. A word is any sequence of non-whitespace characters; comparisons are case-sensitive. If the file has fewer than n distinct words, return an array of all words in the file. Use the C# collection classes.

5. Hash Table Versus Tree

The C# standard library includes a class HashSet<T>, based on a hash table, and a class SortedSet<T>, based on a balanced binary tree.

a) Suppose that we insert N random integers into each of these data structures. Which one do you think will be faster? Perform an experiment that compares the performance for various values of N. Draw a graph (e.g. using Python and matplotlib) showing the results.

b) Now suppose that in each trial we insert N random integers, then remove all N integers. Compare the performance of the two data structures in this case.

c) Probably the class HashSet<T> rebuilds the hash table whenever its load factor exceeds a certain threshold. Design and perform an experiment to determine that threshold.

6. Family Tree

Consider this class for representing a person:

class Person {
    public string name;

    public Person[] children;
}

Write a static method show(Person[] a) that takes an array of Person objects. Every Person in the array will have a unique name. For every person p in the array, it is guaranteed that p's children (if any) also appear somewhere in the array. The objects in the array might be in any order.

The method should print out the names of all people, one per line, in some order such that each person's name appears before the names of their children.

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

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

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