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
  • 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)
  • Ο(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.

ItemValueWeight
16010
210020
312030

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