CS502 Midterm MCQs by VU Topper RM

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

➢constant page 10

If the indices passed to merge sort algorithm are not equal, the algorithm may return immediately. ➢True

➢false page 28

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

➢True page 18

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

➢True page 24

For small values of n, any algorithm is fast enough. Running time does become an issue when n gets large. ➢Fast

➢True page 14

Heaps can be stored in arrays without using any pointers; this is due to the ___ nature of the binary tree ➢right-complete ➢tree nodes

➢Left-complete page 40

One of the clever aspects of heaps is that they can be stored in arrays without using any______ ➢constants ➢variables

➢Point page 40

How much time merge sort takes for an array of numbers?

➢T(n) ➢T( log n)

➢T(n log n) Page40

The sequence of merge sort algorithm is:

➢Conquer-Divide-Combine

➢Divide-Conquer-Combine Page 27

➢Combine-Divide-Conquer

In ______ Knapsack Problem, limitation is that an item can either be put in the bag or not. Fractional items are not allowed.

➢1

➢0/1 Page 91

➢Fractional

In Selection algorithm, we assume pivot selection takes theta _______ running time.

➢a. n Page – 36

➢n2 ➢n3

In Heap Sort algorithm (using max heap), when every time maximum elements removed from top ________.

➢it becomes Order n2 Algorithm ➢Divide and Conquer strategy helps us

➢We are left with a hole Page – 41

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.

➢ O (q) Page – 84

➢O (1) ➢O (p x q) In max heap (for Heap Sort algorithm), when every time maximum element is removed from top we replace it with _____ leaf in the tree.

➢second last

➢Last Page -41

➢First

For comparison-based sorting algorithms, it is possible to sort more efficiently than Omega n log(n) time.

➢Sometimes not

➢NOT Pg 54

➢Sometimes

In Sorting the key value or attribute_____ from an ordered domain.

➢Must be page 39

➢Not always ➢May be

Result of asymptotical analysis of n(n -3) and 4n*n is that _______

➢n(n-1) is asymptotically Greater ➢Both are asymptotically Not equivalent

➢Both are asymptotically Equivalent page 23 (4n*n= 4n2)

Floor and ceiling are ______ to calculate while analyzing algorithms

➢Very easy ➢3rd Option is missing

➢Usually considered difficult

_____ of reference is an important fact of current processor technology.

➢Defining ➢Assigning