Transform & Conquer

Which of these is not a variation of Transform and Conquer? (Tick all that applies)

• Instance simplification

• Problem transformation

• Instance reduction

• Representation change

Which of these is an example of instance simplification approach?

• Presorting

• Heap sort

• Heapify

• Least common mutiple

What is the running time of this algorithm?

•  $\theta\left(n\ \lg\ n\right)$  

•  $\theta\left(\lg\ n\right)$  

•  $\theta\left(n^2\right)$  

•  $\theta\left(n\right)$  

Which of these is a heap?

• 
• 
• 
• 

Which is correct about heapsort

• its best, average and worse case is (n lg n)

• Its not in place

• Can be constructed with bottom-up or top-down approach

• heapify is to serve the 'parental dominance' condition