[Solved] CS3001301 Homework1

Problem 1.1. Is the sequence 23, 18, 14, 6, 13, 10, 1, 5, 7, 12 a max-heap? Can you call MAX-HEAPIFY (A, i) to make it a max-heap for a single i? Why?

Problem 1.2. What is the effect of calling MAX-HEAPIFY (A, i) for i > heapsize[A]/2?

Problem 1.3. The operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in O(lg n) time for an n-element max-heap.

Problem 1.4. We aim to sort a set of sequences when the set may constantly gets a small portion of new data once a while. What could be the right choice of the sorting algorithm if we have (i) insertion sort, (ii) selection sort, (iii) quicksort on hand? Explain your answer as clear as possible. That is, you should explain what algorithm is appropriate to be used and what is not for this application.

Problem 1.5. Given three sorting algorithms: (i) insertion sort, (ii) selection sort, (iii) bubble sort, can we use any of them to find the largest three elements from a sequence? How? What is the complexity? You should provide (the portion of) the codes if you want to make your conclusion clear.

Problem 1.6. Name the algorithms that can be implemented in a stable way for the given candidates: (i) insertion sort, (ii) merge sort, (iii) selection sort, (iv) bubble sort, (v) heapsort, (vi) quicksort. In your answer (Yes or No) for each of the algorithms, you should provide one or two lines of codes that is the key to make sure the stable property can (or cannot) be ensured.