CS502 Midterm Online Quiz

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

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

The number of nodes in a complete binary tree of height h is

The time assumed for each basic operation to execute on RAM model of computation is-----

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

Counting sort has time complexity:

In Sieve Technique we do not know which item is of interest

If there are Θ (n2) entries in edit distance matrix then the total running time is

Slow sorting algorithms run in,

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

When we call heapify then at each level the comparison performed takes time

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

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

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

In analysis, the Upper Bound means the function grows asymptotically no faster than its largest term.

______________ graphical representation of algorithm.

While solving Selection problem, in Sieve technique we partition input data __________w

_______________ is a graphical representation of an algorithm

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

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

Sorting can be in _________

Random access machine or RAM is a/an

Cont sort is suitable to sort the elements in range 1 to k

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

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

For the worst-case running time analysis, the nested loop structure containing one “for” and one “while” loop, might be expressed as a pair of _________nested summations.

Efficient algorithm requires less computational…….

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

Quick sort is

In Heap Sort algorithm, the maximum levels an element can move upward is _________

The definition of Theta-notation relies on proving ___________asymptotic bound.

In Heap Sort algorithm, if heap property is violated _________

In plane sweep approach, a vertical line is swept across the 2d-plane and _______structure is used for holding the maximal points lying to the left of the sweep line.

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

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

In selection algorithm, because we eliminate a constant fraction of the array with each phase, we get the

A heap is a left-complete binary tree that conforms to the ___________

Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,

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

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

from a larger set of _____________

If the indices passed to merge sort algorithm are ________,then this means that there is only one element to sort.

One Example of in place but not stable sort is

An in place sorting algorithm is one that uses ___ arrays for storage

Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________

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

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

Which may be stable sort:

For the Sieve Technique we take time

Is it possible to sort without making comparisons?

For the heap sort we store the tree nodes in