Problem 1: (50 points) Stacks Two stacks of positive integers are needed, one containing elements with values less than or equal to 100 and the other containing elements with values larger than 100. The total number of elements in the small-value stack and the large-value stack combined is not more than 20 at any time, but we cannot predict how many are in each stack. (All of the elements could be in the small-value stack, they could be evenly divided, both stacks could be empty, and so on.) Can you think of a way to implement both stacks in one array of size 20? Write briefly how you would implement this. (You can add this into comments in the .java file or as a separate txt file or .docx file) Implement the Array which incorporates both the stacks; it should store the new item into the correct stack according to its value (compared to 100) and should have pop1 and pop2 functions based on which stack pops the element. Calculate the performance (Big O) notation for the Push operation(s) you just implemented and pop(s) operation you just implemented(Add this into comments or txt file or docx file you created.)

Problem 2: (15 points) Recursion Recursive solution to raising a number to a power. Implement the recursive approach in JAVA to raising a number to a power. Write a recursive power function and the main routine to test it. So 28 = 2 * 27 = 2 * 2 * 26 and so on. So x^Y is x multiplied by itself y times.

Problem 3: ( 35 points ) Recursion Knapsack problem Write a program that solves the knapsack problem recursively in JAVA for an arbitrary knapsack capacity and series of weights. Assume the weights are sorted in an array. Hint: The arguments to the knapsack function are target weight and the array index where the remaining items start. The knapsack problem in its simplest form involves trying to fit items of different weights into a knapsack so that the knapsack ends up with a specified total weight. You need to fit in all items. For example, if you want your knapsack to weigh exactly 20 pounds and you have five items with weights of 11,8,7,6 and 5 pounds. In this case only combination that works is 8, 7 and 5 pounds.