From the book
CREATIVE PROBLEMS
From the book
From the book
From the book
CREATIVE PROBLEMS
- Sorting three numbers. Suppose that the variables a, b, c, and t are all of the same numeric primitive type. Show that the following code puts a, b, and c in ascending order:
- Binomial distribution. Estimate the number of recursive calls that would be used by the code
- Remove duplicates. Modify the test client in BinarySearch to remove any duplicate keys in the whitelist after the sort.
- Equal keys. Add to BinarySearch a static method rank() that takes a key and a sorted array of int values (some of which may be equal) as arguments and returns the number of elements that are smaller than the key and a similar method count() that returns the number of elements equal to the key. Note : If i and j are the values returned by rank(key, a) and count(key, a) respectively, then a[i..i+j-1] are the values in the array that are equal to key.
- Array exercise. Write a code fragment that creates an N-by-N boolean array a[][] such that a[i][j] is true if i and j are relatively prime (have no common factors), and false otherwise.
- Random connections. Write a program that takes as command-line arguments an integer N and a double value p (between 0 and 1), plots N equally spaced dots of size .05 on the circumference of a circle, and then, with probability p for each pair of points, draws a gray line connecting them.
- Histogram. Suppose that the standard input stream is a sequence of double values. Write a program that takes an integer N and two double values l and r from the command line and uses StdDraw to plot a histogram of the count of the numbers in the standard input stream that fall in each of the N intervals defined by dividing (l , r) into N equal-sized intervals.
- Matrix library. Write a library Matrix that implements the following API:
- Filtering. Which of the following require saving all the values from standard input (in an array, say), and which could be implemented as a filter using only a fixed number of variables and arrays of fixed size (not dependent on N)? For each, the input comes from standard input and consists of N real numbers between 0 and 1.
- Print the maximum and minimum numbers.
- Print the median of the numbers.
- Print the k th smallest value, for k less than 100.
- Print the sum of the squares of the numbers.
- Print the average of the N numbers.
- Print the percentage of numbers greater than the average.
- Print the N numbers in increasing order.
- Print the N numbers in random order.
if (a > b) { t = a; a = b; b = t; }
if (a > c) { t = a; a = c; c = t; }
if (b > c) { t = b; b = c; c = t; }
public static double binomial(int N, int k, double p)
{
if ((N == 0) || (k < 0)) return 1.0;
return (1.0 - p)*binomial(N-1, k) + p*binomial(N-1, k-1);
}
to compute binomial(100, 50). Develop a better implementation that is based on saving computed values in an array.
public class Matrix |
||
static double |
dot(double[] x, double[] y) |
vector dot product |
static double[][] |
mult(double[][] a, double[][] b) |
matrix-matrix product |
static double[][] |
transpose(double[][] a) |
transpose |
static double[] |
mult(double[][] a, double[] x) |
matrix-vector product |
static double[] |
mult(double[] y, double[][] a) |
vector-matrix product |
Develop a test client that reads values from standard input and tests all the methods.