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