CTECH-02.02.2024-FN

What is dynamic programming in data structures?

• A technique for designing efficient algorithms by breacking down a problem into smaller subproblems
• A way to store and organize data in a computer program
• A process of optimizing memory usage in a program
• Amethod for creating algorithms that use only constant space

Consider the recursive implementation to find the nth fibonacci number: int fibo(int n) if n <= 1 return n return __________ Which line would make the implementation complete?

• fibo(n) + fibo(n)
• fibo(n) + fibo(n – 1)
• fibo(n – 1) + fibo(n + 1)
• fibo(n – 1) + fibo(n – 2)

Suppose we find the 8th term using the recursive implementation. The arguments passed to the function calls will be as follows: fibonacci(8) fibonacci(7) + fibonacci(6) fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4) fibonacci(5) + fibonacci(4) + fibonacci(4) + fibonacci(3) + fibonacci(4) + fibonacci(3) + fibonacci(3) + fibonacci(2) : : : Which property is shown by the above function calls?

• Memoization
• Optimal substructure
• Overlapping subproblems
• Greedy

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________

• Dynamic programming
• Greedy
• . Divide and conquer
• Recursion

The following sequence is a fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21,….. Which technique can be used to get the nth fibonacci term?

• Recursion
• Dynamic programming
• A single for loop
• Recursion, Dynamic Programming, For loops

What is the space complexity of the recursive implementation used to find the nth fibonacci term?

• O(1)
• O(n)
• O(n2)
• O(n3)

Which of the following is/are property/properties of a dynamic programming problem?

• Optimal substructure
• Overlapping subproblems
• Greedy approach
• Both optimal substructure and overlapping subproblems

Which of the following is not a characteristic of dynamic programming?

• Overlapping subproblems
• Optimal substructure
• Recursion
• Divide and Conquer

In dynamic programming, the technique of storing the previously calculated values is called ___________

• Saving value property
• Storing value property
• Memoization
• Mapping

Which of the following problems should be solved using dynamic programming?

• Mergesort
• Binary search
• Longest common subsequence
• Quicksort