CS 502 Fundamental of Algorithms Assignment # 02 Solution Fall 2012

CS 502 Fundamental of Algorithms

Assignment # 02

Fall 2012

Total Marks = 20

CS 502 Fundamental of Algorithms

Assignment # 02

Fall 2012

Total Marks = 20

Read more: CS502 - Fundamentals of Algorithms Assignment # 2 discussion and solution Due date is November 27, 2012. - Virtual University of Pakistan http://vustudents.ning.com/group/cs502fundamentalsofalgorithms/forum/topics/cs502-fundamentals-of-algorithms-assignment-2-discussion-and#ixzz2DOpOfZ5B

 SOLUTION:

Outline of Procedure Heapify

Heapify picks the largest child key and compare it to the parent key. If parent key is larger than heapify quits, otherwise it swaps the parent key with the largest child key. So that the parent is now becomes larger than its children.
It is important to note that swap may destroy the heap property of the subtree rooted at the largest child node. If this is the case, Heapify calls itself again using largest child node as the new root.

Heapify (A, i)

1.     l ← left [i]

2.     r ← right [i]

3.     if l ≤ heap-size [A] and A[l] > A[i]

4.         then largest ← l

5.         else largest ← i

6.     if r ≤ heap-size [A] and A[i] > A[largest]

7.         then largest ← r

8.     if largest  ≠ i

9.         then exchange A[i] ↔ A[largest]

10.         Heapify (A, largest)

 

Analysis

If we put a value at root that is less than every value in the left and right subtree, then 'Heapify' will be called recursively until leaf is reached. To make recursive calls traverse the longest path to a leaf, choose value that make 'Heapify' always recurse on the left child. It follows the left branch when left child is greater than or equal to the right child, so putting 0 at the root and 1 at all other nodes, for example, will accomplished this task. With such values 'Heapify' will called h times, where h is the heap height so its running time will beθ(h) (since each call does (1) work), which is (lgn). Since we have a case in which Heapify's running time (lg n), its worst-case running time is Ω(lgn).

 

Example of Heapify
 

Suppose we have a complete binary tree somewhere whose subtrees are heaps. In the following complete binary tree, the subtrees of 6 are heaps:

The Heapify procedure alters the heap so that the tree rooted at 6's position is a heap. Here's how it works. First, we look at the root of our tree and its two children.

We then determine which of the three nodes is the greatest. If it is the root, we are done, because we have a heap. If not, we exchange the appropriate child with the root, and continue recursively down the tree. In this case, we exchange 6 and 8, and continue.

Now, 7 is greater than 6, so we exchange them.

We are at the bottom of the tree, and can't continue, so we terminate.

cs502 quize 1st-12-11-2012

MC100400431 : Zaheer Abbas



Quiz Start Time: 10:05 PM    
Time Left     88
sec(s)    
Question # 1 of 10 ( Start time: 10:05:34 PM )     Total Marks: 1
The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required?
Select correct option:
    16
    10
    32
    31

MC100400431 : Zaheer Abbas



Quiz Start Time: 10:05 PM    
Time Left     80
sec(s)    
Question # 2 of 10 ( Start time: 10:06:00 PM )     Total Marks: 1
In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis,
Select correct option:
    linear
    arithmetic
    geometric
    exponent

MC100400431 : Zaheer Abbas



Quiz Start Time: 10:05 PM    
Time Left     89
sec(s)    
Question # 3 of 10 ( Start time: 10:06:16 PM )     Total Marks: 1
One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.
Select correct option:
    pointers
    constants
    variables
    functions

MC100400431 : Zaheer Abbas



Quiz Start Time: 10:05 PM    
Time Left     47
sec(s)    
Question # 4 of 10 ( Start time: 10:06:58 PM )     Total Marks: 1
Analysis of Selection algorithm ends up with,
Select correct option:
    T(n)
    T(1 / 1 + n)
    T(n / 2)
    T((n / 2) + n)

MC100400431 : Zaheer Abbas



Quiz Start Time: 10:05 PM    
Time Left     80
sec(s)    
Question # 5 of 10 ( Start time: 10:07:47 PM )     Total Marks: 1
The number of nodes in a complete binary tree of height h is
Select correct option:
    2^(h+1) – 1
    2 * (h+1) – 1
    2 * (h+1)
    ((h+1) ^ 2) – 1

MC100400431 : Zaheer Abbas



Quiz Start Time: 10:05 PM    
Time Left     75
sec(s)    
Question # 6 of 10 ( Start time: 10:08:01 PM )     Total Marks: 1
For the heap sort we store the tree nodes in
Select correct option:
    level-order traversal
    in-order traversal
    pre-order traversal
    post-order traversal

