Week 11: Exercises

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

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

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

4. Edit Distance

The edit distance between two strings s and t is the smallest number of edits that can transform s into t, where each edit is one of the following operations:

• deleting a character

• inserting a character

• replacing one character with another

Write a method that takes strings s and t and returns the edit distance between s and t.

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

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