Lecture 10

Here are some notes about topics we covered in lecture 10.

For more details about exceptions, see the Essential C# textbook or the C# reference pages. Dynamic programming is covered in ch. 15 of Cormen, Introduction to Algorithms.

throw

The throw statement throws an exception, which can be any object belonging to the System.Exception class or any of its subclasses. The exception will pass up the call stack, aborting the execution of any methods in progress until it is caught with a try...catch block at some point. If the exception is not caught, the program will terminate.

try

The try statement attempts to execute a block of code. It may have a set of catch clauses and/or a finally clause.

A catch clause catches all exceptions of a certain type. For example:

  static void Main() {
    StreamReader reader;
    try {
      reader = new StreamReader("numbers");
    } catch (FileNotFoundException e) {
      WriteLine("can't find input file: " + e.FileName);
      return;
    }
    …

The code above will catch an exception of class FileNotFoundException, or of any subclass of it. When an exception is caught, the catch block (called an exception handler) executes. The catch block may itself rethrow the given exception, or even a different exception. If the catch block does not throw an exception, execution resumes below the try statement.

A finally clause will always execute, even if an exception is thrown inside the body of the try statement. For example:

  StreamReader reader = …;
  StreamWriter writer = …;
  try {
    while (reader.ReadLine() is string s)
      writer.WriteLine(transform(s));
  } finally {
    reader.Close();
    writer.Close();
  }

In this close, reader and writer will be closed even if an exception occurs within the try body (for example, within the transform method). Note that a finally clause does not itself catch an exception, which will continue to pass up the call stack.

using

Certain classes in the C# library implement the interface IDisposable, which has a single method:

  void Dispose ();

This method frees any external resources associated with an object. You should call it when you are finished using an object.

Fort example, the StreamReader and StreamWriter classes implement IDisposable. The Dispose() method in these classes performs the same task as the Close() method: it closes a file or other stream. It is especially important to call Close() or Dispose() when writing to a file; if you do not, some output may not be written. So to be sure that the file is closed in any case, you can write

StreamWriter w = new StreamWriter("output");
try {

  ... write to w ...

} finally {
  w.Dispose();
}

This pattern is so common that C# includes a statement called using that can be used for the same task. using takes a object that implements IDisposable and executes a block of code, disposing the object when the block exits:

StreamWriter w = new StreamWriter("output");
using (w) {
  ... write to w ...
}

Alternatively, you can bind a new variable inside a using statement:

using (StreamWriter w = new StreamWriter("output")) {
  ... write to w ...
}

dynamic programming

In class we talked about dynamic programming problems with a 2-dimensional structure. Here are the programs we saw:

longest palindromic subsequence

// Compute the longest palindromic subsequence of s.
  static string longestPalindromic(string s) {
    // len[i, j] is the length of the longest palindromic subsequence of
    // s[i .. j].
    int[,] len = new int[s.Length, s.Length];
    int from, to;
    for (from = s.Length - 1 ; from >= 0 ; --from) {
      len[from, from] = 1;
      for (to = from + 1 ; to < s.Length ; ++to) {
        len[from, to] =
          s[from] == s[to] ? 2 + len[from + 1, to - 1]
                           : Max(len[from, to - 1], len[from + 1, to]);
      }
    }
    
    // Now len[0, s.Length - 1] is the length of the longest palindromic
    // subsequence.  We now want the subsequence itself.  We need to build
    // the sequence from the outside inward, so we use two strings a and b
    // and will return (a + b).
    
    string a = "", b = "";
    from = 0;
    to = s.Length - 1;
    while (to >= from) {
      if (to == from) {
        a += s[from];
        break;
      }
      if (s[from] == s[to]) {
        a = a + s[from];
        b = s[to] + b;
        ++from;
        --to;
      } else if (len[from, to - 1] > len[from + 1, to])
        --to;
      else ++from;
    }
    
    return a + b;
  }

longest common subsequence

  // Compute the length of the longest common subsequence of s and t.
  static int lcs_len(string s, string t) {
    // len[i, j] is the length of the longest common subsequence of
    // s[0 .. (i - 1)] and t[0 .. (j - 1)].
    int[,] len = new int[s.Length + 1, t.Length + 1];
    
    for (int i = 1 ; i <= s.Length ; ++i)
      for (int j = 1 ; j <= t.Length ; ++j)
        len[i, j] = s[i - 1] == t[j - 1] ? 1 + len[i - 1, j - 1]
                                         : Max(len[i, j - 1], len[i - 1, j]);
                                         
    return len[s.Length, t.Length];
  }

subset sum

  // Does any subset of the integers in a have sum s?  If so, return the subset;
  // otherwise return null.
  static int[] subsetSum(int[] a, int s) {
    // b[i, j] is true if some subset of a[0 .. (i - 1)] adds up to j.
    bool[,] b = new bool[a.Length + 1, s + 1];
    b[0, 0] = true;   // we can make 0 from the empty set
    
    for (int i = 1 ; i <= a.Length ; ++i)
      for (int j = 0; j <= s ; ++j)
        b[i, j] = b[i - 1, j] ||                            // we can make j without a[i - 1]
                  a[i - 1] <= j && b[i - 1, j - a[i - 1]];  // we can make j by adding a[i - 1]
    
    if (!b[a.Length, s])
      return null;  // sum is not possible
      
    // Now construct the integers in the set.
    List<int> result = new List<int>();
    int k = s;
    for (int i = a.Length ; i > 0 ; --i) {
      if (!b[i - 1, k]) {
        result.Add(a[i - 1]); 
        k -= a[i - 1];
      }
    }
    
    return result.ToArray();
  }