Week 8: Exercises

1. Stair Climbing

A staircase has n steps from bottom to top. A person walks up the staircase, and can take up to m steps at a time. Write a function

int stairs(int n, int m)

that returns the number of different ways in which the person may climb the stairs.

2. Carrots and Parsley

A garden contains N plant beds, all in a row. Each bed will contain either carrots or parsley, but no two neighboring beds may both contain parsley.

a) Write a function void garden(int n) that takes N, the size of the garden, and prints out all possible ways that exist to plant these vegetables in the garden. For example, garden(5) might print

C C C
P C C
C P C
C C P
P C P

b) Write a function int ways(int n) that takes N, the size of the garden, and returns the number of possible ways that exist to plant these vegetables in the garden. For example, ways(5) will print 5.

3. Longest Ascending Subsequence

Write a function that takes an array of type int[]. The function should return the length of the longest ascending subsequence in the array, where a subsequence is not necessarily contiguous.

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 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. Box Stacking

A Box represents a box with a given width, height, and depth:

class Box {
    public int width, height, depth;

    public Box(int width, int height, int depth) {
        this.width = width; this.height = height; this.depth = depth;
    }
}

Write a method

int max_height(Box[] boxes)

that takes a set of boxes and determines the maximum possible height of a stack that can be formed from these boxes, assuming that you can place box b on box c only if b.width < c.width and b.depth < c.depth. You may not rotate the boxes in any way.

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

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

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