Questions and Answers of Algorithm Design

Given \(n\) timestamps for when a file is requested from a web server, find the largest interval of time in which no file is requested. Write a program to solve this problem in linearithmic time.
Write a method \(\max ()\) that takes the first Node in a linked list as its argument and returns the value of the maximum item in the list. Assume that all items are positive integers, and return 0
Modify BST to add a method rangeCount() that takes two keys as arguments and returns the number of keys in a BST between the two specified keys. Your method should take time proportional to the
Implement a class that supports the following API, which generalizes both a queue and a stack by supporting removal of the \(i\) th least recently inserted item (see EXERCISE 4.3.40):Data From in
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
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,
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
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
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
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
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
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
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
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
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
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
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.
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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?

Showing 300 - 400 of 648