Introduction To Programming In Java An Interdisciplinary Approach 2nd Edition Robert Sedgewick, Kevin Wayne - Solutions

Counting primes. Write a program PrimeCounter that takes an integer command-line argument n and finds the number of primes less than or equal to n.Use it to print out the number of primes less than or equal to 10 million. Note : If you are not careful, your program may not finish in a reasonable
2D random walk. A two-dimensional random walk simulates the behavior of a particle moving in a grid of points. At each step, the random walker moves north, south, east, or west with probability equal to 1/4, independent of previous moves. Write a program RandomWalker that takes an integer
Exponential function. Assume that x is a positive variable of type double. Write a code fragment that uses the Taylor series expansion to set the value of sum to ex = 1 + x + x2/2! + x3/3! + . . . .
Trigonometric functions. Write two programs, Sin and Cos, that compute the sine and cosine functions using their Taylor series expansions sin x = x x 3/3! + x 5/5! - ... and cos x = 1- x 2/2! + x 4/4! - . . . .
Run experiments to determine the relative costs of Math.exp() and the methods from EXERCISE 1.3.38 for computing e x : the direct method with nested for loops, the improvement with a single for loop, and the latter with the loop-continuation condition (term > 0). Use trial-and-error with a
In 1693 Samuel Pepys asked Isaac Newton which is more likely: getting 1 at least once when rolling a fair die six times or getting 1 at least twice when rolling it 12 times. Write a program that could have provided Newton with a quick answer.
In the game show Let’s Make a Deal, a contestant is presented with three doors. Behind one of them is a valuable prize. After the contestant chooses a door, the host opens one of the other two doors (never revealing the prize, of course). The contestant is then given the opportunity to switch to
Write a program that takes five distinct integers as commandline arguments and prints the median value (the value such that two of the other integers are smaller and two are larger). Extra credit : Solve the problem with a program that compares values fewer than 7 times for any given input.
Sorting three numbers. Suppose that the variables a, b, c, and t are all of the type int. Explain why 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; }
Chaos. Write a program to study the following simple model for population growth, which might be applied to study fish in a pond, bacteria in a test tube, or any of a host of similar situations. We suppose that the population ranges from 0 (extinct) to 1 (maximum population that can be sustained).
In 1769 Leonhard Euler formulated a generalized version of Fermat’s Last Theorem, conjecturing that at least n nth powers are needed to obtain a sum that is itself an nth power, for n > 2. Write a program to disprove Euler’s conjecture (which stood until 1967), using a quintuply nested loop to
Write a program that declares, creates, and initializes an array a[] of length 1000 and accesses a[1000]. Does your program compile? What happens when you run it?
Describe and explain what happens when you try to compile a program with the following statement:int n = 1000;int[] a = new int[n*n*n*n];
Given two vectors of length n that are represented with one-dimensional arrays, write a code fragment that computes the Euclidean distance between them(the square root of the sums of the squares of the differences between corresponding elements).
Write a code fragment that reverses the order of the values in a onedimensional string array. Do not create another array to hold the result. Hint : Use the code in the text for exchanging the values of two elements.
What is wrong with the following code fragment?int[] a;for (int i = 0; i < 10; i++)a[i] = i * i;
Write a code fragment that prints the contents of a two-dimensional boolean array, using * to represent true and a space to represent false. Include row and column indices.
What does the following code fragment print?int[] a = new int[10];for (int i = 0; i < 10; i++)a[i] = 9 - i;for (int i = 0; i < 10; i++)a[i] = a[a[i]];for (int i = 0; i < 10; i++)System.out.println(a[i]);
Which values does the following code put in the array a[]?int n = 10;int[] a = new int[n];a[0] = 1;a[1] = 1;for (int i = 2; i < n; i++)a[i] = a[i-1] + a[i-2];
What does the following code fragment print?int[] a = { 1, 2, 3 };int[] b = { 1, 2, 3 };System.out.println(a == b);
Write a program Deal that takes an integer command-line argument n and prints n poker hands (five cards each) from a shuffled deck, separated by blank lines.
Write a program HowMany that takes a variable number of command-line arguments and prints how many there are.
Write a program DiscreteDistribution that takes a variable number of integer command-line arguments and prints the integer i with probability proportional to the ith command-line argument.
Write code fragments to create a two-dimensional array b[][] that is a copy of an existing two-dimensional array a[][], under each of the following assumptions:a. a[][] is squareb. a[][] is rectangularc. a[][] may be ragged Your solution to b should work for a, and your solution to c should
Write a code fragment to print the transposition (rows and columns exchanged)of a square two-dimensional array. For the example spreadsheet array in the text, you code would print the following:99 98 92 94 99 90 76 92 97 89 85 57 77 32 34 46 59 66 71 29 98 78 76 11 22 54 88 89 24 38
Write a code fragment to transpose a square two-dimensional array in place without creating a second array.
Write a program that takes an integer command-line argument n and 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. Use your solution to EXERCISE
Download the file medium.txt from the booksite and add to it links from page 23 to every other page. Observe the effect on the page ranks, and discuss the result.Page 23
Modify the spreadsheet code fragment in the text to compute a weighted average of the rows, where the weights of each exam score are in a one-dimensional array weights[]. For example, to assign the last of the three exams in our example to be twice the weight of the first two, you would use
Write a code fragment to multiply two rectangular matrices that are not necessarily square. Note: For the dot product to be well defined, the number of columns in the first matrix must be equal to the number of rows in the second matrix.Print an error message if the dimensions do not satisfy this
Write a program that multiplies two square boolean matrices, using the or operation instead of + and the and operation instead of *.
Modify SelfAvoidingWalk (PROGRAM 1.4.4) to calculate and print the average length of the paths as well as the dead-end probability. Keep separate the average lengths of escape paths and dead-end paths.
Modify SelfAvoidingWalk to calculate and print the average area of the smallest axis-aligned rectangle that encloses the dead-end paths.
Dice simulation. The following code computes the exact probability distribution for the sum of two dice:int[] frequencies = new int[13];for (int i = 1; i
Longest plateau. Given an array of integers, find the length and location of the longest contiguous sequence of equal values for which the values of the elements just before and just after this sequence are smaller.
Empirical shuffle check. Run computational experiments to check that our shuffling code works as advertised. Write a program ShuffleTest that takes two integer command-line arguments m and n, does n shuffles of an array of length m that is initialized with a[i] = i before each shuffle, and prints
Bad shuffling. Suppose that you choose a random integer between 0 and n-1 in our shuffling code instead of one between i and n-1. Show that the resulting order is not equally likely to be one of the n! possibilities. Run the test of the previous exercise for this version.
Music shuffling. You set your music player to shuffle mode. It plays each of the n songs before repeating any. Write a program to estimate the likelihood that you will not hear any sequential pair of songs (that is, song 3 does not follow song 2, song 10 does not follow song 9, and so on).
Minima in permutations. Write a program that takes an integer commandline argument n, generates a random permutation, prints the permutation, and prints the number of left-to-right minima in the permutation (the number of times an element is the smallest seen so far). Then write a program that
Inverse permutation. Write a program that reads in a permutation of the integers 0 to n-1 from n command-line arguments and prints the inverse permutation.(If the permutation is in an array a[], its inverse is the array b[] such that a[b[i]] = b[a[i]] = i.) Be sure to check that the input is a
Hadamard matrix. The n-by-n Hadamard matrix H(n) is a boolean matrix with the remarkable property that any two rows differ in exactly n / 2 values. (This property makes it useful for designing error-correcting codes.) H(1) is a 1-by-1 matrix with the single element true, and for n > 1, H(2n) is
Rumors. Alice is throwing a party with n other guests, including Bob. Bob starts a rumor about Alice by telling it to one of the other guests. A person hearing this rumor for the first time will immediately tell it to one other guest, chosen uniformly at random from all the people at the party
Counting primes. Compare PrimeSieve with the method that we used to demonstrate the break statement, at the end of SECTION 1.3. This is a classic example of a space–time tradeoff: PrimeSieve is fast, but requires a boolean array of length n; the other approach uses only two integer variables, but
Minesweeper. Write a program that takes three command-line arguments m, n, and p and produces an m-by-n boolean array where each element is occupied with probability p. In the minesweeper game, occupied cells represent bombs and empty cells represent safe cells. Print out the array using an
Find a duplicate. Given an integer array of length n, with each value between 1 and n, write a code fragment to determine whether there are any duplicate values. You may not use an extra array (but you do not need to preserve the contents of the given array.)
Self-avoiding walk length. Suppose that there is no limit on the size of the grid. Run experiments to estimate the average path length.
Suppose that n random walkers, starting in the center of an n-by-n grid, move one step at a time, choosing to go left, right, up, or down with equal probability at each step. Write a program to help formulate and test ahypothesis about the number of steps taken before all cells are touched.
Random walkers. Suppose that n random walkers, starting in the center of an n-by-n grid, move one step at a time, choosing to go left, right, up, or down with equal probability at each step. Write a program to help formulate and test a hypothesis about the number of steps taken before all cells are
Bridge hands. In the game of bridge, four players are dealt hands of 13 cards each. An important statistic is the distribution of the number of cards in each suit in a hand. Which is the most likely, 5–3-3–2, 4–4-3–2, or 4–3–3–3?
Birthday problem. Suppose that people enter an empty room until a pair of people share a birthday. On average, how many people will have to enter before there is a match? Run experiments to estimate the value of this quantity. Assume birthdays to be uniform random integers between 0 and 364.
Coupon collector. Run experiments to validate the classical mathematical result that the expected number of coupons needed to collect n values is approximately n Hn, where Hn in the nth harmonic number. For example, if you are observing the cards carefully at the blackjack table (and the dealer has
Riffle shuffle. Compose a program to rearrange a deck of n cards using the Gilbert–Shannon–Reeds model of a riffle shuffle. First, generate a random integer r according to a binomial distribution: flip a fair coin n times and let r be the number of heads. Now, divide the deck into two piles:
Write a program that reads in integers (as many as the user enters) from standard input and prints the maximum and minimum values.
Modify your program from the previous exercise to insist that the integers must be positive (by prompting the user to enter positive integers whenever the value entered is not positive).
Write a program that takes an integer command-line argument n, reads n floating-point numbers from standard input, and prints their mean (average value)and sample standard deviation (square root of the sum of the squares of their differences from the average, divided by n-1).
Extend your program from the previous exercise to create a filter that reads n floating-point numbers from standard input, and prints those that are further than 1.5 standard deviations from the mean.
Write a program that reads in a sequence of integers and prints both the integer that appears in a longest consecutive run and the length of that run. For example, if the input is 1 2 2 1 5 1 1 7 7 7 7 1 1, then your program should print Longest run: 4 consecutive 7s.
Write a filter that reads in a sequence of integers and prints the integers, removing repeated values that appear consecutively. For example, if the input is 1 2 2 1 5 1 1 7 7 7 7 1 1 1 1 1 1 1 1 1, your program should print 1 2 1 5 1 7 1.
Write a program that takes an integer command-line argument n, reads in n-1 distinct integers between 1 and n, and determines the missing value.
Write a program that reads in positive floating-point numbers from standard input and prints their geometric and harmonic means. The geometric mean of n positive numbers x1, x2, ..., xn is (x1 - x2 - ... xn)1/n. The harmonic mean is n / (1/x1 + 1/x2 + ... + 1/xn). Hint : For the geometric mean,
Suppose that the file input.txt contains the two strings F and F. What does the following command do (see EXERCISE 1.2.35)? % java Dragon
Write a filter TenPerLine that reads from standard input a sequence of integers between 0 and 99 and prints them back, 10 integers per line, with columns aligned. Then write a program RandomIntSeq that takes two integer commandline arguments m and n and prints n random integers between 0 and m-1.
Write a program that reads in text from standard input and prints the number of words in the text. For the purpose of this exercise, a word is a sequence of non-whitespace characters that is surrounded by whitespace.
Write a program that reads in lines from standard input with each line containing a name and two integers and then uses printf() to print a table with a column of the names, the integers, and the result of dividing the first by the second, accurate to three decimal places. You could use a program
Write a program that prints a table of the monthly payments, remaining principal, and interest paid for a loan, taking three numbers as command-line arguments: the number of years, the principal, and the interest rate (see EXERCISE 1.2.24).
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? For each, the input comes from standard input and consists of n real numbers between 0 and 1.• Print the maximum and
Write a program that takes three double command-line arguments x, y, and z, reads from standard input a sequence of point coordinates (xi, yi, zi), and prints the coordinates of the point closest to (x, y, z). Recall that the square of the distance between (x , y , z) and (xi , yi , zi ) is (x - xi
Given the positions and masses of a sequence of objects, write a program to compute their center-of-mass, or centroid. The centroid is the average position of the n objects, weighted by mass. If the positions and masses are given by (xi , yi, mi ), then the centroid (x, y, m) is given by m = m + m
Write a program that reads in a sequence of real numbers between 1 and1 and prints their average magnitude, average power, and the number of zero crossings. The average magnitude is the average of the absolute values of the data values. The average power is the average of the squares of the data
Write a program that takes an integer command-line argument n and plots an n-by-n checkerboard with red and black squares. Color the lower-left square red.
Write a program that takes as command-line arguments an integer n and a floating-point number p (between 0 and 1), plots n equally spaced points on the circumference of a circle, and then, with probability p for each pair of points, draws a gray line connecting them. 16 0.125 16 0.25 16 0.5 16 1.0
Write code to draw hearts, spades, clubs, and diamonds. To draw a heart, draw a filled diamond, then attach two filled semicircles to the upper left and upper right sides.
Write a program that takes an integer command-line argument n and plots a rose with n petals (if n is odd) or 2n petals (if n is even), by plotting the polar coordinates (r, θ) of the function r = sin(n θ) for θ ranging from 0 to 2π radians. 4 5 8 200 9
Write a program that takes a string command-line argument s and displays it in banner style on the screen, moving from left to right and wrapping back to the beginning of the string as the end is reached. Add a second command-line argument to control the speed.
Modify PlayThatTune to take additional command-line arguments that control the volume (multiply each sample value by the volume) and the tempo(multiply each note’s duration by the tempo).
Write a program that takes the name of a .wav file and a playback rate r as command-line arguments and plays the file at the given rate. First, use StdAudio.read() to read the file into an array a[]. If r = 1, play a[]; otherwise, create a new array b[] of approximate size r times the length of
Write programs that uses StdDraw to create each of the following designs.
Write a program Circles that draws filled circles of random radii at random positions in the unit square, producing images like those below. Your program should take four command-line arguments: the number of circles, the probability that each circle is black, the minimum radius, and the maximum
Visualizing audio. Modify PlayThatTune to send the values played to standard drawing, so that you can watch the sound waves as they are played. You will have to experiment with plotting multiple curves in the drawing canvas to synchronize the sound and the picture.
Statistical polling. When collecting statistical data for certain political polls, it is very important to obtain an unbiased sample of registered voters. Assume that you have a file with n registered voters, one per line. Write a filter that prints a uniformly random sample of size m (see PROGRAM
Terrain analysis. Suppose that a terrain is represented by a two-dimensional grid of elevation values (in meters). A peak is a grid point whose four neighboring cells (left, right, up, and down) have strictly lower elevation values. Write a program Peaks that reads a terrain from standard input and
Histogram. Suppose that the standard input stream is a sequence of double values. Write a program that takes an integer n and two real numbers lo and hi as command-line arguments 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
Spirographs. Write a program that takes three double command-line arguments R, r, and a and draws the resulting spirograph. A spirograph (technically, an epicycloid) is a curve formed by rolling a circle of radius r around a larger fixed circle of radius R. If the pen offset from the center of the
Clock. Write a program that displays an animation of the second, minute, and hour hands of an analog clock. Use the method StdDraw.pause(1000) to update the display roughly once per second.
Oscilloscope. Write a program that simulates the output of an oscilloscope and produces Lissajous patterns. These patterns are named after the French physicist, Jules A. Lissajous, who studied the patterns that arise when two mutually perpendicular periodic disturbances occur simultaneously. Assume
Bouncing ball with tracks. Modify BouncingBall to produce images like the ones shown in the text, which show the track of the ball on a gray background.
Bouncing ball with gravity. Modify BouncingBall to incorporate gravity in the vertical direction. Add calls to StdAudio.play() to add a sound effect when the ball hits a wall and a different sound effect when it hits the floor.
Random tunes. Write a program that uses StdAudio to play random tunes.Experiment with keeping in key, assigning high probabilities to whole steps, repetition, and other rules to produce reasonable melodies.
Tile patterns. Using your solution to EXERCISE 1.5.25, write a program TilePattern that takes an integer command-line argument n and draws an n-by-n pattern, using the tile of your choice. Add a second command-line argument that adds a checkerboard option. Add a third command-line argument for
Modify Transition to take the leap probability as a command-line argument and use your modified version to examine the effect on page ranks of switching to an 80–20 rule or a 95–5 rule.
Modify Transition to ignore the effect of multiple links. That is, if there are multiple links from one page to another, count them as one link. Create a small example that shows how this modification can change the order of page ranks.
Modify Transition to handle pages with no outgoing links, by filling rows corresponding to such pages with the value 1/n, where n is the number of columns.
The code fragment in RandomSurfer that generates the random move fails if the probabilities in the row p[page] do not add up to 1. Explain what happens in that case, and suggest a way to fix the problem.
Determine, to within a factor of 10, the number of iterations required by RandomSurfer to compute page ranks accurate to 4 decimal places and to 5 decimal places for tiny.txt.
Determine the number of iterations required by Markov to compute page ranks accurate to 3 decimal places, to 4 decimal places, and to ten 10 places for tiny.txt.
Download the file medium.txt from the booksite (which reflects the 50-page example depicted in this section) and add to it links from page 23 to every other page. Observe the effect on the page ranks, and discuss the result.
Add to medium.txt (see the previous exercise) links to page 23 from every other page, observe the effect on the page ranks, and discuss the result.Data from in previous exerciseDownload the file medium.txt from the booksite (which reflects the 50-page example depicted in this section) and add to it
Suppose that your page is page 23 in medium.txt. Is there a link that you could add from your page to some other page that would raise the rank of your page? public class IntOps { } public static void main(String[] args) { } int a = Integer.parseInt(args[0]); int b = Integer.parseInt(args [1]); int
Suppose that your page is page 23 in medium.txt. Is there a link that you could add from your page to some other page that would lower the rank of that page? public class IntOps { } public static void main(String[] args) { } int a = Integer.parseInt(args[0]); int b = Integer.parseInt(args [1]); int
Use Transition and RandomSurfer to determine the page ranks for the eight-page graph shown below.

Showing 600 - 700 of 744

Introduction To Programming In Java An Interdisciplinary Approach 2nd Edition Robert Sedgewick, Kevin Wayne - Solutions

Step by Step Answers