Week 8: Exercises

1. Euler 1 and 2

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

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

b) The Fibonacci numbers are the sequence

1, 1, 2, 3, 5, 8, 13, 21, ...

Write a function that produces an infinite enumeration of Fibonacci numbers. Then solve Project Euler Problem 2 in a single line using Linq methods:

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

2. Binary Tree

Consider this binary tree class:

class TreeSet<T> where T: IComparable<T> {
    Node? root;

    class Node {
        public T val;
        public Node? left, right;

        public Node(T val, Node? left, Node? right) {
            this.val = val; this.left = left; this.right = right;
        }
    }

    public bool contains(T val) { ...  }
}

a) The class always orders values by their natural ordering as defined by IComparable<T>. Modify the class so that the caller can specify an alternate ordering. For example, the caller might want to create a TreeSet<string> where the strings are ordered by length, or a TreeSet<int> where integers are ordered by absolute value.

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. If the tree contains duplicate elements, those duplicates should be retained in the returned array.

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