Suppose we live where there are coins for 1, 4, and 6 units, and we have to make change for 8 units. Show the solution of this problem by dynamic programming.
Hint: Find the formula of c[i, j], which is the minimum number of coins required to pay an amount of j units. 1≤i≤n is the denomination and i have value di units, 0≤j≤N is the amount of units. Then set up a table for c[1..n, 0..N]
Using Dijkstra's algorithm to find the shortest path from A to all other vertices for the below graph, show the value of D and P of each node when a node is declared at each step.
Having an array A=[5, 13, 2, 25, 7, 17, 20, 8, 4]
a. Show the full array A by using Heapify algorithm step by step, each call of trickle down is considered as a step.
b. Show the full array A by using HEAPSORT step by step, each heapify is considered as a step and you could start directly with the answer from a.