1. Implement the sorting algorithms for integers including selection sort, insertion sort, quick sort, improved quick sort (bonus 10, set M = 50), merge sort with large data: (1) Test the correctness of your implementation with 20 random integers, (2) Show the real running time of the sorting algorithms with 500000 integers by a table, and (3) Compare the running time with the time complexity for above sorting algorithms with discussion. Outline of main method: Find the running time with 500000 integers as follows (i) randomly generate 500000 integers and save them into array A; (ii) check the current time t1; (iii) sort the integers in A using selection sort (or insertion sort, quick sort, improved quick sort, merge sort); (iv) check the current time t2; (v) running time of selection sort (or insertion sort, quick sort, merge sort) : = t2 t1; Submission: (i) Show the correctness of your implementation with 20 integers for each algorithm, (ii) A table of time complexity for the sorting algorithms, (iii) A table of real running time of the sorting algorithms, (iv) Compare and discussion. (iv) coding with python 2. Implement algorithm DivideConquerMatch Outline of implementation: (i) Use the algorithm/method DivideConquerMatch(S[p..q], P[0..m-1]), where S is the test with n symbols and P is the pattern with m symbols, to find the first match in S[p] to S[q]. (ii) Write a main method to (a) randomly generate 100000 symbols of A, C, G, T for text S and 8 symbols of A, C, G, T for pattern P, (b) call the above method to find the first match, (c) calculate the total number of matches by changing the above method. Submission: (i) Show the correctness of your implementation with the text of 100 symbols, (ii) output and running time for 100000 symbols. (iii) coding with python