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

Create a program PercolationDirected that tests for directed percolation (by leaving off the last recursive call in the recursive flow() method in PROGRAM 2.4.5, as described in the text), then use PercolationPlot to draw a plot of the directed percolation probability as a function of the site
Modify Htree (Program 2.3.4) to animate the drawing of the \(\mathrm{H}\)-tree. Next, rearrange the order of the recursive calls (and the base case), view the resulting animation, and explain each outcome. Program 2.3.4 Recursive graphics public class Htree { } public static void draw(int n, double
Write a data type Point that implements the following API: public class Point Point (double x, double y) double distanceTo (Point q) String toString() Euclidean distance between this point and q string representation
Write a function isWatsonCrickPalindrome() that takes a DNA string as its input and returns true if the string is a Watson-Crick complemented palindrome, and false otherwise. A Watson-Crick complemented palindrome is a DNA string that is equal to the reverse of its Watson-Crick complement.
Describe the effect of the following function. public void swap(Color a, Color b) { } Color temp a = b; b = temp; R a;
Extend your solutions to the previous two exercises to also take a command-line argument \(m\) and to add \(m\) random edges to the graph. Experiment with your programs for graphs with approximately 1,000 vertices to find small-world graphs with relatively few edges. 6-by-6 grid graph
Write a recursive method to print the items in a linked list in reverse order. Do not modify any of the links. Easy: Use quadratic time, constant extra space. Also easy: Use linear time, linear extra space. Not so easy: Develop a divide-and-conquer algorithm that takes linearithmic time and uses
Write a program that takes the name of a grayscale image file as a command-line argument and uses StdDraw to plot a histogram of the frequency of occurrence of each of the 256 grayscale intensities.
Given an integer array, find the longest subsequence that is strictly increasing. Hint : Compute the longest common subsequence of the original array and a sorted version of the array, where any duplicate values are removed.
Longest common strictly increasing subsequence. Given two integer arrays, find the longest increasing subsequence that is common to both arrays.
The binomial coefficient C(n, k) is the number of ways of choosing a subset of k elements from a set of n elements. Pascal’s identity expresses the binomial coefficient C(n, k) in terms of smaller binomial coefficients: C(n, k) = C(n1, k1) + C(n1, k), with C(n, 0) = 1 for each integer n. Write
Your job is to paint a row of n houses red, green, or blue so as to minimize total cost, where cost(i, color) = cost to pain house i the specified color. You may not paint two adjacent houses the same color. Write a program to determine an optimal solution to the problem. Hint : Use bottom-up
Consider the following data-type implementation for axis-aligned rectangles, which represents each rectangle with the coordinates of its center point and its width and height:Write an API for this class, and fill in the code for perimeter(), intersects (), and contains(). Consider two rectangles to
Represent a point in time by using an int to store the number of seconds since January 1,1970 . When will programs that use this representation face a time bomb? How should you proceed when that happens?
Write a static method reverse() that takes a string as an argument and returns a string that contains the same sequence of characters as the argument string but in reverse order.
Develop an object-oriented version of BouncingBa11 (Program 3.1.9). Include a constructor that starts each ball moving in a random direction at a random velocity (within reasonable limits) and a test client that takes an integer commandline argument \(n\) and simulates the motion of \(n\) bouncing
Create a data type Location for dealing with locations on Earth using spherical coordinates (latitude/longitude). Include methods to generate a random location on the surface of the Earth, parse a location " 25.344 N, 63.5532 W", and compute the great circle distance between two locations.
Write a test client for Rectangle that takes three command-line arguments \(\mathrm{n}\), min, and max; generates \(\mathrm{n}\) random rectangles whose width and height are uniformly distributed between min and max in the unit square; draws them on standard drawing; and prints their average area
Write a program that takes from the command line three integers between 0 and 255 that represent red, green, and blue values of a color and then creates and shows a 256-by-256 Picture in which each pixel has that color.
Add a main() method to Program 3.4.1 that unit-tests the Body data type. Program 3.4.1 Gravitational body public class Body { py private Vector r; private Vector v; private final double mass; public Body (Vector r0, Vector v0, double m0) { r = r0; v = v0; mass = m0; } public void move (Vector
Give an implementation of minus () for Vector solely in terms of the other Vector methods, such as direction() and magnitude().
Develop an implementation of your Rectang 7e API from EXERCISE 3.2.1 that represents rectangles with the \(x\) - and \(y\)-coordinates of their lower-left and upperright corners. Do not change the API.Data From in Exercise 3.2.1Consider the following data-type implementation for axis-aligned
Write a program LongestPalindromic-Subsequence that takes a string as a command-line argument and determines the longest subsequence of the string that is a palindrome (the same when read forward or backward).
Longest common subsequence of three strings. Given three strings, write a program that computes the longest common subsequence of the three strings.
Write a program Tree that takes a command-line argument n and produces the following recursive patterns for n equal to 1, 2, 3, 4, and 8. So b b b h l 4 3 2 1
A strange function. Consider McCarthy’s 91 function:public static int mcCarthy(int n){if (n > 100) return n - 10;return mcCarthy(mcCarthy(n+11));}Determine the value of mcCarthy(50) without using a computer. Give the number of recursive calls used by mcCarthy() to compute this result. Prove that
Write a recursive program to draw plasma clouds, using the method suggested in the text.
Mandelbrot asked the famous question How long is the coast of Britain? Modify Brownian to get a program BrownianIsland that plots Brownian islands, whose coastlines resemble that of Great Britain. The modifications are simple: first, change curve() to add a random Gaussian to the x-coordinate as
Consider the following recursive function, which is related to a famous unsolved problem in number theory, known as the Collatz problem, or the 3n+1 problem:public static void collatz(int n){StdOut.print(n + " ");if (n == 1) return;if (n % 2 == 0) collatz(n / 2);else collatz(3*n + 1);}For example,
Estimate the number of recursive calls that would be used by the codeto compute binomial(100, 50). Develop a better implementation that is based on dynamic programming. public static double binomial(int n, int k) { } if ((n == 0) && (k == 0)) if ((n < 0) || (k < 0)) return (binomial(n-1, k) return
Use StdDraw to animate a solution to the towers of Hanoi problem, moving the discs at a rate of approximately 1 per second. order 2
Add to StdRandom a static method maxwellBoltzmann() that returns a random value drawn from a Maxwell-Boltzmann distribution with parameter \(\sigma\). To produce such a value, return the square root of the sum of the squares of three random numbers drawn from the Gaussian distribution with mean 0
What happens in a universe in which there is no gravitational force? This situation would correspond to forceTo () in Body always returning the zero vector.
Implement a main() method for Vector that unit-tests its methods.
What is wrong with the following code? public class Charge { } private double rx, ry; private double q; public Charge (double x0, double y0, double q0) { } double rx = x0; double ry y0; double q = q0; // position // charge =
Write a program that takes the name of an image file as a command-line argument and flips the image horizontally.
Create a data type Universe3D to model three-dimensional universes. Develop a data file to simulate the motion of the planets in our solar system around the sun.
Create a data type Location that represents a location on Earth using latitudes and longitudes. Include a method distanceTo() that computes distances using the great-circle distance.
Write a program that takes the name of an image file as a command-line argument, and creates and shows three Picture objects, one that contains only the red components, one for green, and one for blue.
Implement a class RandomBody that initializes its instance variables with (carefully chosen) random values instead of using a constructor and a client RandomUniverse that takes a single command-line argument \(n\) and simulates motion in a random universe with \(n\) bodies.
Write a program that takes the name of an image file as a command-line argument and prints the pixel coordinates of the lower-left corner and the upperright corner of the smallest bounding box (rectangle parallel to the \(x\) - and \(y\)-axes) that contains all of the non-white pixels.
Design a new universe with interesting properties and simulate its motion with Universe. This exercise is truly an opportunity to be creative!
Implement a data type Vector2D for two-dimensional vectors that has the same API as Vector, except that the constructor takes two double values as arguments. Use two doub7e values (instead of an array) for instance variables.
Write a data type Interval that implements the following API:An interval is defined to be the set of all points on the line greater than or equal to min and less than or equal to max. In particular, an interval with max less than min is empty. Write a client that is a filter that takes a
Write a program that takes as command-line arguments the name of an image file and the pixel coordinates of a rectangle within the image; reads from standard input a list of Color values (represented as triples of int values); and serves as a filter, printing those color values for which all pixels
Develop an object-oriented version of Percolati on (Program 2.4.5). Think carefully about the design before you begin, and be prepared to defend your design decisions. Program 2.4.5 Percolation detection. public static boolean[] [] flow (boolean[] [] isOpen) { // Fill every site reachable from the
Write a static method isValidDNA() that takes a string as its argument and returns true if and only if it is composed entirely of the characters A, T, C, and G.
Write a client UniverseTrace that produces traces of the \(n\)-body simulation system like the static images. 100 steps 150 steps 1.000 steps 10,000 steps 150 steps 880 steps 1,600 steps 3,100 steps 100 steps 500 steps 1,000 steps 3,000 steps Simulating 2-body (left column), 3-body (middle
Prove that the dot product of two two-dimensional unit-vectors is the cosine of the angle between them.
Develop an implementation of your Rectangle API from EXERCISE 3.2.1 that takes advantage of the Interval data type to simplify and clarify the code.Data From in Exercise 3.2.1Consider the following data-type implementation for axis-aligned rectangles, which represents each rectangle with the
Write a function complementWatsonCrick() that takes a DNA string as its argument and returns its Watson-Crick complement: replace A with T, C with G, and vice versa.
Implement a data type Vector3D for three-dimensional vectors that has the same API as Vector, except that the constructor takes three doub7e values as arguments. Also, add a cross-product method: the cross-product of two vectors is another vector, defined by the equation \[\mathbf{a} \times
Pick an interesting set of documents from the booksite (or use a collection of your own) and run CompareDocuments with various values for the command-line arguments \(\mathrm{k}\) and \(\mathrm{d}\), to learn about their effect on the computation.
Write a recursive Turtle client that produces these recursive patterns. 1 2 3 4
A space-filling curve is a continuous curve in the unit square that passes through every point. Write a recursive Turt le client that produces these recursive patterns, which approach a space-filling curve that was defined by the mathematician David Hilbert at the end of the 19th century.Design a
A string s is a circular shift of a string t if it matches when the characters of one string are circularly shifted by some number of positions. For example, ACTGACG is a circular shift of TGACGAC, and vice versa. Detecting this condition is important in the study of genomic sequences. Write a
Write a Complex client that takes three floating-point numbers \(a, b\), and \(c\) as command-line arguments and prints the two (complex) roots of \(a x^{2}+b x+c\).
Write a static method that takes a domain name as its argument and returns the reverse domain name (reverse the order of the strings between periods).For example, the reverse domain name of cs.princeton.edu is edu.princeton.cs. This computation is useful for web log analysis.
Write a Stopwatch client that compares the cost of using Comp1ex to the cost of writing code that directly manipulates two doub7e values, for the task of doing the calculations in Mande1brot. Specifically, create a version of Mande1brot that just does the calculations (remove the code that refers
Write a Complex client Roots0fUnity that takes two double values \(a\) and \(b\) and an integer \(n\) from the command line and prints the \(n\)th roots of \(a+b i\). Skip this exercise if you are not familiar with the operation of taking roots of complex numbers.
Develop Appointment and Calendar APIs that can be used to keep track of appointments (by day) in a calendar year. Your goal is to enable clients to schedule appointments that do not conflict and to report current appointments to clients.
In 1843, Sir William Hamilton discovered an extension to complex numbers called quaternions. A quaternion is a 4-tuple \(a=\left(a_{0}, a_{1}, a_{2}, a_{3}ight)\) with the following operations:Create a data type Quaternion for quaternions and a test client that exercises all of your code.
Find a website that publishes the current temperature in your area, and write a screen-scraper program Weather so that typing java Weather followed by your ZIP code will give you a weather forecast.
Suppose that a[] and b[] are both integer arrays consisting of millions of integers. What does the following code do, and how long does it take?int[] temp = a; a = b; b = temp;
The polynomial \(f(z)=z^{4}-1\) has four roots: at \(1,-1, i\), and \(-i\). We can find the roots using Newton's method in the complex plane: \(z_{k+1}=z_{k}-f\left(z_{k}ight) / f^{\prime}\left(z_{k}ight)\). Here, \(f(z)=z^{4}-1\) and \(f^{\prime}(z)=4 z^{3}\). The method converges to one of the
Write a program that displays the color study shown at right, which gives Albers squares corresponding to each of the 256 levels of blue (blue-to-white in row major order) and gray (black-to-white in column-major order) that were used to print this book. A color study
Write a StockAccount client that builds an array of StockAccount objects, computes the total value of each account, and prints a report for the accounts with the largest and smallest values. Assume that the information in the accounts is kept in a single file that contains the information for the
Safe password verification. Write a static method that takes a string as an argument and returns true if it meets the following conditions, false otherwise:• At least eight characters long• Contains at least one digit (0–9)• Contains at least one uppercase letter• Contains at least one
The file DJIA.csv on the booksite contains all closing stock prices in the history of the Dow Jones Industrial Average, in the comma-separatedvalue format. Create a data type DowJonesEntry that can hold one entry in the table, with values for date, opening price, daily high, daily low, closing
Write a data type for use in running experiments where the control variable is an integer in the range \([0, n)\) and the dependent variable is a double value. (For example, studying the running time of a program that takes an integer argument would involve such experiments.) Implement the
Write a filter KamasutraCipher that takes two strings as command-line argument (the key strings), then reads strings (separated by whitespace) from standard input, substitutes for each letter as specified by the key strings, and prints the result to standard output. This operation is the basis for
Write a recursive program that surfs the web, starting at a page given as the first command-line argument, looking for pages that are similar to the page given as the second command-line argument, as follows: to process a name, open an input stream, do a readA11(), sketch it, and print the name if
Write a program that uses StdAudio and Picture to create an interesting two-dimensional color visualization of a sound file while it is playing. Be creative!
Create a data type Chemi ca1Element for entries in the Periodic Table of Elements. Include data-type values for element, atomic number, symbol, and atomic weight, and accessor methods for each of these values. Then create a data type PeriodicTable that reads values from a file to create an array of
Develop profiling strategies for sound and pictures, and use them to discover interesting similarities among songs in the music library and photos in the photo album on your computer.
Write a library of static methods RawPicture with read() and write() methods for saving and reading pictures from a file. The write() method takes a Picture and the name of a file as arguments and writes the picture to the specified file, using the following format: if the picture is w-byh, write
Prove by induction that the number of (unordered) pairs of integers between 0 and \(n-1\) is \(n(n-1) / 2\), and then prove by induction that the number of (unordered) triples of integers between 0 and \(n-1\) is \(n(n-1)(n-2) / 6\).
Create a copy constructor for Graph that takes as its argument a graph G, then creates and initializes a new, independent copy of the graph. Any future changes to \(G\) should not affect the newly created graph.
Describe why it is desirable to use immutable keys with binary search.
Write a static method that reads floating-point numbers one at a time from standard input and returns an array containing them, in the same order they appear on standard input. Hint: Use either a stack or a queue.
Develop an implementation BinarySearchST of the symbol-table API that maintains parallel arrays of keys and values, keeping them in key-sorted order. Use binary search for get, and move larger key-value pairs to the right one position for put (use a resizing array to keep the array length
Give the output printed by java ArrayStackOfStrings 5 for this input:it was - the best - of times - - - it was - the - -
Modify Lookup to make a program LookupMu1tiple that handles multiple values having the same key by storing all such values in a queue, as in Index, and then printing them all on a get request, as follows: % java LookupMultiple amino.csv 3 0 Leucine TTA TTG CTT CTC CTA CTG
How much time does it take to call functions such as Math. \(\sin ()\), Math. \(\log ()\), and Math.sqrt()?
Modify ThreeSum to take an integer command-line argument target and find a triple of numbers on standard input whose sum is closest to target.
Add to Graph a method degree() that takes a string argument and returns the degree of the specified vertex. Use this method to find the performer in the file movies. txt who has appeared in the most movies.
Suppose that a client performs an intermixed sequence of push and pop operations on a pushdown stack. The push operations insert the integers 0 through 9 in order onto the stack; the pop operations print the return values. Which of the following sequence(s) could not occur? a. 4 3 2 1 0 9 8 7 6 5
Modify Index to make a program IndexByKeyword that takes a file name from the command line and makes an index from standard input using only the keywords in that file. Note: Using the same file for indexing and keywords should give the same result as Index.
Write a program FourSum that reads Tong integers from standard input, and counts the number of 4-tuples that sum to zero. Use a quadruple nested loop. What is the order of growth of the running time of your program? Estimate the largest input size that your program can handle in an hour. Then, run
Add to Graph a method hasVertex() that takes a string argument and returns true if it names a vertex in the graph, and false otherwise.
Add to Graph a method hasEdge() that takes two string arguments and returns true if they specify an edge in the graph, and false otherwise.
Describe what happens if you apply binary search to an unordered array. Why shouldn't you check whether the array is sorted before each call to binary search? Could you check that the elements binary search examines are in ascending order?
Write a filter Reverse that reads strings one at a time from standard input and prints them to standard output in reverse order. Use either a stack or a queue.
Modify Index to make a program IndexLines that considers only consecutive sequences of letters as keys (no punctuation or numbers) and uses line number instead of word position as the value. This functionality is useful for programs, as follows: % java IndexLines 6 0
Why does allocating an array of length \(n\) take time proportional to \(n\) ?
Show by approximating with integrals that the number of distinct triples of integers between 0 and \(n\) is about \(n^{3} / 6\).
Write a version of Graph that supports explicit vertex creation and allows self-loops, parallel edges, and isolated vertices. Hint: Use a Queue for the adjacency lists instead of a SET.
Give traces of insertion sort and mergesort in the style of the traces in the text, for the input it was the best of times it was.
Add to Graph a method subgraph() that takes a SET as its argument and returns the induced subgraph (the graph comprising the specified vertices together with all edges from the original graph that connect any two of them).
What is the value of the variable count, as a function of \(n\), after running the following code fragment? long count = 0; for (int i = 0; i

Showing 100 - 200 of 744

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

Step by Step Answers