Assalam-o-Alaikum Frndz!
today paper CS502 by Safeena Ali
CS502 (Fundamental Of Algorithm)
By Safeena Ali
Date 16-05-2012
Q Due to left complete nature of binary tree, the heap can be stored in
• Arrays
• Structures
• Link Lis
• Stack
Q For Chain Matrix Multiplication we can not use divide and conquer approach
because,
We do not know the optimum k
We use divide and conquer for sorting only
We can easily perform it in linear time
Size of data is not given
Q word Algorithm comes from the name of the muslim author
Abu Ja'far Mohammad ibn Musa al-Khowarizmi.
Uzbikistan
Khawarizmi
India
Q What is the total time to heapify?
• O(log n)
• O(n log n)
• O(n2 logn)
• O(log2n)
Q 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
Q= A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:
heap
binary tree
binary search tree
array
Q= How many elements do we eliminate in each time for the Analysis of Selection
algorithm?
n / 2 elements
(n / 2) + n elements
n / 4 elements
2 n elements
Q= We do sorting to,
keep elements in random positions
keep the algorithm run in linear order
keep the algorithm run in (log n) order
keep elements in increasing or decreasing order
Q= Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
Select correct option:
left-complete
right-complete
tree nodes
tree leaves
Q= Divide-and-conquer as breaking the problem into a small number of
Select correct option:
pivot
Sieve
smaller sub problems
Selection
Q= For the sieve technique we solve the problem,
Select correct option:
recursively
mathematically
precisely
accurately
Q= 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
Q= Random access machine or RAM is a/an
Q= A symptotic notation is used to calculate
Q= If an algorithm has a complexity of 5n + log2 ( log2 n ) + 10 for some model of computation (some set of assumptions) and some complexity measures (such as number of comparison operations) we could say that it has complexity
Q= Matrix – Chain – Order is __________ than the exponential time method of enumerating all possible parenthesizations and checking each one
Q= find maximum and minimum heap of height h . Mark 2
Q= a1,a2 a3 in ki values di hoi thi un ka combination banana tha mark 3
Q= knaspack 0/1 problem by using dynamic mark 5
Q= write running time of edit distances Algorithm mark 3
Q=average case quick sort ka sawal tha 2 mark ka
Q= ak table tha jis ko fill krna tha 1 iteration k bad as main kaya changing hon gi
--
Virtual University of Pakistan*** IT n CS Blog
================================
http://www.geniusweb.tk http://itncs.tk You received this message because you are subscribed to the Google
Groups "vulms" group.
To post to this group, send email to vulmsit@googlegroups.com
To unsubscribe from this group, send email to
vulmsit+unsubscribe@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/vulmsit?hl=en?hl=en
