CS502 Midterm Online Quiz

In simple brute-force algorithm, we give no thought to efficiency.

Efficient algorithm requires less computational…….

Analysis of Selection algorithm ends up with,

The running time of quick sort depends heavily on the selection of

The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,

For the heap sort we store the tree nodes in

Divide-and-conquer as breaking the problem into a small number of

Upper bound requires that there exist positive constants c2 and n0 such that f(n) ____ c2n for all n <= n0(ye question ghalat lag raha hai mujhae

A RAM is an idealized machine with ______________ random-access memory.

One of the clever aspects of heaps is that they can be stored in arrays without using any _______________.

Before sweeping a vertical line in plane sweep approach, in start sorting of the points is done in increasing order of their _______coordinates.

For the Sieve Technique we take time

44.The running time of an algorithm would not depend upon the optimization by the compiler but that of an implementation of the algorithm would depend on it.

In 2d-space a point is said to be ________if it is not dominated by any other point in that space.

Quick sort is based on divide and conquer paradigm; we divide the problem on base of pivot element and:

What type of instructions Random Access Machine (RAM) can execute?

For Chain Matrix Multiplication we can not use divide and conquer approach because,

A (an) _________ is a left-complete binary tree that conforms to the heap order

Due to left complete nature of binary tree, the heap can be stored in

Asymptotic growth rate of the function is taken over_________ case running time.

In ____________ we have to find rank of an element from given input.

Counting sort has time complexity:

A point p in 2-dimensional space is usually given by its integer coordinate(s)____________

_______________ is a graphical representation of an algorithm

Which sorting algorithm is faster

Is it possible to sort without making comparisons?

In pseudo code, the level of details depends on intended audience of the algorithm.w

Which may be stable sort:

Algorithm is a mathematical entity, which is independent of a specific machine and operating system.

Brute-force algorithm uses no intelligence in pruning out decisions.

Quick sort is

In RAM model instructions are executed

For Chain Matrix Multiplication we can not use divide and conquer approach because,

In addition to passing in the array itself to Merge Sort algorithm, we will pass in _________other arguments which are indices.

In Quick sort, we don’t have the control over the sizes of recursive calls

Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,

In Quick Sort Constants hidden in T(n log n) are

The array to be sorted is not passed as argument to the merge sort algorithm.

The analysis of Selection algorithm shows the total running time is indeed ________in n,

F (n) and g (n) are asymptotically equivalent. This means that they have essentially the same __________ for large n.

The sieve technique is a special case, where the number of sub problems is just

Sorting can be in _________

Quick sort is best from the perspective of Locality of reference.

For the Sieve Technique we take time

Sieve Technique applies to problems where we are interested in finding a single item

from a larger set of _____________

Algorithm analysts know for sure about efficient solutions for NP-complete problems.

Brute-force algorithm for 2D-Maxima is operated by comparing ________ pairs of points.

The function f(n)=n(logn+1)/2 is asymptotically equivalent to nlog n. Here Lower Bound means function f(n) grows asymptotically at ____________ as fast as nlog n.

In Heap Sort algorithm, the total running time for Heapify procedure is ____________

One Example of in place but not stable sort is