DAA Quiz 1

Identify the time complexity that indicates the longest running time required by an

algorithm for any given input of size n, and thus guarantees that the algorithm will finish in the indicated period of time.

• Worst case

• Best case

• Average Case

• Constant Time

The θ-notation will be expressed as

• c2*g(n) <= t(n) <= c1*g(n) for all n >= n0

• T(n) <= c*g(n) for all n >= n0

• T(n) >= c*g(n) for all n >=n0

If the time complexity of algorithm A is O(n^2) and that of algorithm B is O(n), then the algorithm _____ is the slowest among A and B.

• B

• A

Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}.

The capacity of knapsack=20.

Find the maximum value output assuming items to be divisible.

• 80

• 100

• 60

• 90

• Asymptotic Tight Bound

Find out the optimal solution that maximizes the profit for the job sequencing problem

• a,e

• c,a,e

• b,a

While analyzing the non-recursive algorithm for matrix multiplication, it is necessary to investigate the best, worst and average case separately.

• True

• False

For all optimization problems, the greedy method will not always provide the best potential solution.

• True

• False

Let the number of occurrences of the characters A, B and C be 40, 35 and 25.___ will be the huffman code for the character C. (If the code is 000, give the answer only in digits as 000 and not using words, spaces in-between, quotations, etc)

Fractional knapsack problem is solved most efficiently by —--------------- technique.

Consider the P, Q, R and S with dimensions 20 x 15, 15 x 30, 30 x 5 and 5 x 40 respectively. Identify the dimension of the product matrix P.Q.R.S.

• 20 x 40

• 15 x 5

• 20 x 15