Week 5: Exercises

1. Xyz

What will this program print?

class Foo {
    public virtual int xyz() => 5;
}

class Bar : Foo {
    public override int xyz() => 10;
}

class Top {
    static void Main() {
        Bar b = new Bar();
        Foo f = b;
        Console.WriteLine(b.xyz());
        Console.WriteLine(f.xyz());
    }
}

2. Frequent Words

Write a method

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.

3. Hash Table Versus Tree

The C# 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 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.