Questions and Answers of Big Java, Enhanced Early Objects

How can you change the selection sort algorithm so that it sorts the elements in descending order (that is, with the largest element at the beginning of the array)?
Suppose we modified the selection sort algorithm to start at the end of the array, working toward the beginning. In each step, the current position is swapped with the minimum. What is the result of
We determined that the actual number of visits in the selection sort algorithm is: T(n) = 1n + 3n-3 We characterized this method as having O(n) growth. Compute the actual ratios T(2,000)/T(1,000)
What is the big-Oh time estimate of the following method in terms of n, the length of a? Use the “light bulb pattern” method of Section 14.7 to visualize your result. public static void swap
Consider this algorithm for sorting an array. Set k to the length of the array. Find the maximum of the first k elements. Remove it, using the second algorithm of Section 7.3.6. Decrement k and place
Why does only one of the two while loops at the end of the merge method in Section 14.4 do any work?
A run is a sequence of adjacent repeated values (see Exercise R7.21). Describe an O(n) algorithm to find the length of the longest run in an array.Data from exercise R7.21A run is a sequence of
Trace a walkthrough of: a. Linear search for 7 in b. Binary search for 8 in c. Binary search for 8 in -7 1 3 3 4 7 11 13 -7 2 2 3 4 7 8 11 13 -7 1 2 3 5 7 10 13
Suppose we modify the quicksort algorithm from Special Topic 14.3, selecting the middle element instead of the first one as pivot. What is the running time on an array that is already sorted?
Implement a program that measures the performance of the insertion sort algorithm described in Special Topic 14.2.Data from special topic 14.2 Special Topic 14.2 Insertion Sort Insertion sort is
Implement a general merge method that can merge any number of sorted subsequences.The method gets an ArrayList with the sorted sequences that should be merged.
Use the general merge method of the preceding exercise to implement the following sort algorithm. Find all non-descending subsequences of an array (that is, sequences such that a[i]≤ a[i + 1]
Reimplement Exercise •• E14.11 so that you don’t generate new arrays with the subsequences, but instead collect the starting index values. Then implement the generalized merge method so that it
Implement the following sorting algorithm. First split the given array a into nondecreasing and decreasing segments (that is, segments such that a[i] ≤ a[i + 1] ≤ ... a[i + k] or a[j] > a[j + 1]
Modify the binary search algorithm so that it returns an array of length 2 with the lowest index and highest index of those element(s) that equal the searched value.For example, when searching for 3,
Explain what the following code prints. Draw a picture of the linked list after each step. LinkedList staff = new LinkedList (); staff.addFirst ("Harry"); staff.addFirst("Diana");
Explain what the following code prints. Draw a picture of the linked list after each step. LinkedList staff = new Linked List (); staff.addFirst("Harry"); staff.addLast ("Diana");
Explain what the following code prints. Draw a picture of the linked list and the iterator position after each step. LinkedList staff = new LinkedList (); ListIterator iterator = staff.
Explain what the following code prints. Draw a picture of the linked list and the iterator position after each step. LinkedList staff = new LinkedList>(); ListIterator iterator = staff.
Repeat Exercise •• R15.10 , using the removeIf method. (Read the description in the API of the Collection interface.) Use a lambda expression (see Special Topic 10.4).Data from exercise
Arrays and lists remember the order in which you added elements; sets do not. Why would you want to use a set instead of an array or list?
Why are set iterators different from list iterators?
Why is the collection of the keys of a map a set and not a list?
Why is the collection of the values of a map not a set?
The union of two sets A and B is the set of all elements that are contained in A, B, or both. The intersection is the set of all elements that are contained in A and B. How can you compute the union
Write a method: public static void downsize that removes every nth employee from a linked list. (LinkedList employeeNames, int n)
Write a method: public static void reverse that reverses the entries in a linked list. (LinkedList strings)
Read all words from a file and add them to a map whose keys are the first letters of the words and whose values are sets of words that start with that same letter. Then print out the word sets in
Read all words from a file and add them to a map whose keys are word lengths and whose values are comma-separated strings of words of the same length. Then print out those strings, in increasing
A labeled point has x- and y-coordinates and a string label. Provide a class Labeled-Point with a constructor LabeledPoint(int x, int y, String label) and hashCode and equals methods. Two labeled
Add a % (remainder) operator to the expression calculator of Section 15.6.3.Data from section 15.6.3
Add a ^ (power) operator to the expression calculator of Section 15.6.3. For example, 2 ^ 3 evaluates to 8. As in mathematics, your power operator should be evaluated from the right. That is, 2 ^ 3 ^
Modify the maze solver program of Section 15.6.4 to handle mazes with cycles. Keep a set of visited intersections. When you have previously seen an intersection, treat it as a dead end and do not add
Reimplement Exercise •• E15.4 so that the keys of the map are objects of class Student. A student should have a first name, a last name, and a unique integer ID. For grade changes and removals,
Write a class Polynomial that stores a polynomial such as: p(x) = 5x0 + 9x-x-10 as a linked list of terms. A term contains the coefficient and the power of x. For example, you would store p(x) as
Repeat Exercise ••• P15.3 , but use a Map for the coefficients.Data from exercise P15.3 Write a class Polynomial that stores a polynomial such as: p(x) = 5x0 + 9x-x-10 as a linked list of
Supply compatible hashCode and equals methods to the Student class described in Exercise ••• P15.2 . Test the hash code by adding Student objects to a hash set.Data from exercise P15.2
Modify the expression calculator of Section 15.6.3 to convert an expression into reverse Polish notation. Instead of evaluating the top and pushing the result, append the instructions to a string.
Suppose you buy 100 shares of a stock at $12 per share, then another 100 at $10 per share, and then sell 150 shares at $15. You have to pay taxes on the gain, but exactly what is the gain? In the
Extend Exercise Business P15.12 to a program that can handle shares of multiple companies. The user enters commands buy symbol quantity price and sell symbol quantity price. Keep a Map> that
Consider the problem of finding the least expensive routes to all cities in a network from a given starting point. For example, in the network shown on the mapbelow, the least expensive route from
The linked list class in the Java library supports operations addLast and removeLast. To carry out these operations efficiently, the LinkedList class has an added reference last to the last node in
The linked list class in the Java library supports bidirectional iterators. To go backward efficiently, each Node has an added reference, previous, to the predecessor node in the linked list. Draw a
What is the big-Oh efficiency of replacing all negative values in a linked list of Integer objects with zeroes? Of removing all negative values?
What is the big-Oh efficiency of replacing all negative values in an array list of Integer objects with zeroes? Of removing all negative values?
In the LinkedList implementation of Section 16.1, we use a flag isAfterNext to ensure that calls to the remove and set methods occur only when they are allowed. It is not actually necessary to
What is the big-Oh efficiency of the size method of Exercise • E16.4?Data from exercise E16.4Add a method size to our implementation of the LinkedList class that computes the number of elements in
Show that the introduction of the size method in Exercise • E16.6 does not affect the big-Oh efficiency of the other list operations.Data from exercise E16.6Add an instance variable currentSize to
Given the size method of Exercise • E16.6 and the get method of Exercise • P16.1, what is the big-Oh efficiency of this loop:Data from exercise E16.6Add an instance variable currentSize to our
Given the size method of Exercise • E16.6 and the get method of Exercise ••• P16.3, what is the big-Oh efficiency of this loop?Data from exercise E16.6Add an instance variable currentSize to
It is not safe to remove the first element of a linked list with the removeFirst method when an iterator has just traversed the first element. Explain the problem by tracing the code and drawing a
Continue Exercise •• R16.10 by providing a code example demonstrating the problem.Data from exercise R16.10 It is not safe to remove the first element of a linked list with the removeFirst
It is not safe to simultaneously modify a linked list using two iterators. Find a situation where two iterators refer to the same linked list, and when you add an element with one iterator and remove
Continue Exercise ••• R16.12 by providing a code example demonstrating the problem.Data from exercise R16.12 It is not safe to simultaneously modify a linked list using two iterators. Find a
In the implementation of the LinkedList class of the standard Java library, the problem described in Exercise •• R16.10 and Exercise ••• R16.12 results in a ConcurrentModification
Consider the efficiency of locating the kth element in a doubly-linked list of length n. If k > n/2, it is more efficient to start at the end of the list and move the iterator to the previous
A linked list implementor, hoping to improve the speed of accessing elements, provides an array of Node references, pointing to every tenth node. Then the operation get(n) looks up the reference at
Suppose an array list implementation were to add ten elements at each reallocation instead of doubling the capacity. Show that the addLast operation no longer has amortized constant time.
Consider an array list implementation with a removeLast method that shrinks the internal array to half of its size when it is at most half full. Give a sequence of addLast and removeLast calls that
Suppose the ArrayList implementation of Section 16.2 had a removeLast method that shrinks the internal array by 50 percent when it is less than 25 percent full. Show that any sequence of addLast and
Given a queue with O(1) methods add, remove, and size, what is the big-Oh efficiency of moving the element at the head of the queue to the tail? Of moving the element at the tail of the queue to the
A deque (double-ended queue) is a data structure with operations addFirst, remove-First, addLast, and removeLast. What is the O(1) efficiency of these operations if the deque is implemented asa. a
In our circular array implementation of a queue, can you compute the value of the currentSize from the values of the head and tail fields? Why or why not?
Draw the contents of a circular array implementation of a queue q, with an initial array size of 10, after each of the following loops: a. for (int i = 1; i
Suppose you are stranded on a desert island on which stacks are plentiful, but you need a queue. How can you implement a queue using two stacks? What is the big-Oh running time of the queue
Suppose you are stranded on a desert island on which queues are plentiful, but you need a stack. How can you implement a stack using two queues? What is the big-Oh running time of the stack
Craig Coder doesn’t like the fact that he has to implement a hash function for the objects that he wants to collect in a hash table. “Why not assign a unique ID to each object?” he asks. What
Add a method reverse to our LinkedList implementation that reverses the links in a list. Implement this method by directly rerouting the links, not by using an iterator.
Consider a version of the LinkedList class of Section 16.1.8 in which the addFirst method has been replaced with the following faulty version:Develop a program ListTest with a test case that shows
Consider a version of the LinkedList class of Section 16.1.8 in which the iterator’s hasNext method has been replaced with the following faulty version:Develop a program ListTest with a test case
Add a method size to our implementation of the LinkedList class that computes the number of elements in the list by following links and counting the elements until the end of the list is reached.
Solve Exercise • E16.4 recursively by calling a recursive helper methodIf start is null, then the size is 0. Otherwise, it is one larger than the size of start.next.Data from exercise E16.4 Add a
Add an instance variable currentSize to our implementation of the LinkedList class.Modify the add, addLast, and remove methods of both the linked list and the list iterator to update the currentSize
Reimplement the LinkedList class of Section 16.1.8 so that the Node and LinkedList - Iterator classes are not inner classes.
Reimplement the LinkedList class of Section 16.1.8 so that it implements the java.util.List interface. Extend the java.util.AbstractSequentialList class.
Provide a listIterator method for the ArrayList implementation in Section 16.2.3.Your method should return an object of a class implementing java.util.ListIterator.Also have the ArrayList class
Provide a removeLast method for the ArrayList implementation in Section 16.2.3 that shrinks the internal array by 50 percent when it is less than 25 percent full.
Complete the implementation of a stack in Section 16.3.2, using an array for storing the elements.
Complete the implementation of a queue in Section 16.3.3, using a sequence of nodes for storing the elements.
Add a method firstToLast to the implementation of a queue in Exercise • E16.12 .The method moves the element at the head of the queue to the tail of the queue. The element that was second in line
Add a method lastToFirst to the implementation of a queue in Exercise • E16.12. The method moves the element at the tail of the queue to the head.Data from exercise E16.12 Complete the
Add a method firstToLast, as described in Exercise • E16.13 , to the circular array implementation of a queue.Data from exercise E16.13 Add a method firstToLast to the implementation of a queue
Add a method lastToFirst, as described in Exercise • E16.14, to the circular array implementation of a queue.Data from exercise E16.14 Add a method lastToFirst to the implementation of a queue in
The hasNext method of the hash set implementation in Section 16.4.5 finds the location of the next element, but when next is called, the same search happens again. Improve the efficiency of these
Reallocate the buckets of the hash set implementation in Section 16.4.5 when the load factor is greater than 1.0 or less than 0.5, doubling or halving its size. Note that you need to recompute the
Implement the remove operation for iterators on the hash set in Section 16.4.5.
Implement the hash set in Section 16.4.5, using the “MAD (multiply-add-divide) method” for hash code compression. For that method, you choose a prime number p larger than the length L of the hash
Add methods to count collisions to the hash set in Section 16.4.5 and the one in Exercise • E16.20 . Insert all words from a dictionary (in /usr/share/dict/words or in words.txt in your companion
Add methods Object get(int n) and void set(int n, Object newElement) to the LinkedList class. Use a helper method that starts at first and follows n links: private Node getNode(int n)
Solve Exercise • P16.1 by using a recursive helper method:Data from exercise P16.1 dd methods Object get(int n) and void set(int n, Object newElement) to the LinkedList class. Use a helper method
Improve the efficiency of the get and set methods of Exercise • P16.1 by storing (or“caching”) the last known (node, index) pair. If n is larger than the last known index, start from the
Add a method boolean contains(Object obj) that checks whether our LinkedList implementation contains a given object. Implement this method by directly traversing the links, not by using an iterator.
Solve Exercise •• P16.4 recursively, by calling a recursive helper method private static boolean contains(Node start, Object obj) If start is null, then it can’t contain the object. Otherwise,
A linked list class with an O(1) addLast method needs an efficient mechanism to get to the end of the list, for example by setting an instance variable to the last element. It is then possible to
In a circular doubly-linked list, the previous reference of the first node points to the last node, and the next reference of the last node points to the first node. Change the doubly-linked list
Modify the insertion sort algorithm of Special Topic 14.2 to sort a linked list.Data from special topic 14.2•• Special Topic 14.2 Insertion Sort Insertion sort is another simple sorting
The LISP language, created in 1960, implements linked lists in a very elegant way.You will explore a Java analog in this set of exercises. Conceptually, the tail of a list—that is, the list with
Add a method length to the LispList interface of Exercise •• P16.9 that returns the length of the list. Implement the method in the EmptyList and NonEmptyList classes.Data from exercise P16.9
Add a method:to the LispList interface of Exercise •• P16.9 . Implement the method in the EmptyList and NonEmptyList classes. When merging two lists, alternate between the elements, then add the
Add a method:to the LispList interface of Exercise •• P16.9 that returns true if the list contains an element that equals obj.Data from exercise P16.9 The LISP language, created in 1960,

Showing 1 - 100 of 791