Algorithms Questions and Answers August 18, 2021

a) Create a program to perform the following operations on a binary search tree Construct a binary search tree Insert elements into a non empty binary search tree Delete elements from a non empty binary search tree Search for an element in a binary search tree Retrieve the elements of a binary search tree in the sorted order i. ii. iii. iv. V.

Construct a binary search tree with the below information. A) The preorder traversal of a binary search tree 11, 5, 4, 6, 12, 13. B) The inorder traversal of a binary search tree 11, 5, 4, 6, 12, 13.

1. There are 24 (4!) different orders of 1, 2, 3, 4. How many orders can produce the same shape as the 2, 1, 4, 3 ?

The shape of binary search tree depends on the order of the input. For example, there are 3 6 different orders of 1, 2, 3, which create 5 different shapes If the input order is 1, 2, 3, the binary search tree is in Fig. 4 (a). If the input order is 1, 3, 2, the binary search tree is in Fig. 4 (b). If the input order is 2, 1, 3, the binary

a) Draw a picture of a full binary search tree containing the numbers 2, 11, 13, 16, 21, 36, 69. Make sure that your tree retains the binary search tree property. Note full is different from complete. b) Draw a picture of a complete binary search tree containing the numbers 2, 11, 13, 16, 21. Make sure that your tree retains the binary search tree

Write a java program to create a binary search tree that consists of ten nodes with integer values and implement the following operations. 1) Find and display the sum of the integer values of the binary search tree 2) Search for the value 5 in the binary search tree and display the result of searching 3) Delete a given value from the binary

A binary search tree is used to store integer keys. Suppose that this binary search tree has the following behavior in searching. Test case (Case 1) Search key 45 (Case 2) Search key 78 (Case 3) Search key 20 The order of visited tree nodes 61, 32, 50, 41, 45 61, 89, 67, 72, 78 61, 32, 11, 25, 22, 20 Draw the binary search tree with the nodes

Show the result of inserting 3,1,4,6,9,2,5,7 into initial Binary Search Tree. (Show only the final tree). Write down the pre-order, in-order and post-order traversal of the resulting Binary Search Tree (1-a). Show the result of deleting the root from the Binary Search Tree (1-a).

(a) Do you know the difference between binary search tree and binary tree (b) Given the following binary search tree (BST), perform breadth first search and depth first search, respectively. (c) 5 10 12 15 18 Figure 2 A sample binary search tree With reference to Figure 2, traverse the binary search tree in order of i. Preorder ii. Postorder iii.

(Q16 pts) Use the Selection Sort algorithm to sort the array assigned to you. Show the contents of the array in each of the iterations of the algorithm. (Q29 pts) Construct a heightbalanced binary search tree of the sorted array of (Q1). Show all the steps in the construction process as the binary search tree evolves. If you just show the final

(i) Draw the binary search tree after deleting the key 30. (ii) Draw the binary search tree after deleting the key 48 from the resultant binary search tree in part (b) (i) of this question. (iii) Draw the binary search tree after deleting the key 20 from the resultant binary search tree in part (b) (ii) of this question. (c) Explain why the time

