Assignment 1 (Textbook: Thomas H. Cormen, Introduction to algorithms, 3rf Edition, ISBN- 978-0-262-03384- 8, ISBN-978-0-262-53305-8) 1 - Give a real-world example that requires sorting? 2- Other than speed, what other measures of efficiency might one use in a real-world setting? 3- What is the smallest value of n such that an algorithm whose running time is 100n runs faster than an algorithm whose running time is 2" on the same machine? 4- Rewrite the INSERTION-SORT procedure to sort into decreasing order instead of increasing order. 5- Using Figure 2.4 in the textbook (page 35) as a model, illustrate the operation of merge sort on the array A = (3, 41, 52, 26, 38, 57, 9, 49). 6- Express the function n / 1000 - 100 n - 100n + 3 in O-notation. 7- Consider a modification of the rod-cutting problem (BOTTOM-UP-CUT-ROD(p, n), page 366 in textbook) in which, in addition to a price pi for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem. 8- Let X = (spanking) and Y = (amputation). Determine an LCS of X and Y. Your solution must include the table that shows the length of LCS between each prefix of X and each prefix of Y (similar to the table shown in Figure 15.8 in page 395). 9- Given a chain of 5 matrices A1, A2, A3, A4, and As with dimensions po = 10, p. = 3, p2 = 12, p3 = 5, p4 = 50, ps = 6, where the matrix A has dimension pil xpi. Find an optimal parenthesization of the product of the given matrix-chain. Your solution must include tables m and s (see Figure 15.5 in page 376) where table m stores minimum number of scalar multiplications needed to compute the matrix Ai.j and table s stores values of k such that an optimal parenthesization of A Ai+l...Aj splits the product between Ak and Ak+I