Questions and Answers of Introduction to Algorithms

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
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
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
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
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 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
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
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
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
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
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,
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
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
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
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
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
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
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] ·
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
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
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
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