DSA Quiz 2cse2

Which of the following sorting algorithms is not an in-place sorting algorithm?

• A. Merge Sort

• B. Quick Sort

• C. Shell Sort

• D. Heap Sort

What is time complexity of fun()?

int fun(int n)

{

    int count = 0;

    for (int i = n; i > 0; i /= 2)

        for (int j = 0; j < i; j++)

           count += 1;

    return count;

}

• (A)O(n2)

• (B)O(n*log(n))

• (C)O(n)

• (D)O(n*log(n*Log(n)))

What is the time complexity of Huffman Coding?

• (A)O(N)

  
  

• (B)O(NlogN)

• (C)O(N(logN)^2)

• (D)O(N^2)

What is the time complexity of Strassen's algorithm for matrix multiplication?

• O(n)

• O(nlogn)

• O(n^2)

• O(n^2.81)

The Bellman-Ford algorithm is used to solve:

• Single-source shortest path problem

• All-pairs shortest path problem

• Maximum flow problem

• Minimum spanning tree problem

The Master Theorem is used to solve recurrences of which type?

• Linear recurrences

• Quadratic recurrences

• Exponential recurrences

• Divide and Conquer recurrences

Which greedy algorithm solves the knapsack problem?

• Dijkstra's algorithm

• Prim's algorithm

• Kruskal's algorithm

• Fractional knapsack algorithm

What is the main difference between greedy algorithms and dynamic programming?

• Greedy algorithms always provide an optimal solution, while dynamic programming does not.

• Dynamic programming always provides an optimal solution, while greedy algorithms do not.

• Greedy algorithms only work for problems with optimal substructure, while dynamic programming can solve any problem.

• Dynamic programming only works for problems with optimal substructure, while greedy algorithms can solve any problem.

Which sorting algorithm has the best time complexity in the average case?

• MergeSort

• QuickSort

• ShellSort

• HeapSort

What is the best-case time complexity of QuickSort?

• O(n)

• O(nlogn)

• O(n^2)

• O(logn)