CS502 Fundamental of Algorithms Assignment No.1 Spring April 2012

[Vuhelper]

CS502 Fundamental of Algorithms Assignment No.1 Spring April 2012 Solution Soon


CS 502 Fundamental of Algorithms
Assignment # 01
Spring 2012
Total Marks = 10+10 = 20
Deadline
Your assignment must be uploaded / submitted before or on April 23, 2012Assignment Statements:
Question 1:
Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n – 1 elements of A. Write pseudo code for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n – 1 element, rather than for all n elements? Give the best-case and worst-case running times of selection sort in Θ-notation.Question 2:
We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function g(n, m), we denote by O(g(n, m)) the set of functionsO(g(n, m)) = {f(n, m): there exist positive constants c, n0, and m0 such that 0 ≤ f(n, m) ≤ cg(n, m) for all n ≥ n0 and m ≥ m0}.Give corresponding definitions for Ω(g(n, m)) and Θ(g(n, m)).