Week 7 – Optional Exercises

1. Write a program that reads two decimal integers, one per line, and writes the last two digits of their product in base 7. The integers may be arbitrary large (i.e. they might not even fit in memory).

2. Let M be a constant. Consider the string hashing function we saw in the lecture:

 int hash(string s) {  // return a value from 0 .. M - 1
    int h = 0;
    foreach (char c in s)
      h = (h * 65536 + c) % M;
    return h;
  }

The function interprets a string as a long integer and returns its value mod M. If M is sufficiently large, this function may return an incorrect result due to overflow. What is the smallest value for M for which this may happen? How can you modify the function to work for larger values of M?

3. Consider the string hashing function from the previous exercise. Write a method printCollisions that takes a string s. The method should print three different strings that all hash to the same value as s. The strings may include any characters representable in the 'char' data type.

4. What will this program print?

class MyException : Exception { }

static class Test {
  static int foo(int i) {
    try {
      WriteLine("a " + i);
      if (i == 0)
        throw new MyException();
      WriteLine("b " + i);
      return foo(i - 1);
    } catch (MyException e) {
      WriteLine("c " + i);
      if (i < 2)
        throw e;
      return i;
    } finally {
      WriteLine("d " + i);
    }
  }  
  
  static void Main(string[] args) {
    WriteLine("e " + foo(3));
  }
}

5. Will the following method terminate? If so, what number will it print?

  static void Main(string[] args) {
    uint sum = 0;
    for (uint i = 1 ; i != 0 ; ++i)
      sum += i;
    WriteLine(sum);
  }

6. Will the following method terminate? If so, what number will it print?

  static void Main(string[] args) {
    int sum = 0;
    for (int i = 1 ; i != 0 ; ++i)
      sum += i;
    WriteLine(sum);
  }

7. Write a method that takes two strings and returns true if they contain the same set of characters. For example, "aaabc" and "cccba" contains the same set of characters, i.e. { 'a', 'b', 'c' }.