Q$2(7)$

$2\mathrm{.}1\mathrm{.}14$ Dequeue Sort: Explain how would you sort a deck of cards, with restriction that only

allowed operations are to look at the values of top two cards, to exchange the top two cards, and

move the top card to the bottom of the deck.

Q$3(5)$

$2\mathrm{.}1\mathrm{.}20$ What is the best case for shellsort? Justify your answer.

Q$4(8)$

Write a recursive method which accepts two parameters: head of a linked list and a value $k.$ Then

it prints the $k^{th}$ to the last element of a linked list.

For example, if the linked list content is $abcd$ and $k$ is $3$ it prints out $b$

Q$5(7)$

Assume that we have a bitonic array $($as explained in Assignment $1)$ with bitonic point p$.$ For

$($the point that the decreasing part begins$).$ Assume that you know the index of bitonic point in a

bitonic array of size $N.$ Explain a sorting algorithm with complexity $O(N)$ to sort a bitonic array with

size $N$ and bitonic point index $p$ in an ascending order. $($hint: merging can help here$).$

Q$6(6)$

a$)$ Explain why Merge sort is the most suited for very large inputs $($that do not fit inside memory$)$

while quick sort is not as suited. Note that these two sorting techniques have comparable time

complexities.

b$)$ Can Merge sort be performed in place? Explain your understanding.