Russian Peasants Multiplication 1) Trace through the Russian Peasants Multiplication algorithm for the following products of...

Transcribed Image Text:

Russian Peasants Multiplication 1) Trace through the Russian Peasants Multiplication algorithm for the following products of integers. Show each recursive call and the final result, as done in the class notes. a) 6413 b) 6013 c) 59 * 13 LomutoPartition 2) Trace the function call LomutoPartition (A, 0, 8) with the array A [100, 213, 65, 29, 153, 199, 47, 181, 85]. Using A[0] 100 as the pivot, the algorithm should rearrange the values of array A as all numbers that are less than 100, followed by 100, followed by all numbers that are greater than 100. Your final answer should be A [65, 29, 47, 85, 153, 199, 100, 181, 213] In your trace, write down the values of L, R, s, and i, updating them each time one of them changes. For each comparison, indicate what two values are being compared and result of the comparison (swap two values or no swap). After each swap, rewrite the entire array. Russian Peasants Multiplication 1) Trace through the Russian Peasants Multiplication algorithm for the following products of integers. Show each recursive call and the final result, as done in the class notes. a) 6413 b) 6013 c) 59 * 13 LomutoPartition 2) Trace the function call LomutoPartition (A, 0, 8) with the array A [100, 213, 65, 29, 153, 199, 47, 181, 85]. Using A[0] 100 as the pivot, the algorithm should rearrange the values of array A as all numbers that are less than 100, followed by 100, followed by all numbers that are greater than 100. Your final answer should be A [65, 29, 47, 85, 153, 199, 100, 181, 213] In your trace, write down the values of L, R, s, and i, updating them each time one of them changes. For each comparison, indicate what two values are being compared and result of the comparison (swap two values or no swap). After each swap, rewrite the entire array.