top of page
Search

# PS2 Math Solutions I Data structures and algorithm sample assignment

## Question 1:

For the given example,

If number is 123, then no of expression will be

12+3, 1+23, 1+2+3

So total number of expressions equal to length of string.

For expression evaluation time take is X unit of time, x might be 10 to the power -9

Then total time taken for evaluate all expression will be n times X= n * X

And X is constant unit of time then algorithm complexity will be O(N)

## Question 2:

Recursive multiplication will O(n) unit of time.

Generally this program will have a unit of time equal to smaller of two arguments.

For example if a and b are two arguments.

If a is less than b, then total time take equal to a - 1 or in term of n, n-1 times

If b is less than a, then total time take equal to b - 1 or in term of n, n-1 times

## Question 3:

To prove selection short correctness need to prove loop invariant is true

ALGORITHM: sort array of integers

Input: A[1..n] , Array of n unsorted integers

Output: same integers in array A now in sorted order

### pseudo code:

for i = 1 to n-1

min = i

for j = i+1 to n

if A[j] < A[min]

min = j

swap A[i] with A[min]

First we prove the correctness of the inner loop: lines 3 to 5

Loop Invariant:

Before the start of each loop, A[min] is less than or equal to A[i..j-1].

First integration of loop, j=i+1. So the array segment A[i..j-1] is really just spot A[i]. Since line 2 of the code sets min = i, we have that

min indexes the smallest element (the only element) in subarray A[i..j-1] and

hence the loop invariant is true.

bottom of page