Algorithms: The Basic Programming Model

From the book

Algorithms: Part I, 4th Edition

Learn More Buy

From the book

From the book 

Algorithms: Part I, 4th Edition

Learn More Buy

CREATIVE PROBLEMS

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

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; }

27. Binomial distribution. Estimate the number of recursive calls that would be used by the code

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.

28. Remove duplicates. Modify the test client in BinarySearch to remove any duplicate keys in the whitelist after the sort.
29. 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.
30. 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.
31. 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.
32. 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.
33. Matrix library. Write a library Matrix that implements the following API:

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.

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