CS 502 Fundamental of Algorithms Assignment # 01 Spring 2012

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, 2012

Upload Instructions

Please view the assignment submission process document provided to you by the

Virtual University.

Rules for Marking

Please note that your assignment will not be graded if:

• It is submitted after due date

• The file you uploaded does not open

• The file you uploaded is copied from someone else or from internet

• It is in some format other than .doc

Note: Material that is an exact copy from handouts or internet would be graded

Zero marks. Your solution should consist of the material found through different sources and written in your own words.

Assignment 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 functions

O(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 ≥ n₀ and m ≥ m₀}.

Give corresponding definitions for Ω(g(n, m)) and Θ(g(n, m)).