CS502 Midterm Online Quiz

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

We cannot make any significant improvement in the running time which is better than that of brute-force algorithm.

Quick sort is

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

In Heap Sort algorithm, we build _______ for ascending sort.

For the heap sort we store the tree nodes in

For the sieve technique we solve the problem,

In RAM model instructions are executed

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

from a larger set of _____________

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.

_________ is one of the few problems, where provable lower bounds exist on how fast we can sort.

Random access machine or RAM is a/an

Floor and ceiling are ____________ to calculate while analyzing algorithms.

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

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

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

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

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

In analysis, the Lower Bound means the function grows asymptotically at least as fast as its largest term.

Efficient algorithm requires less computational…….

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

One example of in place but not stable algorithm is

The function f(n)= n(logn+1)/2 is asymptotically equivalent to n log n. Here Upper Bound means the function f(n) grows asymptotically ____________ faster than n log n.

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

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

The sieve technique works in ___________ as follows

In which order we can sort?

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

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

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

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

Sieve Technique can be applied to selection problem?

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

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

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

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

A RAM is an idealized algorithm with takes an infinitely large random-access memory.

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

One Example of in place but not stable sort is

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

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

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

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

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

For the heap sort, access to nodes involves simple _______________ operations.

Which may be stable sort:

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

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

_______________ is a graphical representation of an algorithm

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