Suppose a physical system is represented by the following system of equations, where u(t) is the input and y(t) is the output d 21 (t) dt 22(t) ( 7 2(t 1) u(t) , u(t), y(t)z1(t1)22(t) u(t). 21 (t) For each of the following properties, determine if it applies to the above system and briefly justify your answers (rigorous proofs not needed).

For each of the following operation, draw the final state of the binary search tree after the remove operation. Remove node 65 from the original tree. Remove node 16 from the original tree. Remove node 12 from the original tree. Remove node 42 from the original tree. 2 8 (12) (16) 42 (22) 19 (53) (60 (57 65 Write a pseudo code for the before()

Given the following keys, draw two binary search trees of minimum and maximum height. Use the resulting binary search trees to explain the impacts of height on the binary search tree's operations. Keys: 1, 2,4,6, 10, 14, 16, 17, 18, 22, 28, 32, 33, 39, 44, b) Delete the following keys from the binary search tree that you have created above the

Draw a binary search tree with keys 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 that has exactly keys 1, 3, 7, and 9 in the leaves. Make the height of your tree as small as possible.

Imagine we have created a Binary Search Tree by inserting the following sequence of integers into an empty Binary Search Tree (in this exact order) 10, 20 Provide a single positive integer that, when added after the above sequence of integers, will result in a perfectly unbalanced tree.,Imagine we have created a Binary Search Tree by inserting the

Draw a binary search tree and AVL tree from the following traversals: {15, 5, 20, 70, 3, 10, 60, 90, 16} Delete 15 and re-draw both Binary Search Tree and AVL Tree drawn in given traversal. Reverse path of Binary Search Tree drawn Convert Binary Search Tree into Binary Tree such that sum of all greater keys is added to every key. Write a code to

Draw a binary search tree and AVL tree from the following traversals: {15, 5, 20, 70, 3, 10, 60, 90, 16} Convert Binary Search Tree into Binary Tree such that sum of all greater keys is added to every key. Write a code to Convert Binary Search Tree drawn into Balanced Binary Search Tree

(a) Draw a binary search tree whose elements are inserted in the following order 11, 7, 13, 8, 12, 6, 20, 18, 2, 24, 17,(b) Given the binary search tree built in part (a), show the resulting binary search tree after deleting the node 18 using the deletion algorithm for binary search trees we studied in class.,(c) Print out the original binary

Suppose you are given an array of integers representing the elements of a binary tree, and you need to create a binary search tree from it. Once the binary search tree is created, you need to perform the following Implementation of a function to create a Mirror Tree. Insert function for a binary search tree using recursion. Write a C++ program

C program to build a Binary Search Tree using the following elements: 45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81 Do In-order Traversal on the constructed Binary Search Tree

What is the binary search tree rank of node E? What is the binary search tree successor of node E? What is the depth of node E?

H D I B J E A F C G

a) Write a method for the BSTNode class to produce an array containing the values from a Binary Search Tree in descending order. b) To efficiently search a binary search tree what must be true about that binary search tree Explain why this is so. What is the maximum number of nodes in the bottom level of a balanced binary search tree with n nodes

The traversals of a Binary Search Tree are given as following 50, 30, 20, 10, 9, 15, 25, 28, 40, 60 9, 15, 10, 28, 25, 20, 40, 30, 60, 50 PreOrder PostOrder Construct a Binary Search Tree Traverse in LevelWise Traverse in Order

Calculate the Search Cost of this Binary Search Tree and determine whether it is an Optimal Binary Search Tree. If it is not optimal, please draw the Optimal Binary Search Tree and the Smallest Expected Search Cost. Based on the previous question, is the Optimal Binary Search Tree you found in 1. unique? If not, please draw two different Optimal

do K1 d K2 d K3 d3 k4 i0 1 2 3 4 5 Pi 0.05 0.15 0.15 0.10 0.10 qi 0.05 0.10 0.05 0.10 0.05 0.10 d4 K5 d5

Write a method that takes a binary tree and an array of items as input, and it returns a binary search tree (BST) as output. The binary tree contains n nodes and doesnt need to be balanced. The array contains n unique items which are mutually comparable. The method should build a binary search tree of n nodes. The binary search tree should contain

Given two binary search trees, return elements of both binary search trees in sorted form. 1) complete the function Merge() which takes roots of both binary search trees as its parameter and returns the binary search tree in a sorted order that merges the node values of both binary search trees 2) complete the function Main() that creates two

1 2 1 3 1 LO 5 2 3 2 4 1 1.0 5 4 2 7 7 9 9

a. Depict the array in an array-based implementation for the binary search tree in Figure 15-14 a. Assume that tree items are strings. b. Show the effect of each of the following sequential operations on the array in part a of this exercise. bst.add("Doug"); bst.add("Nancy"); bst.add("Bob"); bst.add("Sarah"); c. Repeat parts a and b of this

