Solved: The Josephus problem is the following game: N people, numbered 1 to N, are

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?

Swap two adjacent elements by adjusting only the links (and not the data) using: a. Singly linked lists. b. Doubly linked lists.

Implement the contains routine for MyLinkedList.

Given two sorted lists, L1 and L2, write a procedure to compute L1 L2 using only the basic list operations.

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. If M = 1 and N = 5, the order of elimination is 2, 4, 1, 5.

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. If M = 1 and N = 5, the order of elimination is 2, 4, 1, 5. 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?

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( ); } }

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?

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 )

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 )

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

Repeat Exercise 3.11, maintaining the singly linked list in sorted order.

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.

Add support for a ListIterator to the MyLinkedList class, as was done in Exercise 3.13.

Add a splice operation to the LinkedList class. The method declaration public void splice(Iterator<T> itr, MyLinkedList<? extends T> lst ) removes all the items from lst (making lst empty), placing them prior to itr in MyLinkedList this. lst and this must be different lists. Your routine must run in constant time.

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.

Modify the MyArrayList class to provide stringent iterator checking by using the techniques seen in Section 3.5 for MyLinkedList

For MyLinkedList, implement addFirst, addLast, removeFirst, removeLast, getFirst, and getLast by making calls to the private add, remove, and getNode routines, respectively

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.

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.

Write a program to check for balancing symbols in the following languages: a. Pascal (begin/end, (), [], {}). b. Java (/* */, (), [], {} ). c. Explain how to print out an error message that is likely to reflect the probable cause.

Write a program to evaluate a postfix expression.

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.

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.

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.)

Show how to implement three stacks in one array.

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?

A deque is a data structure consisting of a list of items, on which the following operations are possible: push(x): Insert item x on the front end of the deque. pop(): Remove the front item from the deque and return it. inject(x): Insert item x 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.

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.

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. b. Write a linked list implementation of self-adjusting lists. 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

Efficiently implement a stack class using a singly linked list, with no header or tail nodes

Efficiently implement a queue class using a singly linked list, with no header or tail nodes.

Efficiently implement a queue class using a circular array.

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.)

One way to implement a queue is to use a circular linked list. In a circular linked list, the last nodes 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. b. Maintain an iterator that corresponds to the last item in the list.

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.)

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).