1. Consider the above red-black tree, insert the following numbers to the red-black tree indepen-dently. Show your work step by step for each insertion.
(a) Insert 3.
(b) Insert 19.
(c) Insert 56.
1
Homework 3
CS301
2. Suppose that Algorithmsthere are n items to be transferred from a warehouse A to another warehouse B. Each item i to be transferred has the weight of wi and the value of vi, 1 i n. We will be paid 0:1% of the total value of the load that we transfer by our truck which can carry at most W tons, and we are allowed to make only one trip from warehouse A to warehouse B.
(a) Suggest an e cient dynamic programming algorithm to decide which items we should carry so that we make the most money.
(b) What is the complexity of your algorithm?
(c) By creating dynamic programming table for the following items and their value nd best solution for transporting items. (Assume W is 5 tons)
Item
Weight
Value
1
2
12
2
1
10
3
3
20
4
2
15
2
