Project #157195 - Data Structures

Computer Tutors

Subject Computer
Due By (Pacific Time) 12/02/2016 07:00 pm

 

1) Binary Search Tree Please implement the binary search tree and finish the following operations

(1)  Search

(2)  Insert

(3)  Delete

(4)  inorderTraversal (print the tree)

 

Please use the following operation as your tester.

insert(50);

insert (40);

insert (80);

insert (20);

insert (45);

insert (60);

insert (90);

insert (55);

insert (65);

inorderTraversal();

search(20);     // return Boolean to indicate whether it is found

delete(20);

inorderTraversal();

search(80);

delete(80);

inorderTraversal();

 

For the next problem I will need detail explanation of everything you do, I will have to present this particular problem in front of the class and professor.

 

2)

Imagine an array of n items from which you can choose. You will place the items you choose into a knapsack of size k. Each item has a size and a value. Of course, you cannot take more items than you have space for in the knapsack. Your goal is to maximize the total value of the items you take.

a.     Design a recursive algorithm maxKnapsack to solve this knapsack problem. The parameters to the algorithm are the knapsack, the array of items, and the position within the array of the next item to consider. The algorithm chooses the items for the knapsack and returns a knapsack containing the chosen items. A knapsack can report its size, its contents, the value of its contents, and the size of its contents.

Hint: if any items in the array have not yet been considered retrieve the next item in the array. You can either ignore the item or, if it fits, put it in the knapsack. To decide, make a recursive call for each of these two cases. Compare the knapsacks returned by these calls to see which one has the most valuable contents. Then return that knapsack.

b.     Write the classes Knapsack and KnapsackItem. Then write a program that defines the method maxKnapsack. The program should read the size of the knapsack and then the size, value and name of each available item. Here is some sample input data for a knapsack of size 10:

                            

 

 

Size                             Value                          Name

                                    1                                  50000                          rare coin

                                    2                                  7000                            small gold coin

                                    4                                  10000                          packet of stamps

                                    4                                  11000                          pearl necklace

                                    5                                  12000                          silver bar

                                    10                                60000                          painting

After displaying the items, call maxKnapsack. Then display the chosen items, their values and their total value.

For Both questions please answer the following

Test code:

 

 

 

Running results:

 

 

Comments:……

___This program can run successfully, with no errors and passed all test cases.

___ This program can compile and run, but it cannot pass all test cases.

___ This program cannot compile, and it has some syntax errors.

___ This program is incomplete

Other comments: _____________________________________________________

 

 

 

 

 

 

 

 

TutorRating
pallavi

out of 1971 reviews
amosmm

out of 766 reviews
PhyzKyd

out of 1164 reviews
rajdeep77

out of 721 reviews
sctys

out of 1600 reviews
sharadgreen

out of 770 reviews
topnotcher

out of 766 reviews
XXXIAO

out of 680 reviews