These are the questions from my Data Structures Java class. I do not understand the third question.

1. Another simple sort is the odd-even sort. The idea is to repeatedly make two passes through the array. On the first pass you look at all the pairs of items, a[j] and a[j+1], where j is odd (j = 1, 3, 5, ). If their key values are out of order, you swap them. On the second pass you do the same for all the even values (j = 2, 4, 6, ). You do these two passes repeatedly until the array is sorted. Replace the bubbleSort() method in bubbleSort.java (Listing 3.1) with an oddEvenSort() method. Make sure it works for varying amounts of data. You'll need to figure out how many times to do the two passes. The odd-even sort is actually useful in a multiprocessing environment, where aseparate processor can operate on each odd pair simultaneously and then on each even pair. Because the odd pairs are independent of each other, each pair can be checked and swapped, if necessary by a different processor. This makes for a very fast sort.

2. Read the section on Huffman Coding in chapter 8 of the Lafore book [it begins on page 415]. Then write a program to implement Huffman coding and decoding. Use a binary tree to facilitate the decoding part. Your program should do the following:

Accept a text message, possibly of more than one line.

Create a Huffman tree for this message.

Create a code table.

Encode the message into binary.

Decode the message from binary back to text.

If the message is short, the program could also display the Huffman tree after creating it. The ideas in Programming Projects 8.1, 8.2, and 8.3 might prove helpful. You can use String variables to store binary numbers as arrangements of the characters 1 and 0. Don't worry about doing actual bit manipulation unless you really want to.

3. In the game Simon a four-colored disk can play a random sequence of tones and lights. Each color on the disk is actually a button that can be pressed, with a light behind it. As the game makes a tone, it also flashes the light with that tone. The game is for the user to press the buttons in the sequence that is played by the game's controller. The sequence starts with a single light/tone, then increases the number of lights/tones by adding one new trial to the sequence each time the player gets the entire order correct. The game is over when the user makes a mistake in entering the sequence. Using the letters R for Red, G for Green, Y for Yellow, and B for Blue, implement the game. When the player makes a mistake in the sequence, ask if they would like to play again. Be sure that the sequence is random.