## Fundamental of Algorithms – CS502

**Question No: 1 ( Marks: 1 ) – Please choose one**

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

**Arrays**- Structures
- Link List
- Stack

**Question No: 2 ( Marks: 1 ) – Please choose one**

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

►Algebraic and logic ►Geometric and arithmetic

►**Arithmetic and logic **

►Parallel and recursive

**Question No: 3 ( Marks: 1 ) – Please choose one**

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

►**We do not know the optimum k **

►We use divide and conquer for sorting only ►We can easily perform it in linear time ►Size of data is not given

**Question No: 4 ( Marks: 1 ) – Please choose one**

What is the total time to heapify?

**Ο(log n)**- Ο(n log n)
- Ο(n
^{2}log n) - Ο(log
^{2}n)

**Question No: 5 ( Marks: 1 ) – Please choose one**

word Algorithm comes from the name of the muslim author ____________

►__Abu Ja’far Mohammad ibn Musa__** al-Khowarizmi**.

**Question No: 6 ( Marks: 1 ) – Please choose one **al-Khwarizmi’s work was written in a book titled _______________

►__al Kitab al-mukhatasar fi hisab al-jabr wa’l-muqabalah__

**Question No: 6 ( Marks: 1 ) – Please choose one**

Random access machine or RAM is a/an

- Machine build by Al-Khwarizmi
- Mechanical machine
- Electronics machine
**Mathematical model**

**Question No: 7 ( Marks: 1 ) – Please choose one**

_______________ is a graphical representation of an algorithm

- notation
^{}notation**Flowchart**- Asymptotic notation

**Question No: 8 ( Marks: 1 ) – Please choose one**

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

- 256MB
- 512MB
**an infinitely large**- 100GB

**Question No: 9 ( Marks: 1 ) – Please choose one**

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

- Algebraic and logic
- Geometric and arithmetic
**Arithmetic and logic**- Parallel and recursive

**Question No: 10 ( Marks: 1 ) – Please choose one**

What will be the total number of max comparisons if we run brute-force maxima algorithm with n elements?

*n*^{2}^{n}*n*^{8}

**Question No: 11 ( Marks: 1 ) – Please choose one**

What is the solution to the recurrence *T*(*n*) = *T*(*n*/2)+*n* .

*O*(log*n*)*O***(***n*)*O*(*n*log*n*)*O*(*n*^{2})

**Question No: 12 ( Marks: 1 ) – Please choose one**

Consider the following code: For(j=1; j<n;j++)

For(k=1; k<15;k++) For(l=5; l<n; l++)

{

Do_something_constant();

}

What is the order of execution for this code.

**O(***n*)- O(
*n*^{3}) - O(
*n*^{2}log*n*) - O(n
^{2})

**Question No: 13 ( Marks: 1 ) – Please choose one**

What is the total time to heapify?

**O(log n)**- Ο(n log n)
- Ο(n
^{2}log n) - Ο(log
^{2}n)

**Question No: 14 ( Marks: 1 ) – Please choose one**

Consider the following Algorithm:

Factorial (n){ if (n=1)

return 1 else

return (n * Factorial(n-1))

Recurrence for the following algorithm is:

- T(n) = T(n-1) +1
- T(n) = nT(n-1) +1
- T(n)= T(n-1) +n
**T(n)=T(n(n-1)) +1**

**Question No: 15 ( Marks: 1 ) – Please choose one**

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

**It will take Θ (1)**- Time will vary according to the nature of input data
- It can not be predicted
- It will take Θ (log n)

**Question No: 16 ( Marks: 1 ) – Please choose one**

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

**True**- False
- Less information to decide
- Either true or false

**Question No: 17 ( Marks: 1 ) – Please choose one**

Is it possible to sort without making comparisons?

**Yes**- No

**Question No: 18 ( Marks: 1 ) – Please choose one**

If there are Θ (n^{2}) entries in edit distance matrix then the total running time is

- Θ (1)
**Θ (n**^{2})- Θ (n)
- Θ (n log n)

**Question No: 19 ( Marks: 1 ) – Please choose one**

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

**► We do not know the optimum k **

- We use divide and conquer for sorting only
- We can easily perform it in linear time
- Size of data is not given

**Question No: 20 ( Marks: 1 ) – Please choose one**

The Knapsack problem belongs to the domain of _______________ problems.

**Optimization**- NP Complete
- Linear Solution
- Sorting

**Question No: 21 ( Marks: 1 ) – Please choose one**

Suppose we have three items as shown in the following table, and suppose the capacity of the knapsack is 50 i.e. W = 50.

Item | Value | Weight |

1 | 60 | 10 |

2 | 100 | 20 |

3 | 120 | 30 |

The optimal solution is to pick

- Items 1 and 2
- Items 1 and 3
**Items 2 and 3**- None of theselies to problems where we are interested in finding a single item from a larger set of _____________

**Question No: 22 ( Marks: 1 ) – Please choose one**

Mergesort is a stable algorithm but not an in-place algorithm.

►**True **

►false

**Question No: 23 ( Marks: 1 ) – Please choose one**

Counting sort the numbers to be sorted are in the range 1 to k where k is small.

►**True**

►False

**Question No: 24 ( Marks: 1 ) – Please choose one**

Total time for heapify is:

►Ο (log n)

►Ο (n log n)

►**Ο (log n)**

**Question No: 25 ( Marks: 1 ) – Please choose one**

In RAM model instructions are executed

►**One after another (**

►Parallel

►Concurrent

►Random

**Question No: 26 ( Marks: 1 ) – Please choose one**

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

►**Convergent geometric series **

►Divergent geometric series

►None of these

**Question No: 27 ( Marks: 1 ) – Please choose one**

Due to left-complete nature of binary tree, heaps can be stored in

►Link list

►Structure

►**Array **

►None of above