# Fundamental of Algorithms

## 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
• 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)
• Ο(n2 log n)
• Ο(log2 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
• n8

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

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

• O(logn)
• O(n)
• O(nlogn)
• O(n2)

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(n3)
• O(n2 log n)
• O(n2)

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

What is the total time to heapify?

• O(log n)
• Ο(n log n)
• Ο(n2 log n)
• Ο(log2 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 Θ (n2) entries in edit distance matrix then the total running time is

•  Θ (1)
• Θ (n2)
• Θ (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