Students often suffer from a large abundance of academic assignments at college and school. Sometimes, the number of papers that have to be completed is so big that a student simply can’t cope with al

Assignment 1

The Shell sort is a variation of the bubble sort. Instead of comparing adjacent values, the Shell sort adapts a concept from the binary search to determine a “gap” across which values are compared before any swap takes place. In the first pass, the gap is half the size of the array. For each subsequent pass, the gap size is cut in half. For the final pass(es), the gap size is 1, so it would be the same as a bubble sort. The passes continue until no swaps occur.

Below is the same set of values as per the bubble sort example in Chapter 18 (p. 681), showing the first pass of the Shell sort:

Assignment 2

1. PP 12.4 (page 515)

The ArrayStack implementation in this chapter keeps the top variable pointing to the next array position above the actual top of the stack. Modify the array implementation such that stack[top] is the actual top of the stack.

1. PP 13.8 (page 546)

There is a data structure called a drop-out stack that behaves like a stack in every respect except that if the stack size is n, then when the n+1 element is pushed, the bottom element is lost. Implement a drop-out stack using links, by modifying the LinkedStack code.

1. PP 14.6 (page 578)

A data structure called a deque (pronounced like “deck”) is closely related to a queue. The name deque stands for double-ended queue. The difference between the two is that with a deque you can insert or remove from either end of the queue. Implement a deque using arrays (start with CircularArrayQueue).

1. PP 14.9 (page 579)

Create an application using both a stack and a queue to test whether a given string is a palindrome (i.e., the characters read the same forward or backward). Your algorithm should parse the input string only ONCE, and not construct a reverse string.

Assignment 3

For the exercises below, use the classes defined in java.util rather than the classes developed in the textbook.

Hint: Make the container in your stack or queue class of the type indicated—do NOT use inheritance.

1. PP 15.1 (page 615)

Implement a stack using a java.util.LinkedList.

1. PP 15.2 (page 615)

Implement a stack using a java.util.ArrayList.

1. PP 15.3 (page 615)

Implement a queue using a java.util.LinkedList.

1. PP 15.4 (page 615)

Implement a queue using a java.util.ArrayList.

Assignment 4

1. Complete the implementation of a DecisionTree, introduced in Chapter 19. This will require completing a number of methods from the source code for this chapter, particularly for LinkedBinaryTree. Your initial test should be the BackPainAnalyzer output from Listing 19.6 on page 746. Show test cases for at least two other correct traversals. Develop and demonstrate another decision tree that is at least as complex.

2. PP 20.5 (page 801)

Implement a balance tree method for the linked implementation using the brute force method described in Section 20.4 of your textbook.

Hint: Copy the elements into an ArrayList

using an in-order traversal. Recursively build a balanced tree using a binary partitioning.

Assignment 5

1. PP 21.5 (page 831)

As described in Section 21.5 of your textbook, it is possible to make the heap sort algorithm more efficient by writing a method that will build a heap in place using the array to be sorted. Implement such a method, and rewrite the heap sort algorithm to make use of it.

1. PP 24.3 (page 902)

Complete the implementation of Graph.java using an adjacency matrix that was presented in this chapter.

HINT: Identify all of the missing implementations in Graph.java before you start. Some methods like size() and getIndex(T vertex) should be tackled first.

1. PP I.4 (page 1068)

Implement a dynamically resizable hash table to store people’s names and Social Security numbers. Use the extraction method with division using the last four digits of the Social Security number. Use an initial table size of 31 and a load factor of 0.80. Use open addressing with double hashing using an extraction method on the first three digits of the Social Security number.

Note: U.S. SSN numbers are 9 digits like the Canadian Social Insurance Number (SIN).