Many different binary search trees can contain the same data, however. For example, in addition to the tree in Figure 1513, each tree in Figure 1514 is a valid binary search tree for the names Alan, Bob, Elisa, Jane, Nancy, Tom, and Wendy. Although these trees have different shapes, each one satis fies the requirements of a binary search tree.

13. (10 Points) Given the following Binary Search Tree, 10 14 15 21 35 10 13a. (5 Points) Draw the Binary Search tree after deleting the value 2. 13b. (5 Points) Draw the Binary Search tree after deleting the value 15.

a) Insert into an initially empty binary search tree items with the following keys (in this order): 3,22,54,1,7. b) How many different Binary Search Trees are possible using the above sequence? (3,22,54,1,7). c) The inorder traversal of the Binary Search Tree at a) is 1,3,7,22,54. Build a different Binary Search Tree whose inorder traversal

Create one Binary Search Tree and delete nodes from it. Specifically, you have to draw diagrammatically the trees that appear from the following(just the final form): a)Draw the Binary Search Tree using the following data entered(once) in this order:27,59,21,38,54,63,8,70,15 b)Draw the Binary Search Tree which appears if the value 59 is deleted

a. Given the following insert sequence, draw the resulted binary search tree 16, 34, 5, 25, 2, 9, 12, 43, 19 b. Delete element 34 from the binary search tree constructed above, draw the resulted binary search tree

What is the smallest possible interval where f(x) can have a zero? f(5) = 7 f'(5) = 1/2 f is increasing f is concave down

Write a program in Java Merge Sort decreasing order.

Can you implement merge sort without recursion? Explain your answer. Why is the time complexity of a merge sort always O(n log n)?

Consider the following relation R with 12 blocks of data stored on the disk(B(R) 12) 16,8,14,4,1,9,27,12,3,19,15,6,29,7,50,0,18,6,10,30,9,25,8,5,7,20,12.2,13,16 ,88,9,19,14,43,17 Each block holds 3 values and there are 4 blocks of memory available for the operation (M 4). Use Twopass multiway merge sort algorithm to sort the blocks above.

6. 17pts Given a properly implemented merge sort algorithm and the list 5, 3, 7, 8, 9, 11 is it possible for the merge sort algorithm to eventually have to merge the following two lists Why or why not 5, 3, 7 8, 9, 11 7. 20pts Draw a diagram that illustrates how the merge sort algorithm would sort this list. Draw the contents of the list after

What is the worst case time complexity for merge sort when the input given is completely random?

Write down the recurrence relation for worst case of merge sort algorithm. Also write down the Loop Invariant of Merge Procedure in Merge sort algorithm.

1. Given the following list After merge method 1 2 107, 22, 53, 85, 211, 16, 97, 6, 32 a. Use merge sort to fill the following table that shows the value of first and last arguments in calling the quick sort method and the content of the list after each merging Content of list 0 1 2 3 4 5 6 7 8 first last b. Use number of elements in the merge

Write two java programs (sequential and parallel) to implement merge sort that do the following Create a class MergeSortArraySeq that develops a merge sort algorithm to sort an array of integer numbers in sequential. MergeSortArrayThread that will develop merge sort algorithm to sort an array of integer numbers in parallel. Methods to initialize

SOLVE IN PYTHON

5. There are many strategies in sorting elements in an array. Bubble sort, merge sort and quick sort are three common approaches. Given an array of eight (8) integers and algorithm below 3 8 4 10 1 5 6 9 firstHalf mergeSort (firstHalf) secondHalf mergeSort (secondHalf) list merge (firstHalf, secondHalf) Draw the conceptual diagram (workflow)

5. There are many strategies in sorting elements in an array. Bubble sort, merge sort and quick sort are three common approaches. Given an array of eight (8) integers and algorithm below 3 8 4 10 1 5 6 9 firstHalf mergeSort (firstHalf) secondHalf mergeSort (secondHalf) list merge (firstHalf, secondHalf) Draw the conceptual diagram (workflow)

