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

Modify LoadBalance to print the average queue length and the maximum queue length instead of plotting the histogram, and use it to run simulations for 1 million items on 100,000 queues. Print the average value of the maximum queue length for 100 trials each with sample sizes \(1,2,3\), and 4 . Do
Design a linear-time algorithm that finds a contiguous subarray of length at most \(m\) in an array of \(n\) long integers that has the highest sum among all such subarrays. Implement your algorithm, and confirm that the order of growth of its running time is linear.
Write a filter that reads a sequence of domain names from standard input and prints the reverse domain names in sorted order. For example, the reverse domain name of cs.princeton. edu is edu.princeton. cs. This computation is useful for web log analysis. To do so, create a data type Domain that
A folder is a list of files and folders. Write a program that takes the name of a folder as a command-line argument and prints all of the files contained in that folder, with the contents of each folder recursively listed (indented) under that folder's name. Use a queue, and see java. io. File.
Rank query. Add to BST a method rank() that takes a key as an argument and returns the number of keys in the BST that are strictly smaller than key. Maintain subtree sizes in each node (see EXERCISE 4.4.29). The running time should be proportional to the height of the tree.Data from in Exercise
Craps. The following are the rules for a pass bet in the game of craps. Roll two six-sided dice, and let \(x\) be their sum.- If \(x\) is 7 or 11 , you win.- If \(x\) is 2,3 , or 12 , you lose.Otherwise, repeatedly roll the two dice until their sum is either \(x\) or 7 .- If their sum is \(x\), you
Develop a library based on the functions that we have considered in this book for computing properties of integers. Include functions for determining whether a given integer is prime; determining whether two integers are relatively prime; computing all the factors of a given integer; computing the
Develop a StdRandom client (with appropriate static methods of its own) to study the following problem: Suppose that in a population of 100 million voters, \(51 \%\) vote for candidate \(A\) and \(49 \%\) vote for candidate B. However, the voting machines are prone to make mistakes, and \(5 \%\) of
The width-to-height ratio of paper in the ISO format is the square root of 2 to 1 . Format A0 has an area of 1 square meter. Format A1 is A0 cut with a vertical line into two equal halves, A2 is A1 cut with a horizontal line into two halves, and so on. Write a program that takes an integer
Write a program Permutations that takes an integer command-line argument \(n\) and prints all \(n\) ! permutations of the \(n\) letters starting at a (assume that \(n\) is no greater than 26). A permutation of \(n\) elements is one of the \(n\) ! possible orderings of the elements. As an example,
Write a program Combinations that takes an integer command-line argument \(n\) and prints all \(2^{n}\) combinations of any size. A combination is a subset of the \(n\) elements, independent of order. As an example, when \(n=3\), you should get the following output:a ab abc ac b bc c Note that your
The Hamming distance between two bit strings of length \(n\) is equal to the number of bits in which the two strings differ. Write a program that reads in an integer \(k\) and a bit string \(s\) from the command line, and prints all bit strings that have Hamming distance at most \(\mathrm{k}\) from
Write a program to produce each of the following recursive patterns. The ratio of the sizes of the squares is 2.2:1. To draw a shaded square, draw a filled gray square, then an unfilled black square. 8888 88888
You have a stack of \(n\) pancakes of varying sizes on a griddle. Your goal is to rearrange the stack in order so that the largest pancake is on the bottom and the smallest one is on top. You are only permitted to flip the top \(k\) pancakes, thereby reversing their order. Devise a recursive scheme
Consider the following variant of the towers of Hanoi problem. There are 2n discs of increasing size stored on three poles. Initially all of the discs with odd size (1, 3, ..., 2n-1) are piled on the left pole from top to bottom in increasing order of size; all of the discs with even size (2, 4,
Write a modular program for studying percolation under the assumption that the edges of the grid provide connectivity. That is, an edge can be either empty or full, and a system percolates if there is a path consisting of full edges that goes from top to bottom. This problem has been solved
Bond percolation on a triangular grid. Write a modular program for studying bond percolation on a triangular grid, where the system is composed of 2n 2 equilateral triangles packed together in an n-by-n grid of rhombus shapes. Each interior point has six bonds; each point on the edge has four; and
Implement a class GameOfLife that simulates Conway’s Game of Life. Consider a boolean matrix corresponding to a system of cells that we refer to as being either live or dead. The game consists of checking and perhaps updating the value of each cell, depending on the values of its neighbors (the
Write a client of Percolation like PercolationVisualizer that does a series of experiments for a value of n taken from the command line where the site vacancy probability p increases from 0 to 1 by a given increment (also taken from the command line).
Write a library of static methods that implements the hyperbolic functions based on the definitions \(\sinh (x)=\left(e^{x}-e^{-x}ight) / 2\) and \(\cosh (x)=\left(e^{x}+e^{-x}ight) / 2\), with \(\tanh (x), \operatorname{coth}(x), \operatorname{sech}(x)\), and \(\operatorname{csch}(x)\) defined in
Add a method \(\exp ()\) to StdRandom that takes an argument \(\lambda\) and returns a random number drawn from the exponential distribution with rate \(\lambda\). If \(x\) is a random number uniformly distributed between 0 and 1 , then \(-\ln x / \lambda\) is a random number from the exponential
Develop a full implementation of StdArrayIO (implement all 12 methods indicated in the API).
Sicherman dice. Suppose that you have two six-sided dice, one with faces labeled \(1,3,4,5,6\), and 8 and the other with faces labeled 1,2,2,3,3, and 4. Compare the probabilities of occurrence of each of the values of the sum of the dice with those for a standard pair of dice. Use StdRandom and
What happens if you call factoria1() with a negative value of \(n\) ? With a large value of, say, 35 ?
Write a recursive function that takes an integer \(n\) as its argument and returns \(\ln (n !)\).
Give the sequence of integers printed by a call to ex233(6): public static void ex233 (int n) { } if (n
Give the value of ex234(6): public static String ex234(int n) { } if (n
Criticize the following recursive function:pub7ic static String ex235(int \(n\) )\{String \(s=\operatorname{ex235(n-3)}+n+\operatorname{ex235(n-2)}+n\);if \((n
Given four positive integers a, b, c, and d, explain what value is computed by gcd(gcd(a, b), gcd(c, d)).
Explain in terms of integers and divisors the effect of the following Euclidlikefunction:public static boolean gcdlike(int p, int q){if (q == 0) return (p == 1);return gcdlike(q, p % q);}
Consider the following recursive function:public static int mystery(int a, int b){if (b == 0) return 0;if (b % 2 == 0) return mystery(a+a, b/2);return mystery(a+a, b/2) + a;}What are the values of mystery(2, 25) and mystery(3, 11)? Given positiveintegers a and b, describe what value mystery(a, b)
Solve the following recurrence relations, all with \(T(1)=1\). Assume \(n\) is a power of 2 .- \(T(n)=T(n / 2)+1\)- \(T(n)=2 T(n / 2)+1\)- \(T(n)=2 T(n / 2)+n\)- \(T(n)=4 T(n / 2)+3\)
Prove by induction that the minimum possible number of moves needed to solve the towers of Hanoi satisfies the same recurrence as the number of moves used by our recursive solution.
Prove by induction that the recursive program given in the text makes exactly \(F_{n}\) recursive calls to fibonacci (1) when computing fibonacci( \(n\) ).
Prove that the second argument to \(\operatorname{gcd}()\) decreases by at least a factor of 2 for every second recursive call, and then prove that \(\operatorname{gcd}(p, q)\) uses at most \(2 \log _{2} n+1\) recursive calls where \(n\) is the larger of \(p\) and \(q\).
Implement a print() method for Percolation that prints 1 for blocked sites, 0 for open sites, and * for full sites.
Give the recursive calls for flow() in PROGRAM 2.4.5 given the following input: 33 10 1 000 110
Describe the order in which the sites are marked when Percolation is used on a system with no blocked sites. Which is the last site marked? What is the depth of the recursion?
Experiment with using PercolationPlot to plot various mathematical functions (by replacing the call PercolationProbability.estimate() with a different expression that evaluates a mathematical function). Try the function f(x) = sin x + cos 10x to see how the plot adapts to an oscillating curve, and
Modify Percolation to animate the flow computation, showing the sites filling one by one. Check your answer to the previous exercise.
Modify Percolation to compute that maximum depth of the recursion used in the flow calculation. Plot the expected value of that quantity as a function of the site vacancy probability p. How does your answer change if the order of the recursive calls is reversed?
Write a client of Percolation and PercolationDirected that takes a site vacancy probability p from the command line and prints an estimate of the probability that a system percolates but does not percolate down. Use enough experiments to get an estimate that is accurate to three decimal places.
Vertical percolation. Show that a system with site vacancy probability p vertically percolates with probability 1 - (1 - p n)n, and use PercolationProbability to validate your analysis for various values of n.
Rectangular percolation systems. Modify the code in this section to allow you to study percolation in rectangular systems. Compare the percolation probability plots of systems whose ratio of width to height is 2 to 1 with those whose ratio is 1 to 2.
Adaptive plotting. Modify PercolationPlot to take its control parameters(gap tolerance, error tolerance, and number of trials) as command-line arguments.Experiment with various values of the parameters to learn their effect on the quality of the curve and the cost of computing it. Briefly describe
Nonrecursive directed percolation. Write a nonrecursive program that tests for directed percolation by moving from top to bottom as in our vertical percolation code. Base your solution on the following computation: if any site in a contiguous subrow of open sites in the current row is connected to
Write a StdRandom and StdStats client (with appropriate static methods of its own) to estimate the probabilities of getting one pair, two pair, three of a kind, a full house, and a flush in a five-card poker hand via simulation. Divide your program into appropriate static methods and defend your
Develop your own plot methods that improve upon those in StdStats. Be creative! Try to make a plotting library that you think will be useful for some application in the future.
Write a test client for both StdStats and StdRandom that checks that the methods in both libraries operate as expected. Take a command-line argument \(n\), generate \(n\) random numbers using each of the methods in StdRandom, and print their statistics. Extra credit: Defend the results that you get
Add to StdRandom a method shuffle() that takes an array of double values as argument and rearranges them in random order. Implement a test client that checks that each permutation of the array is produced about the same number of times. Add overloaded methods that take arrays of integers and
Develop a client that does stress testing for StdRandom. Pay particular attention to discrete(). For example, do the probabilities sum to 1 ?
Write a static method that takes double values ymin and ymax (with ymin strictly less than ymax), and a double array a [] as arguments and uses the StdStats library to linearly scale the values in \(a[]\) so that they are all between ymin and ymax.
Write a Gaussian and StdStats client that explores the effects of changing the mean and standard deviation for the Gaussian probability density function. Create one plot with the Gaussian distributions having a fixed mean and various standard deviations and another with Gaussian distributions
Write a library Matrix that implements the following API:Mathematicians and scientists use mature libraries or special-purpose matrix-processing languages for such tasks. See the booksite for details on using such libraries. public class Matrix double dot (double [] a, double[] b) double [] []
Rewrite RandomSurfer (Program 1.6.2) using the StdArrayIO and StdRandom libraries. Partial solution. double [] [] p= StdArrayI0. readDouble2D(); int page = 0; // Start at page 0. int[] freq = new int[n]; for (int t = 0; t < trials; t++) { } legend page - StdRandom.discrete (p[page]); freq[page]++;
Develop a client that does stress testing for StdStats. Work with a classmate, with one person writing code and the other testing it.
What happens if I leave out the keyword static when defining a static method?
What happens if I write code after a return statement?
What happens if I do not include a return statement?
Why do I need to use the return type void? Why not just omit the return type?
Can I return from a void function by using return? If so, which return value should I use?
This issue with side effects and arrays passed as arguments is confusing. Is it really all that important?
So why not just eliminate the possibility of side effects by making all arguments pass by value, including arrays?
In which order does Java evaluate method calls?
I tried to use StdRandom, but got the error message Exception in thread"main" java.lang.NoClassDefFoundError: StdRandom. What’s wrong?
Is there a keyword that identifies a class as a library?
How do I develop a new version of a library that I have been using for a while?
How do I know that an implementation behaves properly? Why not automatically check that it satisfies the API?
Which Java methods are available for me to use?
When I ran Use Argument, I got a strange error message. What’s the problem?
How does Java store strings internally?
How can I compare two strings like words in a book index or dictionary?
How can I specify a string literal that is too long to fit on a single line?
How does Java store integers internally?
What’s the binary number system?
It seems wrong that Java should just let ints overflow and give bad values.Shouldn’t Java automatically check for overflow?
What is the value of Math.abs(-2147483648)?
What do the expressions 1 / 0 and 1 % 0 evaluate to in Java?
What is the result of division and remainder for negative integers?
Why is the value of 10 ^ 6 not 1000000 but 12?
Why is the type for real numbers named double?
How does Java store floating-point numbers internally?
Fifteen digits for floating-point numbers certainly seems enough to me. Do I really need to worry much about precision?
How can I initialize a double variable to NaN or infinity?
Are there functions in Java’s Math library for other trigonometric functions, such as cosecant, secant, and cotangent?
It is annoying to see all those digits when printing a double. Can we arrange System.out.println() to print just two or three digits after the decimal point?
Why the distinction between primitive and reference types?
What happens if I forget to use new when creating an object?
Why can we print an object x with the function call StdOut.println(x), as opposed to StdOut.println(x.toString())?
What is the difference between =, ==, and equals()?
How can I arrange to pass an array as an argument to a function in such a way that the function cannot change the values of the elements in the array?
What happens if I forget to use new when creating an array of objects?
Where can I find more details on how Java implements references and garbage collection?
Why red, green, and blue instead of red, yellow, and blue?
What exactly is the purpose of an import statement?
I noticed that the argument to the equals() method in String and Color is of type Object. Shouldn’t the argument be of type String and Color, respectively?
Why does the String method call s.substring(i, j) return the substring of s starting at index i and ending at j-1 (and not j)?
Why is the image-processing data type named Picture instead of Image?
Do instance variables have default initial values that we can depend upon?
What is null?

Showing 400 - 500 of 744

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

Step by Step Answers