top of page
Search

# Data Structure and algorithm analysis I sample work

In this blog, we will be solving some problems related to data structure and algorithm analysis. Below are the questions

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 4:

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.

Contact Codersarts for any such project/assignment help
Codersarts is a top-rated website for students which is looking for online Programming Assignment Help, Homework Help, Coursework Help in C, C++, Java, Python, Database, Data structure, Algorithms, Final year project, Android, Web, C sharp, ASP NET to students at all levels whether it is school, college and university level Coursework Help or Real-time project. Hire us and Get your projects done by a computer science expert.