Algorithms: Question Set – 12
What are the features of dynamic programming?
In order to save time and effort, optimal solutions to subproblems are stored away rather than having their values recalculated. We do not take into consideration decision sequences that contain subsequences that are less than ideal. It unquestionably delivers the best solution each and every time.
What are the drawbacks of dynamic programming?
Time and space requirements are high since storage is needed for all levels. Optimality should be checked at all levels.
Write the general procedure of dynamic programming.
- The development of a dynamic programming algorithm can be broken into a sequence of 4 steps.
- Characterize the structure of an optimal solution.
- Recursively define the value of the optimal solution.
- Compute the value of an optimal solution in the bottom-up fashion.
- Construct an optimal solution from the computed information.
Define the principle of optimality.
It states that an optimal sequence of decisions has the property that whenever the initial stage or decisions must constitute an optimal sequence with regard to stage resulting from the first decision.
Write any two characteristics of the Greedy Algorithm.
- Constructing the solution from the candidates that have been provided is an effective strategy for finding the best answer to a problem.
- The progression of the algorithm results in the accumulation of two more sets.
- One of these sets contains the candidates that have been considered previously and selected, while the other set contains the candidates that have been considered previously but not selected.
What is the Greedy choice property?
- The first part is the greedy choice property, which states that it is possible to arrive at a solution that is optimal globally by first arriving at a solution that is optimal locally.
- The choice that the greedy algorithm makes is dependent on the previous choices that have been made, but it cannot depend on any choices that will be made in the future or on the solution to the subproblem. It moves from the highest level to the lowest.
What is the use of Dijksra’s algorithm?
- The single-source shortest-paths problem can be solved with Dijkstra’s algorithm.
- This problem requires finding the shortest path from a specified vertex, which is referred to as the source, in a weighted connected graph to all of the other vertices in the graph.
- The task of finding the single-source shortest pathways requires the generation of a family of paths, each of which travels from the source to a different vertex in the graph, despite the fact that some paths may share edges.
Define the Spanning tree.
Spanning tree of a connected graph G: a connected acyclic subgraph of G that includes all of G‘s vertices
What is a minimum spanning tree?
Minimum spanning tree of a weighted, connected graph G: a spanning tree of G of the minimum total weight