CS502 Assignment 1 Solution Fall 2017

CS502 Assignment 1 Solution Fall 2017

 

Question # 1:

Let us use the same logic which the book uses i.e. any array access is considered a single operation. Also, consider that the array A has n elements.

Search(A, Key)

i  ← 1                                                        .. 1 initialization takes constant time

while (A[i] ≠ key) and (i ≤ length[A])        .. 1 array access taking constant time

i ← i + 1                                                    .. 1 operation taking constant time

if ( i ≤ length[A]) return true                     .. 1 operation of comparison

else return false

cs502 assignment 1 solution

 

 

 

 

Best case happens when the key is found in first iteration i.e. at first position. In that case, the loop executes a single time only giving:
Best case big-Oh O(1) i.e. only one iteration

Worst case happens when the key is not found at all. This means that the loop executes for n times.
Worst case big-Oh O(n) i.e. n iterations

Average case happens when the key is not found in the center of the array i.e. n/2 iteration.
Average case big-Oh O(n/2) i.e. n/2 iterations

 

Question # 2:

Yellow boxes are always the pivots. Red is the position of the swap. The final row in each recursion always shows where the pivot comes to after the partition algorithm has executed.

 

cs502 assignment 1 solution

 

cs502 assignment 1 solution

 

cs502 assignment 1 solution

 

 

algo assignment, algorithm assignment, assignment solution cs502, cs502, cs502 assignment, cs502 assignment 1, cs502 assignment 1 solution, cs502 assignment 1 solution 2017, cs502 assignment 2017, cs502 assignment solution 2017, algorithm assignment solution, fundamentals of algorithms assignment 1 solution.

Leave a Reply

Your email address will not be published. Required fields are marked *

%d bloggers like this: