Questions and Answers of Algorithm Design

Write a static method max3() that takes three int arguments and returns the value of the largest one. Add an overloaded function that does the same thing with three double values.
Write a recursive program Ruler to plot the subdivisions of a ruler using StdDraw, as in Program 1.2.1. Program 1.2.1 String concatenation public class Ruler { public static void main(String[] args)
Write a program that takes a command-line argument n and creates an n-by-n boolean matrix with the element in row i and column j set to true if i and j are relatively prime, then shows the matrix on
Modify PercolationProbability to produce output like that produced by Bernoulli (PROGRAM 2.2.6). Extra credit : Use your program to validate the hypothesis that the data obeys a Gaussian
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
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
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
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
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 =
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
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
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
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
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,
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
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
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
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
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
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}\),
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
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,
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
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.
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
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
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
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) /
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
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
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•
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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\).

Showing 1 - 100 of 648