Part A: Short Answer Questions $(30$ Marks$)$

$1.$ Definitions $(10$ Marks$)$

$$ Define the following terms: $(2$ marks each$)$

$$ Growth of Functions

$$ Asymptotic Notation

$$ Divide$-$and$-$Conquer

$$ Dynamic Programming

$$ Balanced Search Trees

$2.$ Conceptual Questions $(20$ Marks$)$

$$ Explain how the Divide$-$and$-$Conquer strategy is applied in Merge Sort. $(4$ Marks$)$

$$ Describe the main idea behind solving recurrences using the Recursion$-$tree method. Provide a brief example. $(4$ Marks$)$

$$ What is the significance of the Master method in solving recurrences? $(4$ Marks$)$

$$ Compare and contrast Heapsort and Quicksort in terms of their algorithmic approach and efficiency. $(4$ Marks$)$

$$ Explain the concept of "lower bound" in the context of sorting algorithms. $(4$ Marks$)$