can ypu help me solve it by tomorrow
Assignment 2 ASSIGNMENT 2 Assignment 2 tests your knowledge of program complexity (Chapter 22), sorting methods (Chapter 23), and user-defined lists, stacks, queues, and priority queues (Chapter 24). Design a program/project/driver class YourNameAssignment2 and the following classes (with exact1 names, replace YourName with your actual first name or the name you go by, no spaces): Class Description YourNameArray A new class that contains an array A of N integers, a constructor that takes an array as parameter to create the array A, and the following sorting methods (see Chapter 23): ▪ InsertionSort that sorts the array A of N integers using insertion sort. ▪ BubbleSort that sorts the array A of N integers using bubble sort. ▪ MergeSort that sorts the array A of N integers using merge sort. ▪ QuickSort that sorts the array A of N integers using quick sort. ▪ SortAlgorithmComplexity that outputs to the console for each of the 4 sorting algorithms above, their complexity (see Chapter 22) and an explanation of which one of the sorting methods is better and why. Make sure the entire text shows in screenshots. This method does not compute anything, just outputs the explanation. ▪ SortArray that uses the best sorting method from above (that you determined and explained in the SortAlgorithmComplexity) to sort the array A and print the array. YourNameList A complete version of user-defined MyList class from Chapter 24 (meaning you need to add the code for the method that were not coded in the book and have an omitted or “Left as an exercise” comment). Add an additional output method that outputs the list in the format: LIST: [position0], [position1], …, [positionN] YourNameArrayList A complete version of the user-defined MyArrayList class from Chapter 24 that code all the methods (including the omitted or “Left as an exercise” methods) and uses the YourNameList instead of MyList. Add an additional output method that outputs the list in the format: LIST: [position0], [position1], …, [positionN] YourNameLinkedList A complete version of the user-defined MyLinkedList class from Chapter 24 that code all the methods (including the omitted or “Left as an exercise” methods and uses the YourNameList instead of MyList. Add an additional output method that outputs the list in the format: LINKED LIST: [position0], [position1], …, [positionN] YourNameQueue A complete version of the user-defined GenericQueue class from Chapter 24 that code all the methods (including the omitted or “Left as an exercise” methods and uses a YourNameLinkedList instead of the pre-defined LinkedList used in textbook. Add an additional output method that outputs the list in the format: QUEUE: [position0], [position1], …, [positionN] YourNameAssignment2 Driver class main Creates an array of 10 integers, read the values from the user and build instances of the user-defined lists above (YourNameArray, YourNameArrayList, YourNameLinkedList, and YourNameQueue) with the values from the array and test/demonstrate all their functionality/methods (e.g. output, add, remove, delete, etc) including the SortArray and SortAlgorithmComplexity. You can and should start with the examples from the textbook/presentation and adapt them to the assignment at hand and use the appropriate names and add the code and requirements above. Create a Microsoft Word screenshots document called YourNameAssignment2-Screenshot.docx (replace YourName with your actual name) that contains screenshots of the entire JAVA source code in the editor window, (YourNameAssignment2) and the entire output (from the driver class). If the entire class JAVA source code or the output does not fit in one screenshot, create multiple screenshots and add them to the document. Submit the following 7 files: YourNameAssignment2.java, YourNameArray.java, YourNameList.java, YourNameArrayList.java, YourNameLinkedList.java, YourNameQueue.java Java source code files and YourNameAssignment2-Screenshots.docx screenshots document on eCampus under Assignment 2. Do not archive the files or submit other file formats. If you choose add additional classes, please make sure you explain why at the beginning of the screenshots document, attach screenshots to the document and attach the JAVA files to your submission. 1 Use the exact names (spelling, caps), parameters, returned values, functionality. You are not going to earn any credit if the classes and methods do not contain your actual name and have the exact/precise names and functionality. Yes, you may find examples in the textbook with different names and cases and with other methods, but you will need to adapt them to have this exact names and cases, to earn credit for the assignment. Chapter 1 Chapter 22: Developing Efficient Algorithms Dr. Adriana Badulescu Objectives ▪ To estimate algorithm efficiency using the Big notation (§22.2). ▪ To explain growth rates and why constants and nondominating terms can be ignored in the estimation (§22.2). ▪ To determine the complexity of various types of algorithms (§22.3). ▪ To analyze the binary search algorithm (§22.4.1). ▪ To analyze the selection sort algorithm (§22.4.2). ▪ To analyze the insertion sort algorithm (§22.4.3). ▪ To analyze the Tower of Hanoi algorithm (§22.4.4). ▪ To describe common growth functions (constant, logarithmic, log-linear, quadratic, cubic, exponential) (§22.4.5). ▪ To design efficient algorithms for finding Fibonacci numbers using dynamic programming (§22.5). ▪ To find the GCD using Euclid’s algorithm (§22.6). ▪ To finding prime numbers using the sieve of Eratosthenes (§22.7). ▪ To design efficient algorithms for finding the closest pair of points using the divide-and-conquer approach (§22.8). ▪ To solve the Eight Queens problem using the backtracking approach (§22.9). ▪ To design efficient algorithms for finding a convex hull for a set of points (§22.10). Executing Time ▪ Suppose two algorithms perform the same task such as search (linear search vs. binary search). Which one is better? One possible approach to answer this question is to implement these algorithms in Java and run the programs to get execution time. But there are two problems for this approach: ▪ First, there are many tasks running concurrently on a computer. The execution time of a particular program is dependent on the system load. ▪ Second, the execution time is dependent on specific input. Consider linear search and binary search for example. If an element to be searched happens to be the first in the list, linear search will find the element quicker than binary search. Growth Rate ▪ It is very difficult to compare algorithms by measuring their execution time. ▪ To overcome these problems, a theoretical approach was developed to analyze algorithms independent of computers and specific input. ▪ This approach approximates the effect of a change on the size of the input. In this way, you can see how fast an algorithm’s execution time increases as the input size increases, so you can compare two algorithms by examining their growth rates. Big O Notation ▪ Consider linear search. The linear search algorithm compares the key with the elements in the array sequentially until the key is found or the array is exhausted. If the key is not in the array, it requires n comparisons for an array of size n. If the key is in the array, it requires n/2 comparisons on average. ▪ The algorithm’s execution time is proportional to the size of the array. If you double the size of the array, you will expect the number of comparisons to double. The algorithm grows at a linear rate. ▪ The growth rate has an order of magnitude of n. Computer scientists use the Big O notation to abbreviate for “order of magnitude.” Using this notation, the complexity of the linear search algorithm is O(n), pronounced as “order of n.” Best, Worst, and Average Cases ▪ For the same input size, an algorithm’s execution time may vary, depending on the input. ▪ An input that results in the shortest execution time is called the best-case input and an input that results in the longest execution time is called the worst-case input. ▪ Best-case and worst-case are not representative, but worst-case analysis is very useful. You can show that the algorithm will never be slower than the worst-case. ▪ An average-case analysis attempts to determine the average amount of time among all possible input of the same size. Average- case analysis is ideal, but difficult to perform, because it is hard to determine the relative probabilities and distributions of various input instances for many problems. Worst-case analysis is easier to obtain and is thus common. So, the analysis is generally conducted for the worst-case. Ignoring Multiplicative Constants ▪ The linear search algorithm requires n comparisons in the worst- case and n/2 comparisons in the average-case. Using the Big O notation, both cases require O(n) time. The multiplicative constant (1/2) can be omitted. Algorithm analysis is focused on growth rate. The multiplicative constants have no impact on growth rates. The growth rate for n/2 or 100n is the same as n, i.e., O(n) = O(n/2) = O(100n). f(n) n 100 200 n n/2 100n 100 200 50 100 10000 20000 2 2 2 f(200) / f(100) Ignoring Non-Dominating Terms ▪ Consider the algorithm for finding the maximum number in an array of n elements. ▪ If n is 2, it takes one comparison to find the maximum number. ▪ If n is 3, it takes two comparisons to find the maximum number. ▪ In general, it takes n-1 times of comparisons to find maximum number in a list of n elements. ▪ Algorithm analysis is for large input size. If the input size is small, there is no significance to estimate an algorithm’s efficiency. As n grows larger, the n part in the expression n-1 dominates the complexity. ▪ The Big O notation allows you to ignore the non-dominating part (e.g., -1 in the expression n-1) and highlight the important part (e.g., n in the expression n-1). ▪ So, the complexity of this algorithm is O(n). Useful Mathematic Summations ▪ Useful formulas for computing the program complexity 12 12 22....2222 1 1 .... 2 )1( )1(....321 1 )1(3210 1 )1(3210 − − =++++++ −