Week 9: Exercises

1. Subset Sum

Write a function that takes an array a[] of integers and an integer k, and returns true if any subset of a (which need not be contiguous) has sum k. Use dynamic programming.

2. Square Submatrix

Write a function 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. Use dynamic programming.

3. Text Segmentation

a) Write a function that takes an array string words[] containing a set of words, plus a string s. The function should return true if s can be written by concatenating one or more words from the given set. A word may be used more than once in the concatenation. For example, if words[] = { "pot", "potato", "to", "topo" } and s = "topottopopotatotopo", the function will return true, since s = "to" + "pot" + "topo" + "potato" + "topo". A solution that backtracks may have exponential time in the worst case. Use dynamic programming for an efficient solution.

b) Modify your function so that it returns the number of ways that a string s may be written by concatenating words from the given set.

4. Smallest Number of Coins

a) Write a method that takes an array coins[] with the values of various coins, plus an integer 'sum'. The method should return the smallest number of coins that can form the given sum. Each coin may be used only once in the sum.

b) Modify your method so that it returns an array with the actual coin values needed to form the sum minimally.

5. Partition Count

Write a function 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.

6. Longest Common Subsequence

Write a function that takes two strings and returns the longest common subsequence of the strings, i.e. the longest (not necessarily contiguous) subsequence that belongs to both strings. Use dynamic programming.

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

8. Longest Path II

Write a function 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. No efficient algorithm is known for solving this problem, so you will need to perform an exhaustive search of all possible paths.

More Dynamic Programming

For more dynamic programming practice, you can find many exercises at