We are given a complete binary tree where nodes and edges have positive weights. Node weights...

Transcribed Image Text:

We are given a complete binary tree where nodes and edges have positive weights. Node weights are stored in a 2-dimensional array WN. Edge weights are stored in a 2-dimensional array WE where O denotes no edge. Node indices are given form top-to-bottom and left-to-right (e.g. root node index is 1, its left child 2 and so on...). Starting at the root of the tree and moving to either one of the children from the current node, the goal is to find the minimum total weight (i.e. sum of node and edge weights) path from the root to any one of the leaves. Example: Node weights array: WN=[3 4 2 6 1 9 8 851 Edge weights array: WE=[0 15 000 000 0006 20000 00000 9300 0 0 0 0 0 0 0 6 4 000000000 000000000 000000000 000000000 000000000 use java for implementations Output: Min total weight path includes nodes 1-2-5 with total weight 11. 1. Implement the greedy algorithm (i.e., write a function) of choosing the child with smallest sum of edge and node weights each time. 2. Implement a recursive algorithm (i.e., write a function) to find the minimum total weight. You must determine the input parameters. Also, give the time complexity of a recursive algorithm that implements this formulation? Show your work. 3. Implement a dynamic programming algorithm to solve the problem. You must determine the input parameters. Also, give the time complexity of your dynamic programming solution? Show your work. 4. In your main function: a. Show that the greedy algorithm does not solve this problem optimally. b. Run each of the recursive and dynamic functions with three different input sizes and compute the actual running times (in milliseconds or seconds) of these three algorithms. You will need to calculate the time passed before and after making a call to each function. Provide a 2x3 table involving the actual running times. We are given a complete binary tree where nodes and edges have positive weights. Node weights are stored in a 2-dimensional array WN. Edge weights are stored in a 2-dimensional array WE where O denotes no edge. Node indices are given form top-to-bottom and left-to-right (e.g. root node index is 1, its left child 2 and so on...). Starting at the root of the tree and moving to either one of the children from the current node, the goal is to find the minimum total weight (i.e. sum of node and edge weights) path from the root to any one of the leaves. Example: Node weights array: WN=[3 4 2 6 1 9 8 851 Edge weights array: WE=[0 15 000 000 0006 20000 00000 9300 0 0 0 0 0 0 0 6 4 000000000 000000000 000000000 000000000 000000000 use java for implementations Output: Min total weight path includes nodes 1-2-5 with total weight 11. 1. Implement the greedy algorithm (i.e., write a function) of choosing the child with smallest sum of edge and node weights each time. 2. Implement a recursive algorithm (i.e., write a function) to find the minimum total weight. You must determine the input parameters. Also, give the time complexity of a recursive algorithm that implements this formulation? Show your work. 3. Implement a dynamic programming algorithm to solve the problem. You must determine the input parameters. Also, give the time complexity of your dynamic programming solution? Show your work. 4. In your main function: a. Show that the greedy algorithm does not solve this problem optimally. b. Run each of the recursive and dynamic functions with three different input sizes and compute the actual running times (in milliseconds or seconds) of these three algorithms. You will need to calculate the time passed before and after making a call to each function. Provide a 2x3 table involving the actual running times.

Answer rating: 100% (QA)

Answer 1 Greedy Algorithm public class GreedyAlgorithm int currentLevel 0 final int maxLevel 3 Socia... View the full answer