Write down the merge sort algorithm for this input

7) Merge sort and merge algorithm and time complexity analysis 5 3 1 11 29 2

A variation of merge sort involves calling a bubble or insertion sort when we reduce to an array size that is small say less than 50. Rewrite the merge sort so that if the array partition we are looking at has a size less than 50, call insertion sort on that partition. Then using System.nanotime for a rough estimate and using random Integer

N 1000 10000 100000 1000000 10000000 Merge Sort Modified Merge Sort Bubble Sort Insertion Sort

Given the following array 4 90, 61, 10, 52, 23, 34, 24, 24 (a) The merge sort algorithm is applied to sort the array A in ascending order. Show the array contents after each pass. (4 Marks) (b) The standard quicksort algorithm is applied to sort the array A in ascending order. Show the array contents after each pass. (6 Marks) (c) Merge sort and

Merge sort runs in loglinear time, e, O(n logn) comparisons. Mergeinsertion sort and other hybrid merge sort approaches use quadratic 0(n) sorts to sort ublists, but we can still refer to the overall hybrid algorithm as loglinear. Why

What is the full implementation of merge-insertion sort (combination of insertion sort and merge sort algorithms) in c++ (not Pseudocode)? explain it in details of how it's more efficient than the normal merge sort algorithm in terms of time complexity and number of comparison etc?

For the following array A 6, 2, 8, 10, 3, 1, 7,Roihn shares part of his answer for applying merge sort to the given array Solution 1. Division 6, 2, 8, 10 3, 1, 7 2. Division 6, 2 8, 10 3, 1, 7 3. Division 6 2 8, 10 3, 1,7 4. Merge 2,6 8, 10 3, 1,7 5. Division Merge Last. Merge 1, 2, 3, 6, 7, 8, 10 Now please simulate merge sort for the following

Sort Array A using 1 Merge Sort 2 Quick Sort 42 23 74 11 65 58 94 When is the (bestcase) and (worstcase) for 1 Merge Sort 2 Quick Sort 36 6 99 87

4) Consider the list 21 11 23 16 13 22 18 a) 5 Use bubble sort to sort the list. Show each swap. How many swaps took place b) 7 Explain how merge sort works in your own words. Use merge sort to sort the list. Show each step. c) 7 Explain how insertion sort works in your own words. Use insertion sort to sort the list. Show each step.

Identify a problem that can efficiently be solved with merge sort. Implement the merge sort algorithm . Determine and summarize the algorithmic runtime of the merge sort algorithm. As you saw from your readings and exercises, Merge Sort is based upon the idea of divideandconquer. If implemented correctly, your merge sort algorithm should have a

Consider a variation of Merge sort called 4way Merge sort. Instead of splitting the array into two parts like Merge sort, 4way Merge sort splits the array into four parts. 4way Merge divides the input array into fourths, calls itself for each fourth and then merges the four sorted fourths. a) Give pseudocode for 4way Merge sort. b) State a

