JAVA PROGRAMING (DATA STRUCTURES AND ALGORITHMS

1. Create an ArrayListReview class with one data field of ArrayList and one with LinkedList with the generic type passed to the class. (2 point)

2. Create a constructor that populate an array list and the LinkedList filled with the generic type through inserting new elements into the specified location index-i in the list. (2 points)

3. A homophone is one of two or more words that are pronounced alike but are different in meaning or spelling; for example, the words two", too", and to". Write a Java program that uses HashMap to find the most words that has the same homophones and return the count of the number of words.

4. You have been given the job of creating a new order processing system for the Yummy Fruit CompanyTM. The system reads pricing information for the various delicious varieties of fruit stocked by YFC, and then processes invoices from customers, determining the total amount for each invoice based on the type and quantity of fruit for each line item in the invoice. The program input starts with the pricing information. Each fruit price (single quantity) is specified on a single line, with the fruit name followed by the price. You can assume that each fruit name is a single word consisting of alphabetic characters (AZ and az). You can also assume that prices will have exactly two decimal places after the decimal point. Fruit names and prices are separated by a single space character. The list of fruit prices is terminated by a single line consisting of the text END_PRICES. After the fruit prices, there will be one or more invoices. Each invoice consists of a series of line items. A line item is a fruit name followed by an integer quantity, with the fruit name and quantity separated by a single space. You can assume that no line item will specify a fruit name that is not specified in the fruit prices. Each invoice is terminated by a line consisting of the text END_INVOICE. As a special case, if a line with the text QUIT appears instead of the beginning of an invoice, the program should exit immediately. The overall input will always be terminated by a QUIT line. (5 points)

Example input:

orange 0.80

pomegranate 2.50

plum 1.20

peach 1.00

persimmon 1.75

lime 0.60

END_PRICES

persimmon 2

orange 3

peach 1

plum 10

pomegranate 5

END_INVOICE

peach 11

plum 5

orange 1

lime 9

END_INVOICE

QUIT

For each invoice, the program should print a single line of the form Total: X.YY where X.YY is the total cost of the invoice, which is the sum of the costs of all of the line items in the invoice. The cost should be printed with exactly two digits after the decimal point.

Example output (corresponding to the input shown above):

Total: 31.40

Total: 23.20

5. Implement insertionSort. (8 points)

6. Write the code to print the No. 50 Fibonacci number. (2 points)

7. Write the main method to test your program and use System.nanoTime() to find out the speed of each step of your program. (1 point)

Bonus: (2 points)

Given any integer, print an English phrase that describes the integer (e.g. One Thousand, Two Hundred Thirty Four). An ArrayList must be used in your program.