CS 502 – Fundamentals of Algorithms Current Solved Quiz 2021

CS 502 – Fundamentals of Algorithms Current Solved Quiz 2021

In selection problem the sieve technique works in

1. Non-recursive manner
2. Constant time
3. Phases
4. One complete go

In  selection problem the sieve technique

1. Add some more input items each time
2. Do not work recursively
3. Do not uses divide and conquer approach
4. Eliminates undesired data items each time

In the analysis of selection algorithm we got the convergent

1. Harmonic
2. Linear
3. Arithmetic
4. Geometric

Identify the TRUE statement

1. The knapsack problem does not belong to the domain of optimization problem
2. The knapsack problem belong to the domain of optimization problem
3. The knapsack problem can not be solved by using dynamic programming
4. The knapsack problem is optimally solved by using brute force algorithm

The only way to convert an empty string into a string of I character is by doing  j insertions represented as

1. E (I , j) =l
2. E (I , 0) = i
3. E (0 , j) = j
4. E (I , j) = j

__________ provide us more accurate result when input values are not closer with each other

1. Average
2. Median

In merge sort algorithm we split the array around the ________ index q.

1. Entering
2. Mid
3. Exiting
4. Summing

Matrix multiplication is a (n)__________ option.

1. Commutative
2. Associative
3. Neither commutative nor associative
4. Commutative but not associative

The sieve technique works where we have to find __________ item(s) from a large input

1. Single
2. Two
3. Three
4. Similar

For average-case time analysis of quick sort algorithm pivot selection is on average basis from

1. Half of the input value
2. All possible random values
3. Pivot is input separately
4. Values greater than 5

Algorithm is a sequence of computational steps that ……the input into output

1. Merge
2. Assign
3. Transform
4. Integrate

If matrix A of dimension p x q is multiply with matrix B of dimension q x r then each entry in resultant matrix takes…….time

1. O (q)
2. O (1)
3. O (P X q)
4. O (q x r)

CS 502 – Fundamentals of Algorithms Current Solved Quiz 2021

In Dynamic programming based solution of knapsack problem if we decide to take an object T then we gain

1. W (total weight of knapsack)
2. V (Total value of all items)
3.  V i (value of object i)
4. None of the given option

In the statement output p[i].x ,p[i].y , the number of time elements of p are accessed is……..

1. 1
2. 2
3. 3
4. 4

In heap sort algorithm the total running time for heapify procedure procedure is ___________

1. Theta (log n)
2. Order (log n)
3. Omega (log n)
4. O (1) i.e constant time

Pseudo code algorithms are to be read by

1. People
2. RAM
3. Computer
4. Compiler

If pj dominates pi and pi dominates ph then pj also dominates ph .It mean domince relation is

1. Transitive
2. Non transitive
3. Equation
4. Symbolic

_________ is a method of solving a problem in which we check all possible solutions to the problem to find the solution we need.

1. Plane-sweep Algorithm
2. Sorting Algorithm
3. Brute-force Algorithm
4. Greedy approach

In sorting the key value or attribute _______ from an ordered domain

1. Must be
2. Not always

The worst case running time of quick sort algorithm

1. Cannot be quadratic
2. Is quadratic
3. Is always exponential
4. Is linear