Implement merge sort that merges two list and then sort them. public class MySortedList{ public void merge(ArrayList myList){ // Implement merge sort method } }

Use the merge sort to sort the above array. Please show the substeps of the merge sort using recursion trees. 81 22 48 13 69 93 14 45 58 79 72

Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements recursively, hence consuming less time. Merge sort runs in O(n*log n) time in all the cases. Two functions are involved in this algorithm. The merge() function is used for the merging two halves and the mergesort() function recursively calls itself to divide the

There is limited parallelism in merge sort because the merge operation is naturally sequential. Question Rewrite merge to make it suitable to execute with P processors. (Hint it is one of these cases where you may have to increase complexity slightly.) Question What are the work and critical path of the merge algorithm you created Question If you

Let A be a random permutation of [1,2,3,4,5,6,7,8]. Determine the probability that exactly 12 comparisons are required by Merge Sort to sort the input array A. Clearly and carefully justify your answer.

Using merge sort to sort an array of size n, then use binary search to find 10 elements. Using merge sort to sort an array of size n, then use binary search to find n^2 elements. Using merge sort to sort an array of size n, then use binary search to find (1/2)n elements. Using merge sort to sort an array of size n, then run sequential search on it.

2. Explain the procedure (step by step) to calculate the time complexity of merge sort using master method. (5 Points) Enter your answer

Use numbers to track every step of the order of merge sort recursion(not the sorting) of an example array sized at least 10. (Hint Merge sort is LRM)

Here we will study what happens to Merge Sort if we divide the given problem into more than two sub problems. Consider the modification to the Merge Sort procedure that at each step of the recursion, divides the problem of size n into n sub problems each of size n. In this problem you will analyze the running time of this version of Merge Sort.

Implement functions that return the sorted array for the following Use rand() 100 to store random values to an array of n Implementation of Merge Sort Implementation of Quick Sort

If a modified merge sort method splits the input array into three equalsized subarrays, what is the recurrence relation T(n) of this merge sort method

6. (15 points) Explain why Dynamic Programming does not apply to the Merge sort algorithm. Draw the recursion tree of the Merge sort to support your answer.

4. In class, we have considered 1dimensional rod cutting problem. For this question we consider a (wo dimensional version of this protilemi. Assume, you are giveri a rexilarggular piexe of sheen sheel with dimenzion X x Y, where X and I are poeitive integers you are also given a lizt of products that can be made using steel sheets. For each

The formulation of the problem is as follows Given a rod of length n inches and a table of prices p, for i 1, 2, ...,n, determine the maximum revenue r obtainable by cutting up the rod and selling the pieces. Note that if the price pn for a rod of length n is large enough, an optimal solution may require no cutting at all. a) Formulate this

Pi (30 points) A Variant of Rod cutting. Recall in the rod cutting problem, were given a rod of length n along with an array pii

Input 20 1 5 8 9 10 17 17 20 24 30 31 32 33 34 35 36 37 38 39 40 2 3 5 Expected output 50

A rod cutting company streling corporation will cut rods of specific lengths only. Given a list of lengths by which this company will make rods, a rod of length n and list of prices of each piece of rod that shall be cut by the company, write an algorithm and implement it using top down dynamic programming to find maximum revenue that shall be

you are required to implement one of the following algorithms, depending the result of your registration 48984 mod 3: If the result is 0, you will have to implement both the recursive and bottom up version of rod cutting algorithm If the result is 1, you will have to implement both the recursive and iterative version of LCS If the rault is 2, you

You are given a single positive integer n, 2,For n7, the best two options are Sum 734 7322 The computational complexity of your program should be O(n). Use dynamic programming to achieve that complexity. Examples INPUT 2 3 STI 4 10 5 01 6 7 Product 1234 12322 Hint OUTPUT 1 2 4 6 9 12 Consider the similarities between this problem for input n and

Write a program cmsc401.java that reads the size of the rod and cutting points in the format below The size of the rod, N, in the first line. N2, N 1, M 0 and,You are given a rod that is N inches long and a set of M cutting points on the rod. You will need to cut the rod from these M points. You can perform the cuts in any order of these points.

Assuming a rod length of 6, provide a p array, such that the optimal cutting solution requires exactly two cuts. Your p array must make sense, containing only positive numbers and be monotonically increasing (i.e., pi1 pi for all i). Consider an extension to the rod cutting problem in which every cut incurs a cost, and the cost varies based on

a) What type of implementation is used in the algorithm given topdown with memoization or bottomup Hint the notation K(w) used in the algorithm should NOT be interpreted as a function call, instead it should be treated as Kw, i.e., accessing table element using index w b) Rewrite the algorithm using recursive function without memoization. c)

