QUIZ 01 -DAA

Analyze the time complexity derivation of the divide and conquer maximum subarray algorithm. Which recurrence relation represents the time complexity correctly?

• T(n)=T(n−1)+O(1)

• T(n)=2T(n/2)+O(n)

• T(n)=T(n/2)+O(log n)

• T(n)=nT(n−1)+O(n2))

Huffman coding produces a prefix-free code that minimizes the weighted path length. Which data structure most efficiently supports the construction of this code?

• Linked List

• Priority Queue (Min-Heap)

• Stack

• Binary Search Tree

Which of the following properties is not required for an algorithm to be solvable optimally using greedy techniques?

• Greedy-choice property

• Optimal substructure

• Overlapping subproblems

• Problem decomposition into independent subproblems

In analyzing the time complexity of the maximum subarray problem solved by divide and conquer, the merging step takes O(n)O(n)O(n) time. What does this step accomplish?

• Combining the solutions of left and right subarrays, including subarrays crossing the midpoint

• Sorting the array to reduce the problem size

• Removing duplicate subarrays

• Calculating the prefix sums for dynamic programming

Suppose you design a new algorithm for a problem and derive its time complexity as O(nlogn). Which of the following algorithmic techniques is most likely used?

• Dynamic programming with memoization

• Greedy algorithm with sorting

• Divide and conquer with recursive calls

• Backtracking with pruning

The Subset Sum problem solved using backtracking is classified as:

• Polynomial time problem

• NP-complete problem

• Greedy solvable problem

• Linear time problem

In the Branch and Bound method using FIFO-BB for the job selection problem, the primary difference from LIFO-BB is:

• FIFO-BB explores nodes in a breadth-first manner; LIFO-BB in a depth-first manner

• FIFO-BB requires more memory than LIFO-BB always

• LIFO-BB guarantees optimal solution, FIFO-BB does not

• Both methods explore nodes in the same order

For the Matrix Chain Multiplication problem with matrices A1,A2,…,An, which of the following best describes the order of complexity of the dynamic programming solution?

• O(n^2)

• O(n^3)

• O(2^n)

• O(n log n)

The time complexity of the naive backtracking solution for the Traveling Salesman Problem (TSP) is:

• O(n^2)

• O(n!)

• O(2^n)

• O(nlogn)

Given matrices A1 of dimension 10×30, A2​ of dimension 30×5 and A3​ of dimension 5×60, what is the cost (number of scalar multiplications) of multiplying (A1A2)A3​?

• 4500

• 27000

• 10500

• 9000