1. Exceptions

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));
  }
}

2. Maximum Subarray

Write a method void maxSub(int[] a, out int start, out int end) that finds the contiguous subarray in a with a maximal sum, and returns the indices of the start and end of the subarray.

3. Longest Palindromic Substring

Modify the longest palindromic subsequence method from lecture to return the longest contiguous palindromic substring of a string s.

4. Longest Common Subsequence

Write a method that returns the longest common subsequence of two strings s and t, where a subsequence is not necessarily contiguous.

5. Subset Sum

Write a method takes an integer array a[] and an integer s, and returns true if any subset of the integers in a have sum s.

6. Dragon's Den II

Modify the Dragon's Den homework exercise for the situation in which the treasure mound contains only a single instance of each treasure.

7. Square Submatrix

Write a method that takes a square matrix a[,] containing only 0s and 1s. The method should return the offset and size of the largest square submatrix of a that contains only 1s.

8. Partition Count

Write a method int partitions(int n) that returns the number of possible partitions of the integer n, i.e. subsets of positive integers that add up to n.

9. Longest Path

Consider the following representation for directed weighted graphs. This class represents edges:

class Edge {
  public int dest;  // destination
  public double weight;
}

We can represent a graph in adjacency-list representation by a jagged array of type Edge[][]. If g is an array of this type, then g[i] is a subarray of edges leading from the i-th vertex.

Write a method int[] longest(Edge[][] graph, int start, int end) that takes a directed acyclic graph and finds the longest weighted path from vertex start to vertex end. The method should return a list of vertices along the path, including start and end. If no path exists between the vertices, return null.

10. Graph Coloring

Write a method that takes a connected undirected graph G, represented as a jagged array. The method should determine whether it is possible to color the graph with three colors (red, green, blue) such that no two adjacent vertices have a same color. If it is, it should print out a valid coloring.

11. Longest Path

Write a method that takes an undirected graph G (represented as a jagged array) with vertices numbered 1 .. N. The method should return the length of the longest path from vertex 1 to vertex N. A path cannot cannot contain the same vertex twice.