Assignment # $3$

Due Oct ${29}^{th},2024$ Solve it quick!!!!!!!!!!!!!

Q$1[10$ pts$].$ Implement and test a JAVA function that converts max heap into min heap in a linear time.

Q$2[5$ pts$].$

Explain the concept of the lower bound in sorting algorithms.

Why does the decision tree model help to explain the lower bound of comparison$-$based sorting algorithms?

Q$3[5$ pts$].$ Counting Sort:

For an array of $1,000,000$ elements with a maximum value of $100,000,000,$ will Counting Sort be efficient? Explain your answer.

What modification should be applied to the algorithm of Counting Sort explained in class to sort an array of integers where negative numbers are also present.

Q$4[10$ pts$].$ Write the algorithm then the JAVA$/$python code for Radix sort

Note:

Your function$/$algorithm should be well$-$structured and well$-$documented.

Indicate the expected time and space complexity of your function$/$algorithm$.$

You should submit your own code. i$.$e$.$ you are not allowed to copy from the internet, any other person or references.