3.1 You are given a list, L, and another list, P, containing integers sorted in ascending
order. The operation printLots(L,P) will print the elements in L that are in positions
specified by P. For instance, if P = 1, 3, 4, 6, the elements in positions 1, 3, 4, and 6
in L are printed. Write the procedure printLots(L,P). You may use only the public
Collections API container operations. What is the running time of your procedure? Get solution
3.2 Swap two adjacent elements by adjusting only the links (and not the data) using:
a. Singly linked lists.
b. Doubly linked lists. Get solution
3.3 Implement the contains routine for MyLinkedList. Get solution
3.4 Given two sorted lists, L1 and L2, write a procedure to compute L1 1 L2 using only
the basic list operations. Get solution
3.5 Given two sorted lists, L1 and L2, write a procedure to compute L1 2 L2 using only
the basic list operations. Get solution
3.6 The Josephus problem is the following game: N people, numbered 1 to N, are sitting
in a circle. Starting at person 1, a hot potato is passed. After M passes, the person
holding the hot potato is eliminated, the circle closes ranks, and the game continues
with the person who was sitting after the eliminated person picking up the hot
potato. The last remaining person wins. Thus, if M = 0 and N = 5, players are
eliminated in order, and player 5 wins. IfM = 1 and N = 5, the order of elimination
is 2, 4, 1, 5.
Exercises 97
a. Write a program to solve the Josephus problem for general values of M and N.
Try to make your program as efficient as possible. Make sure you dispose of
cells.
b. What is the running time of your program? Get solution
3.7 What is the running time of the following code?
public static List<Integer> makeList( int N )
{
ArrayList<Integer> lst = new ArrayList<>( );
for( int i = 0; i < N; i++ )
{
lst.add( i );
lst.trimToSize( );
}
} Get solution
3.8 The following routine removes the first half of the list passed as a parameter:
public static void removeFirstHalf( List<?> lst )
{
int theSize = lst.size( ) / 2;
for( int i = 0; i < theSize; i++ )
lst.remove( 0 );
}
a. Why is theSize saved prior to entering the for loop?
b. What is the running time of removeFirstHalf if lst is an ArrayList?
c. What is the running time of removeFirstHalf if lst is a LinkedList?
d. Does using an iterator make removeHalf faster for either type of List? Get solution
3.9 Provide an implementation of an addAll method for the MyArrayList class. Method
addAll adds all items in the specified collection given by items to the end of the
MyArrayList. Also provide the running time of your implementation. The method
signature for you to use is slightly different than the one in the Java Collections API,
and is as follows:
public void addAll( Iterable<? extends AnyType> items ) Get solution
3.10 Provide an implementation of a removeAll method for the MyLinkedList class.
Method removeAll removes all items in the specified collection given by items
from the MyLinkedList. Also provide the running time of your implementation.
The method signature for you to use is slightly different than the one in the Java
Collections API, and is as follows:
public void removeAll( Iterable<? extends AnyType> items )
98 Chapter 3 Lists, Stacks, and Queues Get solution
3.11 Assume that a singly linked list is implemented with a header node, but no tail
node, and that it maintains only a reference to the header node. Write a class that
includes methods to
a. return the size of the linked list
b. print the linked list
c. test if a value x is contained in the linked list
d. add a value x if it is not already contained in the linked list
e. remove a value x if it is contained in the linked list Get solution
3.12 Repeat Exercise 3.11, maintaining the singly linked list in sorted order. Get solution
3.13 Add support for a ListIterator to the MyArrayList class. The ListIterator interface
in java.util has more methods than are shown in Section 3.3.5. Notice that
you will write a listIterator method to return a newly constructed ListIterator,
and further, that the existing iterator method can return a newly constructed
ListIterator. Thus you will change ArrayListIterator so that it implements
ListIterator instead of Iterator. Throw an UnsupportedOperationException for
methods not listed in Section 3.3.5. Get solution
3.14 Add support for a ListIterator to the MyLinkedList class, as was done in
Exercise 3.13. Get solution
3.16 An alternative to providing a ListIterator is to provide a method with signature
Iterator<AnyType> reverseIterator( )
that returns an Iterator, initialized to the last item, and for which next and hasNext
are implemented to be consistent with the iterator advancing toward the front of
the list, rather than the back. Then you could print a MyArrayList L in reverse by
using the code
Iterator<AnyType> ritr = L.reverseIterator( );
while( ritr.hasNext( ) )
System.out.println( ritr.next( ) );
Implement an ArrayListReverseIterator class, with this logic, and have reverseIterator
return a newly constructed ArrayListReverseIterator. Get solution
3.18 For MyLinkedList, implement addFirst, addLast, removeFirst, removeLast, getFirst, and getLast Get solution
3.19 Rewrite the MyLinkedList class without using header and tail nodes and describe
the differences between the class and the class provided in Section 3.5. Get solution
3.20 An alternative to the deletion strategy we have given is to use lazy deletion. To delete an element, we merely mark it deleted (using an extra bit field). The number of deleted and nondeleted elements in the list is kept as part of the data structure. If there are as many deleted elements as nondeleted elements, we traverse the entire list, performing the standard deletion algorithm on all marked nodes.
a. List the advantages and disadvantages of lazy deletion.
b. Write routines to implement the standard linked list operations using lazy deletion. Get solution
3.22 Write a program to evaluate a postfix expression. Get solution
3.23 a. Write a program to convert an infix expression that includes (, ), +, -, *, and / to postfix.
b. Add the exponentiation operator to your repertoire.
c. Write a program to convert a postfix expression to infix. Get solution
3.24 Write routines to implement two stacks using only one array. Your stack routines should not declare an overflow unless every slot in the array is used.
clue: Two stacks can be implemented in an array by having one grow from the low end of the array up, and the other from the high end down.
3.25 #a. Propose a data structure that supports the stack push and pop operations and a third operation findMin, which returns the smallest element in the data structure, all in O(1) worst-case time.
#b. Prove that if we add the fourth operation deleteMin which finds and removes the smallest element, then at least one of the operations must take %(logN) time.
(This requires reading Chapter 7.) Get solution
3.26 Show how to implement three stacks in one array. Get solution
3.27 If the recursive routine in Section 2.4 used to compute Fibonacci numbers is run for N = 50, is stack space likely to run out? Why or why not? Get solution
3.28 A deque is a data structure consisting of a list of items, on which the following operations are possible:
push(x): Insert itemx on the front end of the deque.
pop(): Remove the front item from the deque and return it.
inject(x): Insert itemx on the rear end of the deque.
eject(): Remove the rear item from the deque and return it.
Write routines to support the deque that take O(1) time per operation. Get solution
3.29 Write an algorithm for printing a singly linked list in reverse, using only constant extra space. This instruction implies that you cannot use recursion, but you may assume that your algorithm is a list member function. Get solution
3.30 a. Write an array implementation of self-adjusting lists. In a self-adjusting list, all
insertions are performed at the front. A self-adjusting list adds a find operation,
and when an element is accessed by a find, it is moved to the front of the list
without changing the relative order of the other items. (Not available)
b. Write a linked list implementation of self-adjusting lists. (Not available)
#c. Suppose each element has a fixed probability, pi, of being accessed. Show that
the elements with highest access probability are expected to be close to the front.
Sol: This follows well-known statistical theorems. See Sleator and Tarjan’s paper in Chapter 11 for references.
3.31 Efficiently implement a stack class using a singly linked list, with no header or tail
nodes. Get solution
3.32 Efficiently implement a queue class using a singly linked list, with no header or tail
nodes. Get solution
3.33 Efficiently implement a queue class using a circular array. Get solution
3.34 A linked list contains a cycle if, starting from some node p, following a sufficient number of next links brings us back to node p. p does not have to be the first node in the list. Assume that you are given a linked list that contains N nodes. However, the value of N is unknown.
a. Design an O(N) algorithm to determine if the list contains a cycle. You may use O(N) extra space.
#b. Repeat part (a), but use only O(1) extra space. (Hint: Use two iterators that are initially at the start of the list, but advance at different speeds.) Get solution
3.35 One way to implement a queue is to use a circular linked list. In a circular linked list, the last node’s next link links to the first node. Assume the list does not contain a header and that we can maintain, at most, one iterator corresponding to a node in the list. For which of the following representations can all basic queue operations be performed in constant worst-case time? Justify your answers.
a. Maintain an iterator that corresponds to the first item in the list.
Sol: Does not work in
constant time for insertions at the end.
b. Maintain an iterator that corresponds to the last item in the list.
Sol: Because of the circularity, we can access the front item in constant time, so this works.
3.36 Suppose we have a reference to a node in a singly linked list that is guaranteed not to be the last node in the list. We do not have references to any other nodes (except by following links). Describe an O(1) algorithm that logically removes the value stored in such a node from the linked list, maintaining the integrity of the linked list. (Hint: Involve the next node.) Get solution
3.37 Suppose that a singly linked list is implemented with both a header and a tail node.
Describe constant-time algorithms to
a. Insert item x before position p (given by an iterator).
b. Remove the item stored at position p (given by an iterator). Get solution
