CS502 - Fundamentals of Algorithms

Home Page
Q & A
Online Test
1How many elements do we eliminate in each time for the Analysis of Selection algorithm?n / 2 elements(n / 2) + n elementsn / 4 elementsn elementsD
2The analysis of Selection algorithm shows the total running time is indeed ________in narithmeticgeometriclinearorthogonalC
3The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case ofdivide-and-conquerdecrease and conquergreedy nature2-dimension MaximaA
4The sieve technique works in ___________ as followsphasesnumbersintegersroutinesA
5For the heap sort, access to nodes involves simple ________ operationsarithmeticbinaryalgebraiclogarithmicA
6We do sorting to _________keep elements in random positionskeep the algorithm run in linear orderkeep the algorithm run in (log n) orderkeep elements in increasing or decreasing orderD
7For the heap sort we store the tree nodes inlevel-order traversalin-order traversalpre-order traversalpost-order traversalA
8In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many asT(n)T(n / 2)log nn / 2 + n / 4C
9In which order we can sort?increasing order onlydecreasing order onlyincreasing order or decreasing orderboth at the same timeC
10One of the clever aspects of heaps is that they can be stored in arrays without using any _________pointersconstantsvariablesfunctionsA
11Slow sorting algorithms run inO(n^2)O(n)O( log n)O(n log n)A
12- What is the total time to heapify?O(log n)O(n log n)O(n^2 log n)O(log^2n)A
13After partitioning array in Quick sort, pivot is placed in a position such thatValues smaller than pivot are on left and larger than pivot are on rightValues larger than pivot are on left and smaller than pivot are on rightPivot is the first element of arrayPivot is the last element of arrayA
14The running time of quick sort depends heavily on the selection ofNo of inputsArrangement of elements in arraySize o elementsPivot elementD
15In Quick Sort Constants hidden in T(n log n) areLargeMediumSmallNot KnownC
16It is possible to sort without making comparisonsTrueFalseNAANA
17Merge sort is stable sort, but not an in-place algorithmTrueFalseNANAA
18In counting sort, once we know the ranks, we simply _________ numbers to their final positions in an output arrayDeleteCopyMarkarrangeB
19An in place sorting algorithm is one that uses ___ arrays for storageTwo dimensional arraysMore than one arrayNo Additional ArrayNone of the aboveC
20Continuation/counting sort is suitable to sort the elements in range 1 to kK is LargeK is not knownK may be small or largeK is smallD
21In stable sorting algorithmIf duplicate elements remain in the same relative position after sortingOne array is usedMore than one arrays are requiredDuplicating elements not handledA
22One example of in place but not stable algorithm isMerger SortQuick SortContinuation SortBubble SortB
23Quick sort is _________Stable & in placeNot stable but in placeStable but not in placeSome time stable & some times in placeC
24Which may be a stable sort?MergerInsertionBoth aboveNone of the aboveC
25Quick sort is based on divide and conquer paradigm; we divide the problem on base of pivot element andThere is explicit combine process as well to conquer the solutinNo work is needed to combine the sub-arrays, the array is already sortedMerging the subarraysNone of aboveA
26It requires more complicated data structures, Prim's algorithm for a minimum spanning tree is better than Kruskal's when the graph has a large number of verticesTrueFalseNANAA
27Which of the following sorting algorithms is stable? (i) Merge sort (ii) Quick sort (iii) Heap sort (iv) Counting SortOnly IOnly iiBoth i and iiBoth iii and ivA
28Mergesort is a stable algorithm but not an in-place algorithmTrueFalseNANAA
29Memorization is?To store previous results for future useTo avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them laterTo make the process accurateNone of the aboveB
30Dynamic programming algorithms need to store the results of intermediate sub-problemsTrueFalseNANAA