Algorithm $A$ is a comparison$-$based sorting algorithm with best$-$case running time $(n),$ average$-$

case running time $(n^{\frac{3}{2}}),$ and worst$-$case running time $(n^2).$ Which of the following is FALSE

regarding the decision tree of algorithm $A?$

A$.$ Some branch has height $(n).$

B$.$ Some branch has height $(n^2).$

C$.$ Most branches have height $(\frac{n^3}{2}).$

D$.$ Some branch has a repeated comparison.

E$.$ There are at least $n!$ leaves.

A$.2,4$

B$.2$

C$.1$

D$.2,3$

E$.2,3,4$ Which of the following is NOT a common property of quicksort and quickselect?

A$.$ Making random choices makes both algorithms more robust.

B$.$ Both algorithms can be used to find the $r-$th statistic of the input.

C$.$ The recurrence relation representing the runtime is the same.

D$.$ The average runtime is asymptotically smaller than the worst case runtime.

E$.$ Both algorithms partition the input with respect to a pivot.

Consider an algorithm takes as input a digraph $G=(V,E)$ where $|E|=m$ and $|V|=n.$ The

algorithm finds the in$-$degree of all nodes and then removes the node with the smallest in$-$degree.

After removing that node, the remaining node with the smallest in$-$degree is removed, and so on until

all nodes have been removed. All nodes are listed in the order of removal. If the digraph is represented

using adjacency lists, and you can cache interim results, what is the most precise characterisation of

the running time of the algorithm?You evaluate a sorting algorithm by measuring its running time on a few inputs of increasing sizes

and the results show that, on these particular inputs, the runtime was $(n^2).$ Which algorithm is NOT

consistent with your observations?

A$.$ Selection sort

B$.$ None $($they are all consistent$)$

C$.$ Insertion sort

D$.$ Quicksort

E$.$ Mergesort

Which of the following inputs can be used to show that selection sort is not stable? Assume that

findmax chooses the rightmost element in case of a tie.

Which recurrence represents the total number of function calls that occur upon calling $g(n)?$

A$.T(n)=T(n-1)+T(n-2)+$cdots$+T(1)$

B$.T(n)=2(T(n-1)+T(n-2)+$cdots$+T(1))$

C$.T(n)=T(n-2)+T(n-4)+$cdots$+T(1)$

D$.T(n)=n+T(n-1)+T(n-2)+$cdots$+T(1)$

E$.T(n)$ is not well defined because there is no base case

What is the closed form of the recurrence $T(n)=T(n-1)+T(n-2)+$cdots$+T(1)$;$T(1)=1?$