ADA Assignment1

1. 1 Quick sort is an example of a sorting algorithm based on which strategy?

• a. Dynamic programming

• b. Greedy approach

• c. Divide and conquer

• d. Backtracking

1. 2 What is the average time complexity of the bubble sort algorithm?

• a. O(n^2)

• b. O(n)

• c. O(log n)

• d. O(n log n)

3. 3 What is the time complexity of merge sort in all cases?

• a. O(n)

• b. O(n log n)

• c. O(n^2)

• d. O(log n)

4 Strassen`s matrix multiplication is an algorithm that multiplies two matrices using which approach?

• a. Brute force

• b. Greedy approach

• c. Dynamic programming

• d. Divide and conquer

5 What is the objective of the 0/1 Knapsack Problem?

• a. To maximize the total weight of the knapsack.

• b. To maximize the total value of the knapsack.

• c. To minimize the total weight of the knapsack.

• d. minimize the total value of the knapsack.

6 Which approach is commonly used to solve the 0/1 Knapsack Problem?

• a. Greedy algorithm

• b. Dynamic programming

• c. Depth-first search

• d. Breadth-first search

7 What is the time complexity of the dynamic programming solution for the 0/1 Knapsack Problem?

• a. O(n)

• b. O(n + W)

• c. O(nW)

• d. O(W^2)

8 Which algorithm is commonly used to solve the APSP problem?

• a. Dijkstra’s Algorithm

• b. Bellman-Ford Algorithm

• c . Floyd-Warshall Algorithm

• d. A* Search Algorithm

9 What is the main purpose of the branch and bound method in optimization problems?

• a. To find the best solution by exploring all possible solutions.

• b. To eliminate non-promising solutions through bounding.

• c. both A and B.

• d. None of the above.

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

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

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

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

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