Given a rod of length n inches and an array which contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 40 (by cutting the rod in

(10 points) In the rod cutting problem, we are given as input, P1.P2, Pn, where pi denotes the price of a rodpiece of length i. We are interested in cutting a given rod of length n into pieces of integer lengths in order to maximize the revenue here we are only interested in finding the maximum revenue. Cutting is free. Let r, denote the maximum

a) Write a program that prompts the user to input the prices for rod lengths from 1 to 10. b) Prompt the user for an input rod length (it must be between 1 and 10). Lets call this variable n. c) Output the maximum revenue for a rod of length n (i.e. r). d) Output the cuts the yield the maximum revenue. Example inputs prices 1, 5, 8, 9, 10, 17, 17,

Write a dynamic programming code for the Rod Cutting problem. Use the prices given to test your program: Given the prices p(i) of rods with length i = 1,2, .., n. We want to find the best cutting strategy of a rod with length l < n that maximizes the revenue. Recurrence formula : r(l) = max (p(i) + r(l i)) for 1 < i < n; r(0) = 0 We can have

A)If you have the best solution for a rod of length x and you want to find the best solution for a rod of length x+1, how many values do you need to examine and what are they? B)Assume the sorting algorithm that sorts in linear time. Write the algorithm in pseudo code to find a fast algorithm that goes digit by digit an x digit binary number that

Modified Rod Cutting Problem. Given n pieces of rod with lengths 11,12,...n Recursively combine two adjacent pieces to have a rod of length n at the end. When combining the two pieces of length x and y, the revenue is actually x b. Write a dynamic programming algorithm that gives us the maximum revenue and explaining your running time. ex given

What is the time complexity of the following implementations of the rod cutting problem Explain and identify how many recursions or iterations occurred when n 4 on the following three algorithms. 1) CUTROD(p.n) 1 if n 0 3900 4 for i1 to n 2) 5 6 return q return 0 1 2 MEMOIZEDCUTRODAUX(p.n.r) if rn 20 return rn q max(q. pi CUTROD(p.ni)) 3 if n

Can we adapt dynamic programming steps to implement the merge sort algorithm? If yes, explain and show five easy steps of dynamic programming. If no, explain and what five steps are not applicable to merge sort? Justify your answer. Can we adapt dynamic programming steps to solve a 2x2x2 Rubik cube? If yes, explain and show five easy steps of

a) State the rod cutting problem. Explain, with reasoning, if you can solve the problem using Greedy algorithm Brute force approach Also explain any limitation of these approaches. b) Suggest a way to overcome the limitations you have identified in (a). You do not need to write any algorithm. You need to simply explain what algorithm paradigm

Rod Cutting Problem Given a rod of length 20 meters and an array of prices that includes prices of all pieces of sizes (See Table 1). Determine the maximum revenue obtainable by cutting up the rod and selling the pieces. Table 1 Price Table Lengths 11 12 13 14 15 Lengths 1m 2m 3m 4m 5m Prices 1 5 Does this problem have an optimal substructure If

a. Solve the rodcutting problem for the attached set of prices. (p1, p2, p3, p4, p5, p6, p7) (1, 3, 4, 6, 8, 12, 15). Show the final r structure and s structure. b. Someone solved an instance of the rodcutting problem the following s array. (s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11, s12) (1, 2, 1, 2, 5, 2, 5, 5, 4, 9, 5, 8). Using only the s

We are given a non-negative integer n and an array P[1..n] of prices. We wish to cut the rod into a number of pieces whose lengths sum to n in order to sell the pieces. We are paid P[i] for selling a piece of length i. Our goal is to find the maximum total selling price for our pieces of rod. Consider a variant of the problem where we can cut the

In the rod cutting example we discussed in class, given a rod of length n and a table pi of prices for i =1, 2, ..., n, we used rn to represent the optimal revenue obtainable given a rod of length n. We express rn using the recurrence: rn = max{pi + rni : 1 i n}. Consider a variant of this problem where a fixed cost c is associated with making

Consider a rod of length n inches and an array of prices P1...n, where Pi denotes the price of any i inches long piece of rod. Now suppose we have to pay a cost of 1 per cut. Thus, for example, if we cut the rod into k pieces of lengths ni, n2,..., nk, this means that we made k 1 cuts, which gives their final selling price as Pn Pnk (k 1). Let