In max heap (for Heap sort algorithm when every time maximum element is removed from top we replace it with _______ leaf in the tree

1. Second last
2. Last
3. First
4. Any

Consider three matrices X , Y , Z of dimensions 1 x 2 x 3 x 4 x respectively .The number of multiplications of X(YZ) is

1. 16
2. 32
3. 26
4. 32

Which of the following is calculated with Big O notation

1. Medium bound
2. Upper bound
3. Lower bound
4. Both upper and lower bounds

While sorting the ordered domain means for any two input elements x and y ________ satisfies only

1. X < y
2. X > y
3. X = y
4. All of the above

CS 502 – Fundamentals of Algorithms Current Solved Quiz 2021

Which one is not passed as parameter in quick sort algorithm?

1. End of the array
2. Middle of the array
3. Array (containing input elements)
4. Start of the array

In selection problem the rank of an element will be its _______ position if we sort the data

1. First
2. Final
3. Second last
4. Last

Election algorithm takes theta

1. (n2)
2. (n)
3. Log(n)
4. Nlog(n)

The only way to convert a string of I character into the empty string is with I deletion represented as ____

1. E (o , j) = j
2. E (I , j) = i
3. E (0 , I) = j
4. E ( I , 0) = i

To find maximal points in brute-force algorithm each point of the space is compared against _____ of that space

1. One other point
2. All other point
3. Few other point
4. Most of the other points

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

1. 1. left-complete
2. right-complete
3. tree nodes
4. tree leaves

Sieve Technique can be applied to selection problem?

1. True
2. False

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

1. increasing order only
2. decreasing order only
3. heap order
4. (log n) order

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

1. heap
2. binary tree
3. binary search tree
4. array

 

1. pivot
2. Sieve
3. smaller sub problems
4. Selection

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

1. True
2. FalseThe recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required?
   16
   10
   32
   31

   In the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent _______________ series in the analysis,
   linear
   arithmetic
   geometric 
   exponent

   For the heap sort, access to nodes involves simple _______________ operations.
   arithmetic
   binary
   algebraic
   logarithmic

   For the sieve technique we solve the problem,
   recursively
   mathematically
   precisely
   accurately

   The sieve technique works in ___________ as follows
   phases
   numbers
   integers
   routines

   Slow sorting algorithms run in,
   T(n^2)
   T(n)
   T( log n)

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

   In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
   T(n)
   T(n / 2)
   log n
   n / 2 + n / 4

   The sieve technique is a special case, where the number of sub problems is just
   5
   many
   1
   few

   In which order we can sort?
   increasing order only
   decreasing order only
   increasing order or decreasing order
   both at the same time

   Analysis of Selection algorithm ends up with,
   T(n)
   T(1 / 1 + n)
   T(n / 2)
   T((n / 2) + n)

   The analysis of Selection algorithm shows the total running time is indeed ________in n,
   arithmetic
   geometric
   linear
   orthogonal

   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

   For the heap sort we store the tree nodes in
   level-order traversal
   in-order traversal
   pre-order traversal
   post-order traversal

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

Divide-and-conquer as breaking the problem into a small number of
pivot
Sieve
smaller sub problems
Selection

How much time merge sort takes for an array of numbers?
T(n^2)
T(n)
T( log n)
T(n log n)

The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
divide-and-conquer
decrease and conquer
greedy nature
2-dimension Maxima

The number of nodes in a complete binary tree of height h is
2^(h+1) – 1
2 * (h+1) – 1
2 * (h+1)
((h+1) ^ 2) – 1

Sieve Technique applies to problems where we are interested in finding a single item from a larger set of _____________
n items
phases
pointers
constant

Memorization is?

To store previous results for future use
To avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later
To make the process accurate
None of the above

Which sorting algorithm is faster
O (n log n)
O n^2
O (n+k)
O n^3

Quick sort is

Stable & in place
Not stable but in place
Stable but not in place
Some time stable & some times in place

One example of in place but not stable algorithm is
Merger Sort
Quick Sort
Continuation Sort
Bubble Sort

In Quick Sort Constants hidden in T(n log n) are
Large
Medium
Small
Not Known

Continuation sort is suitable to sort the elements in range 1 to k
K is Large
K is not known
K may be small or large
K is small

In stable sorting algorithm.

If duplicate elements remain in the same relative position after sorting
One array is used
More than one arrays are required
Duplicating elements not handled

Which may be a stable sort?
Merger
Insertion
Both above
None of the above

An in place sorting algorithm is one that uses ___ arrays for storage
Two dimensional arrays
More than one array
No Additional Array
None of the above

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

In Sieve Technique we donot know which item is of interest
True
False

Sorting is one of the few problems where provable ________ bonds exits on how fast we can sort,
upper
lower
average
log n

The reason for introducing Sieve Technique algorithm is that it illustrates a very important special case of,
divide-and-conquer
decrease and conquer
greedy nature
2-dimension Maxima

Analysis of Selection algorithm ends up with,
T(n)
T(1 / 1 + n)
T(n / 2)
T((n / 2) + n)

In in-place sorting algorithm is one that uses arrays for storage :
An additional array
No additioanal array
Both of above may be true according to algorithm
More than 3 arrays of one dimension.

Which sorting algorithn is faster :
O(n^2)
O(nlogn)
O(n+k)
O(n^3)

The running time of quick sort depends heavily on the selection of
No of inputs
Arrangement of elements in array
Size o elements
Pivot elements

Which may be stable sort:
Bubble sort
Insertion sort
Both of above

For the Sieve Technique we take time

T(n / 3)
n^2
n/3

More Quiz click here

End 301 Solved Current quiz