Question

Algorithm

Humble Numbers

Problem 4-1 (Humble Numbers) 10 points A number k > 1 is called humble if the only prime factors of k are 3 and 5. Consider the task of on input n, outputting the n smallest humble numbers and the following algorithm to do it: HuMBLE(n) count = 0. pret,Output = 0 HEAP.INSERT (3) HEAP.INSERT (5) while (count < n) cur - HEAP. EXTRACTMIN if cur prevOutput then output cur HEAP,INSERT(3*cur) HEAP.İNSERT(5*cur) count -count+1 preu,Output = cur (a) (4 points) Argue that the algorithm above (1) outputs numbers in increasing order, (2) does not output any number twice, (3) only outputs humble numbers, and (4) outputs all of the first n humble numbers. (b) (2 points) Derive an exact (i.e.. no O-notation) bound on the number of times HEAP, INSERT is called (c) (2 points) Bound exactly the number of times HEAP.EXTRACTMIN İs called. (Hint: Use (b).) (d) (2 points) Use the answers to (b) and (c) above to argue that HUMBLE runs in O(n logn) time. Assume that arithmetic can be performed in O(1) time

Answer 1

(a) Let us argue about (1), the only value program output is the value of cur, which gets its value from the step cur = HEAP.EXTRACTMIN, this means minimum number present in the heap is extracted. We can also notice that after extracting the minimum number from the heap, multiples of the number are inserted into the heap, which means no number smaller than the cur is inserted into the heap, which means numbers that will be extracted in the future will be greater than the cur. Hence, the algorithm outputs numbers in increasing order.

(2) the algorithm outputs the number only if cur != prevOutput. as we know from (1) that algorithm output number in increasing order, which means two equal numbers can occur only one after another. if so happens, cur!=prevOutput will prevent it from giving output. Hence, the algorithm will never output the same number twice.

(3) algorithm only output numbers extracted from the heap. in which, only multiples of 3 and 5 are inserted. So, heap contains only humble numbers. Hence, the output will also be humble numbers

(4) Algorithm inserts initially 3 and 5. After that, it inserts the next possible number whose prime factors are 3 and 5. every combination of multiplication of 3 and 5 are covered in the heap. Moreover, it outputs numbers in increasing order without repeating as proved above. Moreover, the loop is conditioned to run until n humble numbers are outputted. So, it will output all the first n humble numbers.

(b) Initially, HEAP.INSERT in called 2 times and after that, it is called for every increment in the value of count until it reaches n. So, total calls of HEAP.INSERT = 2 + n*2 = 2(n+1)

(c) We can observe from the algorithm, for every 2 HEAP.INSERT operation performed, at least 1 HEAP.EXTRACTMIN is called, except for the first 2 inserts. So, a minimum of N HEAP.INSERT will be called.

(d) A HEAP.EXTRACTMIN takes constant time while a HEAP.INSERT takes O(logn) time. from (b) and (c), total time taken by algo will be = n*1 + 2(n+1)*O(logn) = O(nlogn)