cs502 Assignment No. 02 Fall 2021 Solution file CS502- Design and Analysis of Algorithms   
Assignment No. 02
 Fall 2021
 CS502- Design and Analysis of Algorithms
 

Question no 1:

Following is the tree diagram of a max heap. You are required to delete node 50 from the given max heap tree, apply heapify procedure and then show only the final max heap tree. No need to show the intermediate steps.

 


 


 

Solution:

 

 

 


 

 

 

 

 

 


 

 

 

 

 

 

 

 

 


               

                Question No 2:

Following is the tree diagram of a min-heap. Insert node 2 in the given min-heap tree, apply the heapify procedure, and show only the final min-heap tree. No need to show the intermediate steps.


 


                Solution:

 

 

 

 



 

 

 

 

 

 

 

 

 

 

 

 


Question no 3:

The following is the array representation of six elements at its initial stage. You are required to sort this array using the Quicksort technique.

p

 

 

 

 

r

8

3

5

9

6

2

q

s

 

 

 

 

Solution:

Given Array

p                                                                                                                                      r

8

3

5

9

6

2

  q                                                                                                                                     s

Iteration 1:

       p                                                                                                                                r

8

3

5

9

6

2

i         j                                                                                                                                 x

 

 

        p                                                                                                                                   r

8

3

5

9

6

2

i                             j                                                                                                                 x

        p                                                                                                                                   r

8

3

5

9

6

2

i                                                         j                                                                                     x

        p                                                                                                                                   r

8

3

5

9

6

2

i                                                                                   j                                                           x

        p                                                                                                                                   r

8

3

5

9

6

2

i                                                                                                           j                                   x

        p                                                                                                                                   r

8

3

5

9

6

2

i                                                                                                                                    jx

 

        p                                                                                                                                   r

2

3

5

9

6

8

      i 

 

Iteration 2:

        p                                                                                                     r

3

5

9

6

8

i         j                                                                                                     x

        p                                                                                                     r

3

5

9

6

8

    i                         j                                                                                  x

        p                                                                                                     r

3

5

9

6

8

                                  i                                j                                                 x

        p                                                                                                     r

3

5

9

6

8

                                        i                                             j                        x

 

        p                                                                                                     r

3

5

6

9

8

                                                                i                                            jx

 

        p                                                                                                     r

3

5

6

8

9

                                                                                         i                   

 

Iteration 3:

p                                                               r

3

5

6

i     j                                                           x

p                                                               r

3

5

6

       i                             j                            x

p                                                               r

3

5

6

                                 i                       jx

p                                                               r

3

5

6

                                                            i  

 

Iteration 4:

p                                           r

3

5

i      j                                       x

p                                           r

3

5

       i                          j  x

 

 

p                                           r

3

5

                                       i      

Final sorted array using quick sort algorithm

2

3

5

6

8

9

 

Question no 4:

Below is a code snippet that calculates prefix averages by keeping a running sum.  It takes the average of all "previous" values. It's typically used to calculate the prefix average for each position in an array. In financial applications, the prefix average is extremely useful. You are required to find the time complexity with respect to the worst case.

 

pAverages(Z,n)
Arr = new array of n integers
b=0
for j=0 to n-1 do
         b=b+Z[j]
         Arr[j]=b/(j+1)
return Ar

Solution:

 

Cost

Time complexity

D1

1

D2

1

D3

1

D4

N

D5

n-1

D6

n-1

D7

1

 

Time complexity in worst case O(n)





Thanks For visiting the site:

For any problem-related solution visit site regularly.

bookmark the site, please.