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

Write a function

Dictionary<string, string> flip(Dictionary<string, string> d)

that takes a dictionary from strings to strings and returns a flipped version of the dictionary. For example, if d maps "dog" to "pes", then the returned dictionary will map "pes" to "dog". Assume that all values in the dictionary d are unique.

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

4. Collection Classes

Consider the following design for a hierarchy of collection classes and interfaces. (These are not the same as the collection classes in the C# standard library, though they are somewhat similar.)

We have not yet learned to write generic classes, so in this exercise we will assume that all elements are strings. For example, IStack is a stack of strings, IQueue is a queue of strings, and so on.

a) Write the interfaces ICollection, IStack, IQueue, and ISet.

b) Implement as many of the classes above as you can.

5. 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 (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. Abstract Syntax Tree

Consider a tiny programming language that we will call W. It has the following features:

• integer constants

• variables

• the integer operators +, -, *, /, %

• the boolean operators ==, !=, >, >=, <, <=

• assignment statements

• while statements

• a function print()

Here is a program in W that computes the sum of integers from 1 to 100:

x = 100
s = 0

while (x > 0) {
    s = s + x
    x = x - 1
}

print(s)

Here is a program that uses Euclid's algorithm to compute the GCD of two integers:

x = 1056
y = 668

while (y > 0) {
    t = x % y
    x = y
    y = t
}

print(t)

Variables can hold only integers, so boolean operators can be used only inside a 'while' condition. For example the assignment, 'x = y < z' is illegal. Arithmetic expressions may contain parentheses and may be nested. For example, 'x = (a + b) * (c + d)' is legal.

Design and write a set of C# classes that can hold an abstract syntax tree for a W program. There should be a class Program that represents an entire program.