Assume that a company buys long steel rods and cuts them into shorter rods for sale to its customers. If each cut is free, and rods of different lengths can be sold for different amounts, determine how to best cut the original rods to maximize the revenue. The prices of rods with different lengths are listed in the following table Length i 1 2 3 5

Show the recursive equation for Shortest paths (BellmanFord, FloydWarshall) Shortest paths within a budget Knapsack (unbounded) Rod cutting problem Explain the decomposition of a problem into subproblems, and how the solution is obtained from the subproblem solutions that is captured by the recursive equiation.

Given a rod of length n inches and an array of prices (pi, for i = 1...n) of all pieces of size smaller than or equal to n, that is pi is the price for a piece of length i inches. The Rod Cutting problem is to determine the maximum value obtainable by cutting up the rod and selling the pieces. a) Describe a greedy algorithm to determine a set of

Length 1 2 3 Price 1 3 3 Consider the following lengthprice table 6 7 8 5 6 6 9 10 4 5 For this lengthprice table, diagram the OPT table computed by the dynamic programming algorithm we saw in class. In particular, for each entry table j 0, 1, ..., 8, OPTj should store the maximum revenue that can be obtained from cutting a rod of length j in

Consider a rod cutting problem with the following table of prices length 1 2 3 price 357 1. Demonstrate the topdown recursive algorithm without memoization for a rod of length 3. 2. Demonstrate the topdown recursive algorithm with memoization for a rod of length 3. 3. Demonstrate the bottomup dynamic programming algorithm for a rod of length 3. 4.

You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights (20, 30, 40, 70) and values (70, 80, 90, 200). What is the maximum value of the items you can carry using the 01 knapsack (6 points),length 1 2 3 4 5 6 7 8 You are given the following prices of rod cutting. price 2 9 10 5 6 9 9 17 17 18 20 22 Longly

3. (10 pts) Assume n is a power of 2, that is, n 2P for some natural number p 0. Solve the recurrence T(n) 3T(n2) n, T(1) 0 4. (10 pts) The recursive cutRod algorithm below takes an array of prices p and a rod length n. It determines how to cut the rod to maximize the total value of the pieces. 1 2 3 4 5 6 1 2 3 4 5 5. (10 pts) Here is a

(a) Describe a reduction of the change-making problem (finding the least number of coins to make change for a given value) into a rod cutting problem. (b) Prove the loop invariant for bubble sort: after i iterations the indices n-1 through n-i will contain the i maximal values from the original array.

Suppose you are the manager of a company that manufactures metal rods of variable lengths. You have a rod of length L, and you want to cut it into smaller rods of lengths 1, 2, ..., L (That is, the cut pieces of rods always have integral length). Each rod of length i has a certain price vi in the market. In the rod cutting problem, you are

1. Use a greedy Heuristic to determine the best number of coins to give back for A12, and denominations of 1, 3, 10 2. Show the resulting matrix when using Dynamic Programming on the previous problem. 3. Given the following prices length(i) 1 2 3 4 5 6 price p 2 3 7 9 11 13 Use the rod cutting algorithm to determine the r and s arrays Find the

define an array s0..n such that the jh element of s gives the best cut for a steal rod of length j. Given the following s array, indicate how a steal rod of length 15 should be cut In the dynamic programming solution to Rod Cutting problem, we to maximize revenue. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 MIS s 0,1, 1, 1, 4, 4, 3, 2, 8, 3, 8, 5, 7, 7,4,5

Design a dynamic programming algorithm for the following problem. A rod has length n and a segment of length i costs pi dollars. The costs pi are known for all i 1,...,n. The problem is to determine what is the maximum revenue a company can obtain by cutting the rod and selling the segments obtained after the cutting For the dynamic programming

a. 10 points Complete the total revenue and split array of the rod cutting algorithm. You must show your work. Price Revenue 2 4 5 8 Split b. 2 points What are the cuts for a rod of length 3 C. 2 points What are the cuts for a rod of length 7 9 10 11