ease do all exercises

Exercise 1 (10 pts) a. Find ged(314170, 14145) by applying Euclid's algorithm. b. Estimate how many times faster it will be to find ged(314170, 14145) by Euclid's algorithm compared with the algorithm based on checking consecutive integers from min{m, n} down to ged(m, n). Exercise 2 (10 pts) A peasant finds himself on a riverbank with a wolf, a goat, and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the peasant himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Solve this problem for the peasant or prove it has no solution. (Note: The peasant is a vegetarian but does not like cabbage and hence can eat neither the goat nor the cabbage to help him solve the problem. And it goes without saying that the wolf is a protected species.) Exercise 3 (10 pts) Consider the algorithm for the sorting problem that sorts an array by counting, for each of its elements, the number of smaller elements and then uses this information to put the element in its appropriate position in the sorted array: Algorithm 1 Comparison CountingSort(A[0..n - 1]) //Sorts an array by comparison counting //Input: Array A[O..n-1) of orderable values //Output: Array S[O..n-1) of A's elements sorted in nondecreasing order for i 0 ton - 1 do Count 10 end for for i 0 to n-2 do forji +1 to n - 1 do if A[i]