Fundamental-Algorithms Assignment 2-Analysis & Comparison of Bottom-Up and Top-Down Build Heap ApproachesSolved

Implementation

You are required to implement c​orrectly and e​fficiently two methods for building a heap, namely the b​ottom­up and the t​op­down strategies. Additionally, you have to implement heapsort.

You may find any necessary information and pseudo­code in your course notes, or in the book1:

● ● ●

Tresholds

Treshold Requirements

5. 5  Implement and exemplify correctness of bottom­up build heap procedure
6. 6  Implement and exemplify correctness of heapsort
7. 7  Implement and exemplify correctness of top­down build heap procedure

9. 9  Comparative analysis of the two build heap methods, in the average case
10. 10  Interpretations, advantages/disadvantages of each approach

Evaluation
! Before you start to work on the algorithms evaluation code, make sure you have a correct

algorithm! You will have to prove your algorithm(s) work on a small­sized input.

1 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. ​Introduction to Algorithms

Bottom­up:​section 6.3 (Building a heap)
Heapsort:​chapter 6.4 (The heapsort algorithm)
T o p ­ d o w n :​s e c t i o n 6 . 5 ( P r i o r i t y q u e u e s ) a n d p r o b l e m 6 ­ 1 ( B u i l d i n g a h e a p u s i n g i n s e r t i o n )

1. You are required to compare the two build heap procedures in the average c​ase. Remember that for the a​verage case you have to repeat the measurements m times (m=5) and report their average; also for the a​verage case, make sure you always use the s​ame input sequence for the two methods – to make the comparison fair.
2. This is how the analysis should be performed:
   ­ vary the dimension of the input array (n​)​between [100…10000], with an increment of maximum 500 (we suggest 100).
   ­ for each dimension, generate the appropriate input sequence for the method; run the method, counting the operations (assignments and comparisons, may be counted together for this assignment).

   ! Only the assignments and comparisons performed on the input structure and its corresponding auxiliary variables matter.

3. Generate a chart which compares the two methods under the total number of operations, in the a​verage case. If one of the curves cannot be visualized correctly because the other has a larger growth rate, place that curve on a separate chart as well. Name your chart and the curves on it appropriately.
4. Interpret the chart and write your observations in the header (block comments) section at the beginning of your main .cpp file.
5. Only the correctness of heapsort is demonstrated, the analysis is not necessary.
6. (e​xtra – for extra credit)​Try to compare the two build heap procedures in the w​orst case. What do you observe?