$1.$ Multiple choice $($Select all that apply$).$ Total for Question $1$: $10$

$($a$)(2$ points$)$ Select the lower bound for the function f $($n$)=4$n$3+2$n$2+$ n$.$

$($n$)$

$($n$3)$

$$ O$($n$3)$

$($n$)$

$($n$2)$

$($b$)(2$ points$)$ Select the functions that grow asymptotically slower than $8$log$4$ n$.$

$$ n$4$

$5$

$$ n$1$

$3$

$$ n$5$

$8$

$$ n$$n

$2$n

$($c$)(2$ points$)$ Which of the following sorting algorithms are comparison$-$based?

$$ radix sort

$$ heap sort

$$ bucket sort

$$ counting sort

$$ merge sort

$($d$)(2$ points$)$ Which of the following are properties of Dynamic Programming?

$$ top$-$down

$$ brute force

$$ ordered subproblems

$$ recomputation

$$ DAG

$($e$)(2$ points$)$ For which of the following will a greedy algorithm always give an optimal

solution?

$$ Huffman

$$ matrix chain multiplication

$$ Fibonacci

$$ minimum spanning tree