Week 10 – Optional Exercises

1. Which type variables in these interfaces can be marked as covariant?

interface Comparer<T> {
  int Compare (T x, T y);
}

interface Map<K, V> {
  V this[K key] { get; set; }
}

interface ReadOnlyMap<K, V> {
  V this[K key] { get; }
}

interface Stream<T> {
  bool next();  // true if there are any more values
  T val { get; }  // the current value
}

2. Write a program that reads two text files and print a boolean value indicating whether the files contain the same set of words, ignoring the number of occurrences of each word. For this exercise, consider a word to be any sequence of non-space characters separated by spaces.

3. Write a generic extension method reduce that combines elements of an array given a function that combines two values. For example,

int[] a = { 2, 3, 5, 7 };
int k = a.reduce((i, j) => i + j);  // now k == 17

4. You are given the following method:

static int add(int i, int j) => i + j;

Using add and without using any arithmetic operators, write a method pow(int a, int b) that computes a^b. The preceding method reduce may be helpful.

5. Write a generic extension method sortBy that sorts an array of type T[] given a delegate that maps T to int. For example:

string[] a = { "lemon", "grape", "pineapple", "pear", "fig" };
string[] b = a.sortBy(s => s.Length);  // { "fig", "pear", "lemon", "grape", "pineapple" }

You may use a bubble sort or any other sorting algorithm you like.

6. Write a program that reads a list of edges in an undirected graph and prints a boolean value indicating whether the graph is fully connected. The first input line contains the number of vertices N, and each subsequent line contains a pair of integers indicating two vertices that are joined by an edge. Assume that vertices are numbered from 0 to (N – 1).

7. Repeat the previous exercise, assuming that vertices are labeled with names rather than integers. Each input line contains the name of two directly connected vertices, separated by a space.

8. Write a program that reads a list of edges in an undirected graph along with the ids of two vertices U and V. The program should print an integer indicating the length of the shortest path from U to V, or the integer -1 if V is not reachable from U. Assume that the first input line contains the number of vertices N and that vertices are numbered from 0 to (N – 1).

9. Consider this interface:

interface Stream<T> {
  bool next();  // true if there are any more values
  T val { get; }  // the current value
}

Write an extension method filter that transforms a Stream by keeping only values for which a given condition is true.