All questions of Dynamic Programming for Software Development Exam

Dynamic Programming
Dynamic Programming is a technique used in computer science and mathematics to solve complex problems by breaking them down into smaller overlapping subproblems. It is often used when a problem can be expressed as the optimal solution of subproblems, and the optimal solution of the larger problem can be constructed from the optimal solutions of the subproblems.

Dynamic Programming and the Fibonacci Sequence
The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones. It can be defined recursively as follows:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

Calculating the nth Fibonacci number using the recursive definition can be inefficient, as it involves redundant computations of the same subproblems. This is where Dynamic Programming comes in.

Efficiently Solving Fibonacci Using Dynamic Programming
Dynamic Programming can be used to efficiently solve the Fibonacci sequence problem by storing the results of previously computed subproblems and reusing them when needed. This approach is known as memoization.

Here is how Dynamic Programming can be applied to calculate the nth Fibonacci number:

1. Create an array or a table to store the previously computed Fibonacci numbers.
2. Initialize the base cases F(0) and F(1) in the table.
3. Iterate from 2 to n, and for each index i, compute the Fibonacci number F(i) by adding the values of F(i-1) and F(i-2) from the table.
4. Return the value of F(n).

Advantages of Dynamic Programming
Dynamic Programming offers several advantages when used to solve problems:

1. Overlapping subproblems: Dynamic Programming breaks down a problem into smaller subproblems, and the solutions to these subproblems can be reused multiple times, avoiding redundant computations.
2. Optimal substructure: The optimal solution to a larger problem can be constructed from the optimal solutions of its subproblems.
3. Time complexity improvement: By avoiding redundant computations, Dynamic Programming can significantly improve the time complexity of a solution.

Therefore, when given the options, calculating the nth Fibonacci number can be efficiently solved using Dynamic Programming.

Introduction
In graph theory, finding the shortest path between all pairs of vertices is a crucial task. The Floyd-Warshall algorithm is particularly effective for this purpose in directed graphs.
Floyd-Warshall Algorithm Overview
- It is a dynamic programming algorithm that computes shortest paths between all pairs of vertices in a graph.
- It can handle both positive and negative edge weights, but it does not work with graphs containing negative cycles.
Algorithm Steps
1. Initialization:
- Create a distance matrix where each entry (i, j) holds the weight of the edge from vertex i to vertex j. If no edge exists, set it to infinity. The diagonal entries are set to zero.
2. Updating Distances:
- For each vertex k, update the distance matrix. For every pair of vertices (i, j), check if the path from i to j through k is shorter than the current known distance. If so, update it.
3. Complexity:
- The time complexity is O(V^3), where V is the number of vertices, making it suitable for smaller graphs.
Advantages of Floyd-Warshall
- Simplicity: The algorithm is straightforward to implement.
- Comprehensive: It finds shortest paths for all pairs, rather than just a single source.
Conclusion
The Floyd-Warshall algorithm is the correct choice for finding the shortest paths between all pairs of vertices in a directed graph due to its effectiveness and ability to handle various edge weights.