PART $1$: ALL. QUESTIONS ARE REQUIRED $[10$ Marks$]$

Question $1$: $(10$ marks$)$

Mark the fothowing statemerts we trie or false

Linear search in an array $)$ invotves $($log n$)$ comparisons.

To represent hierarchical relationship between family members, a graph data structure is suitable.

The recurrence relation that arises in relation with the complexity of binary search is $T(n)-=T(\frac{n}{2})+k.$ Where $k$ is constant

Minimal spanning tree algorithm belongs to the brute$-$force paradigm

KMP soarching algorthm is faster than the Linear search

Searching in a list for an unavailable value will lead to average case performance.

The sequence $20,15,18,7,9,5,12,3,6,2$ is a max$-$heap.

$O(n),O(nlogn),O(n^2),O(n^{2}logn)$ is the right order from best to worst complexity.

A graph is a collection of nodes, called vertices and line segments called edges that connect pair of nodes.

Consider a sorted array of n numbers. the best known algorithm to find a pair $\text{'}a\text{'}$ and $\text{'}b\text{'}$ such that $|a-b|=k,k$ being a positive integer is of order $O(n).$

PART $2$: ALL QUESTIONS ARE REQUIRED $[25$ Marks$]$