Advanced algorithm design and analysis

Question 1 (30 POINTS ): Given the input string WELOVEALGORITHMS, answer the following questions: 1.A.) (15 POINTS) Using the MergeSort algorithm provided in the course slides, illustrate the operation of MergeSort to manually sort this string. Please show each step of your recursive solution clearly. 1.B.) (10 POINTS) Using the Analysis of Merge Sort algorithm approach we studied in Ch1 starting with slide 36, perform a running time analysis (? only) of executing the MergeSort algorithm. Please use your own words in the way you understood the algorithmic analysis. Use a generic n value for the input size. Hint: As the given input is a string with an arbitrary listing of characters, i.e. not necessarily in increasing or decreasing order, you should be considering average running time. 1.C) (5 POINTS) Using the size of the given input string , what will be the numeric value of the running time? Please show your work.

Merge Sort Algorithm slide

Analysis of Merge Sort Algorithm slide

Question 1 (30 POINTS): Given the input string "WELOVEALGORITHMS", answer the following questions 1.A.) (15 POINTS) Using the MergeSort algorithm provided in the course slides, illustrate the operation of MergeSort to manually sort this string. Please show each step of your recursive solution clearly 1.B.) (10 POINTS) Using the Analysis of Merge Sort algorithm approach we studied in Chl starting with slide 36, perform a running time analysis (O only) of executing the MergeSort algorithm Please use your own words in the way you understood the algorithmic analysis. Use a h" value for the input size Hint: As the given input is a string with an arbitrary listing of characters, i.e. not necessarily in increasing or decreasing order, you should be considering average running time 1.C) (5 POINTS) Using the size of the given input string , what will be the numeric value of the running time? Please show your work. Question 1 (30 POINTS): Given the input string "WELOVEALGORITHMS", answer the following questions 1.A.) (15 POINTS) Using the MergeSort algorithm provided in the course slides, illustrate the operation of MergeSort to manually sort this string. Please show each step of your recursive solution clearly 1.B.) (10 POINTS) Using the Analysis of Merge Sort algorithm approach we studied in Chl starting with slide 36, perform a running time analysis (O only) of executing the MergeSort algorithm Please use your own words in the way you understood the algorithmic analysis. Use a h" value for the input size Hint: As the given input is a string with an arbitrary listing of characters, i.e. not necessarily in increasing or decreasing order, you should be considering average running time 1.C) (5 POINTS) Using the size of the given input string , what will be the numeric value of the running time? Please show your work