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

In the lecture we saw a class IntStack with a subclass AvgStack including a property double avg that returns the average of all values on the stack in O(1).

Write a subclass MaxStack that is like IntStack but also includes a property double max that returns the maximum of all values on the stack in O(1). If the stack is empty, the max property should return the value double.NaN.

3. Circular Queue

At the end of the lecture we saw a hypothetical collection class hierachy that looked like this:

Implementing this entire hierarchy would be a significant project! In this exercise we'll implement just a small part of it, namely the ICollection, IStack, and IQueue interfaces, plus the Deque class. Choose appropriate argument types and return types for the methods in these interfaces. Implement Deque using a fixed-size array plus fields that hold the indices of the first and last elements in the queue. The elements in the queue may wrap past the end of the array back to the beginning; this is called a circular queue, and will allow you to implement all operations in O(1). If the array is full and the user attempts to push or enqueue a value, throw an exception (e.g. throw new Exception("queue is full")). Similarly, throw an exception if the queue is empty and the user attempts to pop or dequeue.

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