Data Structures and Algorithms in Java 6th edition Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser - Solutions

Describe in detail how to swap two nodes x and y (and not just their contents) in a singly linked list L given references only to x and y. Repeat this exercise for the case when L is a doubly linked list. Which algorithm takes more time?
Give an algorithm for concatenating two doubly linked lists L andM, with header and trailer sentinel nodes, into a single list L′.
Describe an algorithm for concatenating two singly linked lists L and M, into a single list L′ that contains all the nodes of L followed by all the nodes of M.
Suppose you are designing a multiplayer game that has n ≥ 1000 players, numbered 1 to n, interacting in an enchanted forest. The winner of this game is the first player who can meet all the other players at least once (ties are allowed). Assuming that there is a method meet(i, j), which is called
Suppose you are given an array, A, containing 100 integers that were generated using the method r.nextInt(10), where r is an object of type java.util.Random. Let x denote the product of the integers in A. There is a single number that x will equal with probability at least 0.99. What is that number
Give Java code for performing add(e) and remove(i) methods for the Scoreboard class, as in Code Fragments 3.3 and 3.4, except this time, don’tmaintain the game entries in order. Assume that we still need to keep n entries stored in indices 0 to n−1. You should be able to implement the methods
Let B be an array of size n ≥ 6 containing integers from 1 to n−5 inclusive, five of which are repeated. Describe an algorithm for finding the five integers in B that are repeated.
Let A be an array of size n ≥ 2 containing integers from 1 to n−1 inclusive, one of which is repeated. Describe an algorithm for finding the integer in A that is repeated.
Give three different examples of a single Java statement that assigns variable, backup, to a new array with copies of all int entries of an existing array, original.
Give an implementation of the size( ) method for the DoublyLinkedList class, assuming that we did not maintain size as an instance variable.
Give an implementation of the size( ) method for the CircularlyLinkedList class, assuming that we did not maintain size as an instance variable.
Give an implementation of the size( ) method for the SingularlyLinkedList class, assuming that we did not maintain size as an instance variable.
Describe a method for finding the middle node of a doubly linked list with header and trailer sentinels by “link hopping,” and without relying on explicit knowledge of the size of the list. In the case of an even number of nodes, report the node slightly left of center as the “middle.” What
The removeFirst method of the SinglyLinkedList class includes a special case to reset the tail field to null when deleting the last node of a list (see lines 51 and 52 of Code Fragment 3.15). What are the consequences if we were to remove those two lines from the code? Explain why the class would
Explain the changes that would have to be made to the program of Code Fragment 3.8 so that it could perform the Caesar cipher for messages that are written in an alphabet-based language other than English, such as Greek, Russian, or Hebrew.
Write a program that consists of three classes, A, B, and C, such that B extends A and that C extends B. Each class should define an instance variable named “x” (that is, each has its own variable named x). Describe a way for a method in C to access and set A’s version of x to a given value,
Explain why the Java dynamic dispatch algorithm, which looks for the method to invoke for a call obj.foo( ), will never get into an infinite loop.
Modify the advance method of the FibonacciProgression class so as to avoid use of any temporary variable.
Write a Java class that extends the Progression class so that each value in the progression is the absolute value of the difference between the previous two values. You should include a default constructor that starts with 2 and 200 as the first two values and a parametric constructor that starts
Assume that we change the CreditCard class (see Code Fragment 1.5) so that instance variable balance has private visibility, but a new protected method is added, with signature setBalance(newBalance). Show how to properly implement the method PredatoryCreditCard.processMonth( ) in this setting.
The PredatoryCreditCard class provides a processMonth( ) method that models the completion of a monthly cycle. Modify the class so that once a customer has made ten calls to charge during a month, each additional call to that method in the current month results in an additional $1 surcharge.
If the parameter to the makePayment method of the CreditCard class (see Code Fragment 1.5) were a negative number, that would have the effect of raising the balance on the account. Revise the implementation so that it throws an IllegalArgumentException if a negative amount is sent as a parameter.
Give an example of a Java code fragment that performs an array reference that is possibly out of bounds, and if it is out of bounds, the program catches that exception and prints the following error message:“Don’t try buffer overflow attacks in Java!”
Consider the inheritance of classes from Exercise R-2.12, and let d be an object variable of type Horse. If d refers to an actual object of type Equestrian, can it be cast to the class Racer? Why or why not?In Exercise R-2.12Draw a class inheritance diagram for the following set of classes:•
Consider the following code fragment, taken from some package:
What are some potential efficiency disadvantages of having very shallow inheritance trees, that is, a large set of classes, A, B, C, and so on, such that all of these classes extend a single class, Z?
What are some potential efficiency disadvantages of having very deep inheritance trees, that is, a large set of classes, A, B, C, and so on, such that B extends A, C extends B, D extends C, etc.?
If we choose an increment of 128, how many calls to the nextValue method from the ArithmeticProgression class of Section 2.2.3 can we make before we cause a long-integer overflow?
Give a short fragment of Java code that uses the progression classes from Section 2.2.3 to find the eighth value of a Fibonacci progression that starts with 2 and 2 as its first two values.
Assume that we change the CreditCard class (see Code Fragment 1.5) so that instance variable balance has private visibility. Why is the following implementation of the PredatoryCreditCard.charge method flawed? public boolean charge(double price) { boolean isSuccess = super.charge(price); if
Assume that we change the CreditCard class (see Code Fragment 1.5) so that instance variable balance has private visibility. Why is the following implementation of the PredatoryCreditCard.charge method flawed? public boolean charge(double price) { boolean isSuccess = super.charge(price); if
Give three examples of life-critical software applications.
Modify the CreditCard class to add a to String( ) method that returns a String representation of the card (rather than printing it to the console, as done by printSummary). Modify the main method from Code Fragment 1.6 accordingly to use the standard println command.
Modify the CreditCard class from Code Fragment 1.5 so that printSummary becomes a nonstaticmethod, and modify the mainmethod fromCode Fragment 1.6 accordingly.
Write a short Java program that takes two arrays a and b of length n storing int values, and returns the dot product of a and b. That is, it returns an array c of length n such that c[i] = a[i] · b[i], for i = 0, . . . ,n−1.
Write a short Java program that outputs all possible strings formed by using the characters 'c', 'a', 't', 'd', 'o', and 'g' exactly once.
Write a Java method that takes an array of float values and determines if all the numbers are different from each other (that is, they are distinct).
The p-norm of a vector v = (v1,v2, . . . ,vn) in n-dimensional space is defined asFor the special case of p = 2, this results in the traditional Euclidean norm, which represents the length of the vector. For example, the Euclidean norm of a two-dimensional vector with coordinates (4,3) has a
Write a short Java method that takes an array of int values and determines if there is a pair of distinct elements of the array whose product is even.
Modify the declaration of the first for loop in the main method in Code Fragment 1.6 so that its charges will cause exactly one of the three credit cards to attempt to go over its credit limit. Which credit card is it?
Modify the CreditCard class from Code Fragment 1.5 so that it ignores any request to process a negative payment amount.
Modify the CreditCard class from Code Fragment 1.5 to include a method that updates the credit limit.
Write a short Java method that counts the number of vowels in a given character string.
Write a short Java method that takes an integer n and returns the sum of the squares of all positive integers less than or equal to n.
Write a short Java method that takes an integer n and returns the sum of all the odd positive integers less than or equal to n.
Suppose that we create an array A of GameEntry objects, which has an integer scores field, and we clone A and store the result in an array B. If we then immediately set A[4].score equal to 550, what is the score value of the GameEntry object referenced by B[4]?
Write a short Java method that takes an integer n and returns the sum of all positive integers less than or equal to n.
Write a short Java method, isEven, that takes an int i and returns true if and only if i is even. Your method cannot use the multiplication, modulus, or division operators, however.
Write a short Java method, isMultiple, that takes two long values, n and m, and returns true if and only if n is a multiple of m, that is, n = mi for some integer i.

Showing 1500 - 1600 of 1549

Step by Step Answers