Recurrence Relations and Algorithms Quiz

Solve the recurrence relation T(n)=2T(n/4)+ n^2 using the Master's Theorem. What is the time complexity of T(n)?

• O(n^2 log n)

• O(n^2)

• O(n log n)

• O(n^3)

Solve the recurrence relation T(n)=3T(n/3)+n using the Master's Theorem. What is the time complexity of T(n)?

• O(n log n)

• O(n^2)

• O(n log^2 n)

• O(n)

Solve the recurrence relation T(n)=8T(n/4)+n^2 using the Master's Theorem. What is the time complexity of T(n)?

• O(n^2 log n)

• O(n^3)

• O(n^2)

• O(n log n)

Solve the recurrence relation T(n)=6T(n/2)+ n^3 using the Master's Theorem. What is the time complexity of T(n)?

• O(n^3)

• O(n^4)

• O(n^3 log n)

• O(n^2 log^2 n)

You are given coins of denominations {1,3,4}. What is the minimum number of coins required to make a value of 6 using dynamic programming?

• 2

• 3

• 4

• 6

In the Traveling Salesman Problem using dynamic programming, what is the state definition for DP(S,i) where S is a set of visited cities, and i is the current city?

• The shortest path from the start to city i.

• The shortest path that visits all cities in S and ends at city i.

• The longest path that visits all cities in S and ends at city i.

• The shortest path from the city i to the end.

You are given coins of denominations {1,2,5}. What is the minimum number of coins needed to make a total of 7?

• 2

• 3

• 4

• 5

What is the base case for solving the Making Change Problem using dynamic programming?

• T(0)=0

• T(1)=1

• T(n)=n

• T(n)=infinity

What is the goal of the Traveling Salesman Problem (TSP)?

• To visit all cities exactly once with the shortest distance and return to the starting city.

• To visit half the cities with the longest path.

• To sort cities based on distance.

• To visit all cities randomly and stop at any point.

Find the Longest Common Subsequence (LCS) for the input sequences "AGGTAB" and "GXTXAYB".

• "AGTAB"

• "GTAB"

• "GXTXAY"

• "GGTAB"