Problem $1.(20$ points$)$ Consider the following array which needs to be sorted in ascending order

using Quicksort:

$[4571623]$

$($a$)(10$ points$)$ Explain which pairs of elements are swapped during the $1$st partitioning. Also,

show the content of the array at the end of the $1$st partitioning.

$($b$)(10$ points$)$ Explain which pairs of elements are swapped during the $2$nd partitioning. Also,

show the content of the array at the end of the $2$nd partitioning.

Problem $2.(20$ points$)$ Consider the following sorted array:

$[0123456]$

$($a$)(10$ points$)$ List the elements of the array that the binary search algorithm accesses when it

searches for $2.$ Briefly justify your answer.

$($b$)(10$ points$)$ List the elements of the array that the binary search algorithm accesses when it

searches for $7.$ Briefly justify your answer.

Problem $3.(20$ points$)$ Determine whether or not each of the following statement is true. Also,

justify your answer rigorously using the Big$-$O$,$ Big$-$Omega, and$/$or Big$-$Theta definitions.

$($a$)(10$ points$)2$n $4$ is O$($n

$2$

$).$

$($b$)(10$ points$)42$n

$2$

is $\backslash$Theta $($n

$2$

$).$

$1$

Problem $4.(37$ points$)$ Express the time complexity $($in Big$-$O notation$)$ of each of the following

cases assuming that the size of the input data $($i$.$e$.,$ the length of the given array$)$ is N$.$ Briefly

justify your answer. You do not need to apply the Big$-$O definition $($i$.$e$.,$ f$($n$)$ is O$($g$($n$))$ if there

exist positive constants c and n$0$ such that f$($n$)<=$ c $$ g$($n$)$ for all n $>=$ n$0)$ to justify your expression

in Big$-$O notation.

$($a$)(10$ points$)$ Best case of binary search

$($b$)(10$ points$)$ Worst case of selection sort

$($c$)(8$ points$)$ Best case of insertion sort

$($c$)(5$ points$)$ Worst case of insertion sort

$($d$)(4$ points$)$ Worst case of Quicksort $($assume that, when a portion of the array is partitioned,

the first element in that portion is chosen as the pivot$)$