DAA QUIZ-I

The time factor when determining the efficiency of algorithm is measured by

• Counting microseconds

• Counting the number of key operations

• Counting the number of statements

• Counting the kilobytes of algorithm

Dijkastra’s algorithm bears some similarity to

• BFS

• PRIMS

• DFS

• BOTH (A) & (C)

The concept of order Big O is important because

• It can be used to decide the best algorithm that solves a given problem

• It determines the maximum size of a problem that can be solved in a given amount of time

• It is the lower bound of the growth rate of algorithm

• Both A and B

Tight bound is denoted as _______

• Ω

• Θ

• O

• o

Which of the following shows the correct relationship among some of the more common computing times on algorithms

• O(log n) < O(n) < O( n* log n) < O(2n ) < O(n2 )

• O(n) < O(log n) < O( n* log n) < O(2n ) < O(n2 )

• O(n) < O(log n) < O( n* log n) < O(n2 ) < O(2n )

• O(log n) < O(n) < O( n* log n) < O(n2 ) < O(2n )

Which of the following properties are necessary for an Algorithm?

• Definiteness

• Correctness

• Effectiveness

• A and C

The running time of Floyd-Warshall algorithm is

• ϴ (n)

• ϴ (n3 )

• ϴ (n2 )

• ϴ (n log n)

Kruskal’s algorithm uses-------- and prim’s algorithm uses------ in determining the MST

• edges,vertex

• vertex,edges

• edges,edges

• vertex,vertex

Suppose we have an O(n) time algorithm that finds the median of an unsorted array. Now consider a QuickSort implementation where we first find the median using the above algorithm, then use the median as a pivot. What will be the worst-case time complexity of this modified QuickSort?

• 
  O(n^2 Logn

• 
  O(n^2)

• 
  O(n Logn Logn)

• O(nLogn)

What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

• 
  Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)

• Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)

• 
  Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)

• 
  Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)