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

Write a stack client Parentheses that reads a string of parentheses, square brackets, and curly braces from standard input and uses a stack to determine whether they are properly balanced. For example, your program should print true for \([()]\{\}\{[()()]()\}\) and false for \([(])\).
Develop an implementation Sequentia7SearchST of the symbol-table API that maintains a linked list of nodes containing keys and values, keeping them in arbitrary order. Test your implementation with Index, and validate the hypothesis that using such an implementation for Index takes time
What does the following code fragment print when \(\mathrm{n}\) is 50 ? Give a high-level description of what the code fragment does when presented with a positive integer n. Stack stack while (n> 0) { = stack.push(n % 2); n /= 2; new Stack (); } while (!stack.isEmpty()) Stdout.println();
Compute \(x\).hashCode() \% 5 for the single-character strings E A S Y Q U E S T I O N In the style of the drawing in the text, draw the hash table created when the \(i\) th key in this sequence is associated with the value \(i\), for \(i\) from 0 to 11 .
So can I use the fact that the worst-case running time of an algorithm is \(O\left(n^{3}ight)\) or \(O\left(n^{2}ight)\) to predict performance?
What does it mean when someone says that the running time is \(O\left(n^{2}ight)\) ?
Show that a \(\log -\log\) plot of the function \(c n^{b}\) has slope \(b\) and \(x\)-intercept \(\log c\). What are the slope and \(x\)-intercept for \(4 n^{3}(\log n)^{2}\) ?
Add to Graph a method remove() that takes two string arguments and deletes the specified edge from the graph, if present.
Add code to Merge to produce a trace like the following: % java Merge < tiny.txt was had him and you his the but had was and him and had him was his you but the but his the you and but had him his the was you
Implement the method contains() for HashST.
Use tilde notation to simplify each of the following formulas, and give the order of growth of each:a. \(n(n-1)(n-2)(n-3) / 24\)b. \((n-2)(\lg n-2)(\lg n+2)\)c. \(n(n+1)-n^{2}\)d. \(n(n+1) / 2+n \lg n\)e. \(\ln ((n-1)(n-2)(n-3))^{2}\)
Write a version of Graph that supports generic comparable vertex types (easy). Then, write a version of PathFinder that uses your implementation to support finding shortest paths using generic comparable vertex types (more difficult).
Determine whether the following code fragment takes linear time, quadratic time, or cubic time (as a function of \(n\) ). for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) j) C[i][j] 1.0; if (i else c[i][j] = 0.0; =
Give the contents and length of the array for ResizingArrayStackOfStrings with this input:\[\text { it was - the best - of times - - - it was - the - - }\]
Implement the method size() for HashST.
Explain why we use 1o + (hi - 10) / 2 to compute the index midway between 10 and hi instead of using \((10+h i) / 2\).
Determine the order of growth of the running time of this statement in ThreeSum as a function of the number of integers \(n\) on standard input:int[] a = StdIn. readA11Ints();Answer: Linear. The bottlenecks are the implicit array initialization and the implicit input loop. Depending on your system,
The Shannon entropy measures the information content of an input string and plays a cornerstone role in information theory and data compression. Given a string of \(n\) characters, let \(f_{c}\) be the frequency of occurrence of character \(c\). The quantity \(p_{c}=f_{c} / n\) is an estimate of
Create a file of 256 integer triples that represent interesting Color values, and then use those colors instead of grayscale values to plot each pixel in Mande1brot. Read the values to create an array of 256 Co1or values, then index into that array with the return value of mand (). By experimenting
Write a program that takes the name of an image file and two integers \(m\) and \(n\) as command-line arguments and creates an \(m\)-by- \(n\) tiling of the image.
Write a program that takes two command-line arguments (the name of an image file and a real number \(\theta\) ) and rotates the image \(\theta\) degrees counterclockwise. To rotate, copy the color of each pixel \(\left(s_{i}ight.\), \(\left.s_{j}ight)\) in the source image to a target pixel
Write a program that takes the names of several image files as command-line arguments and displays them in a slide show (one every two seconds), using a fade effect to black and a fade from black between images. % java Zoom boy.jpg 1.5.5 2014 Janine Dietz
The example images in the text for Fade do not quite line up in the vertical direction (the mandrill's mouth is much lower than Darwin's). Modify Fade to add a transformation in the vertical dimension that makes a smoother transition. % java Zoom boy.jpg .5.5.5
Write a program Zoom that takes the name of an image file and three numbers \(s, x\), and \(y\) as command-line arguments, and shows an output image that zooms in on a portion of the input image. The numbers are all between 0 and 1 , with \(s\) to be interpreted as a scale factor and \((x, y)\) as
Modify Lookup to make a program LookupAndPut that allows put operations to be specified on standard input. Use the convention that a plus sign indicates that the next two strings typed are the key-value pair to be inserted.
Add to Graph the implementations of \(\mathrm{V}()\) and \(\mathrm{E}()\) that return the number of vertices and edges in the graph, respectively. Make sure that your implementations take constant time. Hint: For V(), you may assume that the size() method in ST takes constant time; for
Write a program that takes the name of an image file as a command-line argument and applies a glass filter: set each pixel \(p\) to the color of a random neighboring pixel (whose pixel coordinates both differ from \(p\) 's coordinates by at most 5). glass filter
Write a filter like those in the previous two exercises that creates a wave effect, by copying the color of each pixel \(\left(s_{i}, s_{j}ight)\) in the source image to a target pixel \(\left(t_{i}, t_{j}ight)\), where \(t_{i}=s_{i}\) and \(t_{j}=s_{j}+20 \sin \left(2 \pi s_{j} / 64ight)\). Add
Write a filter DeDup that reads strings from standard input and prints them to standard output, with all duplicate strings removed (and in sorted order).
Modify Body (Program 3.4.1) so that the radius of the circle it draws for a body is proportional to its mass. 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 =
Modify the test client in Turtle to take an odd integer \(n\) as a command-line argument and draw a star with \(\mathrm{n}\) points.
Add a toString() method to Sketch that returns a string representation of the unit vector corresponding to the sketch.
What does the following code fragment print?String string1 = "he11o";String string2 = string1;string1 = "wor1d";StdOut.println(string1);Std0ut.println(string2);
Add methods to Stopwatch that allow clients to stop and restart the stopwatch.
Add a toString() method to Vector that returns the vector components, separated by commas, and enclosed in matching parentheses.
What does the following code fragment print?String \(s=\) "He11o World";s. toUpperCase();s. substring (6, 11);StdOut.println(s);
Given a string that represents a domain name, write a code fragment to determine its top-level domain. For example, the top-level domain of the string cs.princeton.edu is edu.
What does the following recursive function return? public static String mystery (String s) { } int n = s.length(); if (n = 1) return s; String a s.substring(0, n/2); = String b s.substring(n/2, n); return mystery (b) + mystery (a); =
Develop a data type for maintaining statistics for a set of real numbers. Provide a method to add data points and methods that return the number of points, the mean, the standard deviation, and the variance. Develop two implementations: one whose instance values are the number of points, the sum of
Implement the following additions to the Comp1ex API:Write a test client that exercises all of your methods. double theta () Complex minus (Complex b) Complex conjugate() Complex divides (Complex b) Complex power (int b) phase (angle) of this number difference of this number and b conjugate of this
Suppose you want to add a constructor to Comp1ex that takes a double value as its argument and creates a Comp1ex number with that value as the real part (and no imaginary part). You write the following code:But then the statement Comp1ex c = new Comp1ex(1.0); does not compile. Why? Solution:
Provide client methods that return the current hour, minute, and second, as well as toString (), equals(), and hashCode()methods. Develop two implementations: one that keeps the time as a single int value (number of seconds since midnight) and another that keeps three int values, one each for
Find a Complex value for which mand () returns a number greater than 100, and then zoom in on that value.
Write a filter that reads text from an input stream and prints it to an output stream, removing any lines that consist only of whitespace.
Write a program that takes a start string and a stop string as commandline arguments and prints all substrings of a given string that start with the first, end with the second, and otherwise contain neither. Note: Be especially careful of overlaps!
Develop a data type for generating pseudo-random numbers. That is, convert StdRandom to a data type. Instead of using Math . random (), base your data type on a linear congruential generator. This method traces to the earliest days of computing and is also a quintessential example of the value of
Write a program Potential that creates an array of charged particles from values given on standard input (each charged particle is specified by its \(x\) coordinate, \(y\)-coordinate, and charge value) and produces a visualization of the electric potential in the unit square. To do so, sample
Develop a data type for the naming scheme for vehicles known as the Vehicle Identification Number (VIN). A VIN describes the make, model, year, and other attributes of cars, buses, and trucks in the United States.
Is the following class immutable?} import java.util.Date; public class Appointment { } private Date date; private String contact; public Appointment (Date date) { this.date date; this. contact = contact; = } public Date getDate() { return date; }
True or false: At some point during breadth-first search the queue can contain two vertices, one whose distance from the source is 7 and one whose distance is 9.
Suppose the running times of an algorithm for inputs of size \(1,000,2,000\), 3,000, and 4,000 are 5 seconds, 20 seconds, 45 seconds, and 80 seconds, respectively. Estimate how long it will take to solve a problem of size 5,000. Is the algorithm linear, linearithmic, quadratic, cubic, or
Implement the method keys () for HashST.
Implement a PathFinder client AllShortestPaths that creates a PathFinder object for each vertex, with a test client that takes from standard input two vertex queries and prints the shortest path connecting them. Support a delimiter, so that you can type the two-string queries on one line (separated
Each of the four Java functions given here returns a string of length \(n\) whose characters are all \(x\). Determine the order of growth of the running time of each function. Recall that concatenating two strings in Java takes time proportional to the length of the resulting string. public static
Draw all the different BSTs that can represent the sequence of keysbest of it the time was
Suppose that a client performs an intermixed sequence of enqueue and dеqueue operations on a FIFO queue. The enqueue operations insert the integers 0 through 9 in order onto the queue; the dequeue operations print the return values. Which of the following sequence(s) could not occur? a. O 1 2 3 4
Write a Graph client that reads a Graph from a file (in the file format specified in the text), then prints the edges in the graph, one per line.
Apply the scientific method to develop and validate a hypothesis about the order of growth of the running time of each of the following two code fragments as a function of \(n\). String s = for (int i = 0; i
Suppose that the following 31 keys appear (in some order) in a BST of height 4:Draw the top three nodes of the tree (the root and its two children). 10 15 18 21 23 24 30 31 38 41 42 45 50 55 59 60 61 63 71 77 78 83 84 85 86 88 91 92 93 94 98
Add a method isReachable(v) to PathFinder that returns true if there exists some path from the source to \(v\), and false otherwise.
Suppose we have integer keys between 1 and 1000 in a BST and search for 363. Which of the following cannot be the sequence of keys examined?a. 2252401398330363b. 399387219266382381278363c. 3923220911244898258362363d. \(4924278347621299392358 \quad 363\)e. 5925202910245363
Write a filter InfixToPostfix that converts an arithmetic expression from infix to postfix.
What would be the effect of using a queue instead of a stack when forming the shortest path in pathTo()?
Draw the BST that results when you insert the keys E A S Y QUE S T I O N in that order into an initially empty tree. What is the height of the resulting BST?
Write a program that takes from standard input an expression without left parentheses and prints the equivalent infix expression with the parentheses inserted. For example, given the input 1 + 2 ) 3 - 4) * 5 - 6 ) ) ) your program should print ( ( 1 + 2 ) * ( ( 3- 4) * (5 - 6 ) )
Suppose you use a stack instead of a queue for breadth-first search in PathFinder. Does it still compute a path from the source to each vertex? Does it still compute shortest paths? In each case, prove that it does or give a counterexample.
Apply the scientific method to develop and validate a hypothesis about the order of growth of the running time of the following code fragment, as a function of the argument \(n\). public static int f(int n) { } if (n 0) return 1; return f(n-1) + f(n-1); ==
When using generics, what happens if I omit the type argument in either the declaration or the constructor call?\begin{tabular}{llll}Stack stack & \(=\) new Stack ()\(;\) & & // unsafe \\Stack & stack & \(=\) new Stack(); & \(/ /\) unsafe \\Stack stack & \(=\) new Stack(); & \(/ /\)
Modify HashST to use a resizing array so that the average length of the list associated with each hash value is between 1 and 8 .
Modify Vector (Program 3.3.3) so that it implements the Comparable interface (comparing the vectors lexicographically by coordinates). Program 3.3.3 Spatial vectors public class Vector { private final double[] coords; public Vector (double[] a) { // Make a defensive copy to ensure immutability.
Prove by induction that PathFinder computes shortest paths (and shortest-path distances) from the source to each vertex.
Which would you prefer: an algorithm whose order of growth of running time is quadratic, linearithmic, or linear?
I want to use an array representation for a generic stack, but code like the following will not compile. What is the problem?\[\text { private Item[] item = new Item[capacity]; }\]
Modify HashST to add a method remove() that takes a Key argument and removes that key (and the corresponding value) from the symbol table, if it exists.
Write a program that plots average path length versus the number of random edges as random shortcuts are added to a 2-ring graph on 1,000 vertices.
Analyze mathematically the number of compares that mergesort makes to sort an array of length \(n\). For simplicity, assume \(n\) is a power of 2. which is similar to, but more complicated than, the recurrence that we considered for binary search. But if we divide both sides by \(2^{n}\), we get
Write a Queue client that takes an integer command-line argument \(k\) and prints the kth from the last string found on standard input.
What is the order of growth of the running time of the following two functions? Each function takes a string as an argument and returns the string reversed. public static String reversel (String s) { } int ns.length(); String reverse = for (int i = 0; i
Implement the method contains() for BST.
Develop a data type ResizingArrayQueueOfStrings that implements a queue with a fixed-length array in such a way that all operations take constant time. Then, extend your implementation to use a resizing array to remove the length restriction. Hint: The challenge is that the items will "crawl
Implement the method size() for BST.
Give a linear-time algorithm for reversing a string.
Show that the cluster coefficient in a \(k\)-ring graph is \((2 k-2) /(2 k-1)\). Derive a formula for the average path length in a \(k\)-ring graph on \(V\) vertices as a function of both \(V\) and \(k\).
Prove that the array in ResizingArrayStack0fStrings is never less than one-quarter full. Then prove that, for any ResizingArrayStack0fStrings client, the total cost of all of the stack operations divided by the number of operations is bounded by a constant.
Modify BST to add a method remove() that takes a Key argument and removes that key (and the corresponding value) from the symbol table, if it exists. Hint: Replace the key (and its associated value) with the next largest key in the BST (and its associated value); then remove from the BST the node
Write a program MooresLaw that takes a command-line argument \(n\) and outputs the increase in processor speed over a decade if microprocessors double every \(n\) months. How much will processor speed increase over the next decade if speeds double every \(n=15\) months? 24 months?
Show that the diameter in a 2-ring graph on \(V\) vertices is \(\sim V / 4\). Show that if you add one edge connecting two antipodal vertices, the diameter decreases to \(\sim V / 8\).
Implement the method toString() for BST, using a recursive helper method like traverse(). As usual, you can accept quadratic performance because of the cost of string concatenation. Extra credit: Write a linear-time toString() method for BST that uses StringBui 1 der.
Using the 64-bit memory model in the text, give the memory usage for an object of each of the following data:a. Stopwatchb. Turtlec. Vectord. Bodye. Universe
Integer sort. Write a linear-time filter that reads from standard input a sequence of integers that are between 0 and 99 and prints to standard output the same integers in sorted order. For example, presented with the input sequence 98 2 3 1 0 0 0 3 98 98 2 2 2 0002 your program should print the
Perform computational experiments to verify that the average path length in a ring graph on \(V\) vertices is \(\sim 1 / 4 V\). Then, repeat these experiments, but add one random edge to the ring graph and verify that the average path length decreases to \(\sim 3 / 16 \mathrm{~V}\).
Develop a class Stack0fInts that uses a linked-list representation (but no generics) to implement a stack of integers. Write a client that compares the performance of your implementation with Stack to determine the performance penalty from autoboxing and unboxing on your system.
Modify the symbol-table API to handle values with duplicate keys by having get() return an iterable for the values having a given key. Implement BST and Index as dictated by this API. Discuss the pros and cons of this approach versus the one given in the text.
Given a sorted array of Comparable items, write functions floor () and ceiling () that return the index of the largest (or smallest) item not larger (or smaller) than an argument item in logarithmic time.
Suppose \(x\) is a linked-list Node. What is the effect of the following code fragment?\[x \cdot \text { next }=x \cdot \text { next } . \text { next; }\]
Estimate the size of the biggest two-dimensional array of int values that your computer can hold, and then try to allocate such an array.
An array is bitonic if it consists of an increasing sequence of keys followed immediately by a decreasing sequence of keys. Given a bitonic array, design a logarithmic algorithm to find the index of a maximum key.
Write a method find() that takes the first Node in a linked list and a string key as arguments and returns true if some node in the list has key as its item field, and false otherwise.
Modify HashST to implement the SET API given at the end of this section (remover the Comparable restriction from the API).
Find the frequency distribution of words in your favorite novel. Does it obey Zipf's law?

Showing 200 - 300 of 744

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

Step by Step Answers