Week 9: 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

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.

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.

7. Arithmetic Expression

Write a program that evaulates an arithmetic expression. The first input line will contain an expression of a single variable x. The second input line will contain an integer: the value of x. The program should print the value of the expression.

The expression will be in the language defined by this context-free grammar:

digit = '0' | '1' | ... | '9'

int = digit

var = 'x'

op = '+' | '-' | '*'

expr =
    int
  | var
  | '(' expr op expr ')'

Whitespace may appear anywhere in the input.

Sample input:

((2 + x) * (3 + (x * x)))
2

Output:

28

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

9. Mini-Sudoku

A mini-Sudoku puzzle looks like this:

To solve the puzzle, you must place a number from 1 to 4 in every square so that the numbers in every row, column, and mini-square are distinct.

Write a method that reads a mini-Sudoku puzzle from standard input. Empty squares will be represented by the number 0:

3040
0103
2300
1002

The method should print out a solution to the puzzle if it can find one, otherwise 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 II

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