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.

Estimated Time 2.5 hour

For all parts of the question to understand maximum time is 1.25 hours and for solution maximum time is 1.25 hour. It all depends upon your sheer concentration.

Question (4*5)

Write piece of pseudo codes having the following time complexities:

What technique has been discussed in this paper for string pattern matching and its benefit? 1.5

Consider the chain matrix multiplication for 4 matrices:
A1 . A2 . A3 . A4
(5×6) (6×3) (3×7) (7×10)
Compute the cost table m in the dynamic programming algorithm for the chain matrix
multiplication

Question# 1 (10)

After analyzing the pseudo code for an algorithm following recurrence relation have been developed you are required to solve this recurrence relation using iterative method and make proper assumptions for final solution and give answer at end in asymptotic form.

Guidelines
RULES FOR CALCULATING TIME COMPLEXITY AND BIG-OH
Rule 00
Normally these formulas are very handy:
If x y = z then y z x = log