CSC 155 Written Assignment. The Analysis of Algorithms. Comming up with a good algorithm requires a bit more than just being clever. It is a science and to appreciate the nature of algorithms you have to learn to see them from a scientific perspective, independent of the "code" of the program or even the programming language used. This is what the mathematical analysis of algorithms will teach you. To do the problems here, please follow the format of the following example. Let us analyse the complexity of bubblesort: void bubblesort(int A[], int n) { int i, j, k; for(i=0;iA[j+1]) { k = A[j]; A[j] = A[j+1]; A[j+1] = k; } } Since we are interested in the worst case complexity, we should assume that the "if" clause always results in a swapping of values. Since the time it takes to compute the "if" and the swap is independent of n (size of array), we can assign a constant C to represent this time. The inner loop executes n-1 times thus the measure of the inner loop is (n-1)*C But this is executed n-1 times by the outer loop. Thus the total complexity measure is (n-1)*(n-1)*C or C(n*n - 2*n + 1) This measure is inside bigO(n*n) and Omega(n*n) since we can show (after some applications of L'Hopital's rule) that limit of C(n*n - 2*n + 1) / n*n n->inf is a non-zero constant (1). When an algorithm is both upper and lower bound by the same complexity class, We say that it's in Theta(n*n). Caution: please don't confuse "upper and lower bound" with "worst and best" case. These are independent concepts. ---- A more challenging case is when bubblesort is slightly optimized so that the inner loop becomes for(j=0; jA[i]) ax=A[i]; return ax; } Mathematically analyze the (worst-case) time complexity of the algorithm with respect to n. Also determine its upper and lower bound complexity classes (big-O and Omega) along the scale above. 3. Devise an algorithm that finds the SECOND smallest number in an arbitrary array (it may not be as easy as you think). You can write the code out in C, or sufficiently detailed pseudocode. (if you're not sure what "sufficiently detailed" means, write it in C and make sure it compiles). Analyze its complexity as above. 4. Another way to sort a list is to first find the smallest element, swap it into A[0], then find the second smallest element, swap it into A[1], etc... The last step is to find the n-1st smallest element and swap it into A[n-2] (the last element will naturally fall into the right place.) Write out this algorithm in full detail, and analyse its time complexity as above. 5. Speculate whether there are any algorithms that can sort an array in bigO(n) - that is, linear time. I'm not looking for a mathematical answer for this one, just some thoughtful reasoning.