$2\mathrm{.}24.$ On page $62$ there is a high$-$level description of the quicksort algorithm.

$($a$)$ Write down the pseudocode for quicksort.

$($b$)$ Show that its worst$-$case running time on an array of size n is $\backslash$Theta $($n $2).$

$($c$)$ Show that its expected running time satisfies the recurrence relation

T$($n$)<=$ O$($n$)+1$ n nX$1$ i$=1($T$($i$)+$ T$($n $$ i$)).$

Then, show that the solution to this recurrence is O$($n log n$).$

$2\mathrm{.}25.$ In Section $2\mathrm{.}1$ we described an algorithm that multiplies two n$-$bit binary integers x and y in time n a $,$ where a $=$ log$23.$ Call this procedure fastmultiply$($x$,$ y$).$

$($a$)$ We want to convert the decimal integer $10$n $($a $1$ followed by n zeros$)$ into binary. Here is the algorithm $($assume n is a power of $2)$:

function pwr$2$bin$($n$)$

if n $=1$: return $10102$

else: z $=???$

return fastmultiply$($z$,$ z$)$

Fill in the missing details. Then give a recurrence relation for the running time of the algorithm, and solve the recurrence.

$($b$)$ Next, we want to convert any decimal integer x with n digits $($where n is a power of $2)$ into binary. The algorithm is the following:

function dec$2$bin$($x$)$

if n $=1$:

return binary$[$x$]$

else:

split x into two decimal numbers xL$,$ xR with n$/2$ digits each

return $???$

Here binary$[]$ is a vector that contains the binary representation of all one$-$digit integers. That is$,$ binary$[0]=02,$ binary$[1]=12,$ up to binary$[9]=10012.$ Assume that a lookup in binary takes O$(1)$ time. Fill in the missing details. Once again, give a recurrence for the running time of the algorithm, and solve it$.$

$3\mathrm{.}9.$ For each node u in an undirected graph, let twodegree$[$u$]$ be the sum of the degrees of u$$s neighbors. Show how to compute the entire array of twodegree$[]$ values in linear time, given a graph in adjacency list format.

$3\mathrm{.}10.$ Rewrite the explore procedure $($Figure $3\mathrm{.}3)$ so that it is non$-$recursive $($that is$,$ explicitly use a stack$).$ The calls to previsit and postvisit should be positioned so that they have the same effect as in the recursive procedure.

$3\mathrm{.}13.$ Undirected vs$.$ directed connectivity.

$($a$)$ Prove that in any connected undirected graph G $=($V$,$ E$)$ there is a vertex v in V whose removal leaves G connected. $($Hint: Consider the DFS search tree for G$.)$

$($b$)$ Give an example of a strongly connected directed graph G $=($V$,$ E$)$ such that, for every v in V $,$ removing v from G leaves a directed graph that is not strongly connected.

$($c$)$ In an undirected graph with $2$ connected components it is always possible to make the graph connected by adding only one edge. Give an example of a directed graph with two strongly connected components such that no addition of one edge can make the graph strongly connected.