MC100400431 : Zaheer Abbas



Quiz Start Time: 10:05 PM    
Time Left     76
sec(s)    
Question # 7 of 10 ( Start time: 10:08:25 PM )     Total Marks: 1
The analysis of Selection algorithm shows the total running time is indeed ________in n,
Select correct option:
    arithmetic
    geometric
    linear
    orthogonal

MC100400431 : Zaheer Abbas



Quiz Start Time: 10:05 PM    
Time Left     89
sec(s)    
Question # 8 of 10 ( Start time: 10:09:53 PM )     Total Marks: 1
The sieve technique works in ___________ as follows
Select correct option:
    phases
    numbers
    integers
    routines

MC100400431 : Zaheer Abbas



Quiz Start Time: 10:05 PM    
Time Left     89
sec(s)    
Question # 9 of 10 ( Start time: 10:10:36 PM )     Total Marks: 1
In Sieve Technique we do not know which item is of interest
Select correct option:
    True
    False

MC100400431 : Zaheer Abbas



Quiz Start Time: 10:05 PM    
Time Left     87
sec(s)    
Question # 10 of 10 ( Start time: 10:10:55 PM )     Total Marks: 1
The sieve technique is a special case, where the number of sub problems is just
Select correct option:
    5
    many
    1
    few

MC080200323 : Muhammad Zahid



Quiz Start Time: 10:11 PM    
Time Left     89
sec(s)    
Question # 1 of 10 ( Start time: 10:11:54 PM )     Total Marks: 1
In which order we can sort?
Select correct option:
    increasing order only
    decreasing order only
    increasing order or decreasing order
    both at the same time

MC080200323 : Muhammad Zahid



Quiz Start Time: 10:11 PM    
Time Left     89
sec(s)    
Question # 2 of 10 ( Start time: 10:13:07 PM )     Total Marks: 1
How much time merge sort takes for an array of numbers?
Select correct option:
    T(n^2)
    T(n)
    T( log n)
    T(n log n)

MC080200323 : Muhammad Zahid



Quiz Start Time: 10:11 PM    
Time Left     89
sec(s)    
Question # 3 of 10 ( Start time: 10:14:35 PM )     Total Marks: 1
For the Sieve Technique we take time
Select correct option:
    T(nk)
    T(n / 3)
    n^2
    n/3

MC080200323 : Muhammad Zahid



Quiz Start Time: 10:11 PM    
Time Left     89
sec(s)    
Question # 4 of 10 ( Start time: 10:14:52 PM )     Total Marks: 1
Divide-and-conquer as breaking the problem into a small number of
Select correct option:
    pivot
    Sieve
    smaller sub problems
    Selection

MC080200323 : Muhammad Zahid



Quiz Start Time: 10:11 PM    
Time Left     89
sec(s)    
Question # 5 of 10 ( Start time: 10:15:08 PM )     Total Marks: 1
How many elements do we eliminate in each time for the Analysis of Selection algorithm?
Select correct option:
    n / 2 elements
    (n / 2) + n elements
    n / 4 elements
    2 n elements

MC080200323 : Muhammad Zahid



Quiz Start Time: 10:11 PM    
Time Left     88
sec(s)    
Question # 6 of 10 ( Start time: 10:16:07 PM )     Total Marks: 1
Slow sorting algorithms run in,
Select correct option:
    T(n^2)
    T(n)
    T( log n)
    T(n log n)

MC080200323 : Muhammad Zahid



Quiz Start Time: 10:11 PM    
Time Left     89
sec(s)    
Question # 7 of 10 ( Start time: 10:17:10 PM )     Total Marks: 1
Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________
Select correct option:
    n items
    phases
    pointers
    constant

MC080200323 : Muhammad Zahid



Quiz Start Time: 10:11 PM    
Time Left     90
sec(s)    
Question # 8 of 10 ( Start time: 10:17:28 PM )     Total Marks: 1
The number of nodes in a complete binary tree of height h is
Select correct option:
    2^(h+1) – 1
    2 * (h+1) – 1
    2 * (h+1)
    ((h+1) ^ 2) – 1

MC080200323 : Muhammad Zahid



Quiz Start Time: 10:11 PM    
Time Left     89
sec(s)    
Question # 9 of 10 ( Start time: 10:17:46 PM )     Total Marks: 1
The sieve technique works in ___________ as follows
Select correct option:
    phases
    numbers
    integers
    routines

MC080200323 : Muhammad Zahid



Quiz Start Time: 10:11 PM    
Time Left     89
sec(s)    
Question # 10 of 10 ( Start time: 10:18:06 PM )     Total Marks: 1
In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
Select correct option:
    T(n)
    T(n / 2)
    log n
    n / 2 + n / 4