Solve all the following problems and make sure to show work and provide explanat

Solve all the following problems and make sure to show work and provide explanat

Solve all the following problems and make sure to show work and provide explanations. Thank you!
Problem 1: Choosing an appropriate list implementation
9 points total; 3 points each part; individual-only
In lecture, we considered two different implementations of the list ADT: ArrayList and LLList. For each of the following applications, decide which list implementation would be better for that particular application. Your should consider both time efficiency and space efficiency, and you should assume that both implementations have an associated iterator like the LLListIterator that we discussed in lecture. Explain your answers.
You need to keep track of the orders placed to your online store. At the start of each month, you start with an empty list; as orders are made, you add them to the list. The number of orders varies greatly from month to month. You regularly display the list of orders, starting with the most recent order and working backwards towards the least recent one.
The ERC wants you to maintain its weekly list of workshops. The number of workshops is fairly consistent from week to week. The workshops will be added to the list in chrological order, and they will also be displayed in that order.
You are maintaining a list of information about all of the courses that are being offered in the Fall. Each course has an id number between 1 and 5000, and you decide to use that id number as the position of the course’s record in the list. Once the list of courses is created, there are very few additions or removals. However, you need to frequently access the items in the list during the course registration period. Every time that a student registers for a course, you need to access that course’s record in the list so that you can increment the course’s count of enrolled students.Problem 2: Switching from one list implementation to another
10 points total; individual-onlyThe following method takes an instance of our ArrayList class from lecture, and it “converts” it into an LLList object that contains the same values. More precisely, it creates and returns an LLList that contains the same values at the same positions as the original ArrayList.public static LLList convert_AtoL(ArrayList vals) {
LLList converted = new LLList();
for (int i = vals.length() – 1; i >= 0; i–) {
Object item = vals.getItem(i);
converted.addItem(item, 0);
}
return converted;
}
Note that the original list is not altered.In order to be as efficient as possible, the method processes the original ArrayList in reverse order: beginning with the last item and working backwards towards the first item. To see why it does so, begin by determining the running time of the above method as a function of the length n of the original list. Don’t forget to take into account the time efficiency of the underlying list operations, getItem() and addItem(). Use big-O notation, and explain your answer briefly.
Now let’s consider what the time efficiency would be if the method processed the original list from front to rear, as we usually do:public static LLList convert_AtoL_v2(ArrayList vals) {
LLList converted = new LLList();
for (int i = 0; i < vals.length(); i++) { // note the changes! Object item = vals.getItem(i); converted.addItem(item, i); // note the change! } return converted; } What is the running time of this version of the method as a function of the length n of the original list? Use big-O notation, and explain your answer briefly. How does it compare to the efficiency of the original version of the method? Write a method called convert_LtoA that performs the opposite “conversion”: taking an instance of our LLList class from lecture, and “converting” it into an ArrayList object that contains the same values. More precisely, it should create and return an ArrayList that contains the same values at the same positions as the original LLList.Make your new method as efficient as possible. You should assume that this method is client code that does not have direct access to the fields of either object. In addition, it should not modify the original list in any way.Important: Your method should not use an additional array or an additional instance of one of our collection classes. Instead, it should limit itself to: the LLList that is passed in, the ArrayList that is being created, and (optionally) one of the iterators associated with our LLList class, as discussed in lecture.Note: In the ps7.zip file that you will download for Part II, we have included a file called Problem2.java that contains the original methods listed above and a main method with some preliminary test code. You are welcome to use that file to test the correctness of your convert_LtoA method, although we encourage you to convince yourself of its correctness before you test it in VS Code. What is the running time of your convert_LtoA method? Use big-O notation, and explain your answer briefly. Problem 3: Working with stacks and queues 8 points total; 4 points each part; individual-onlyWrite a method doubleAllStack(Stack stack, Object item) that takes a stack and an item, and that doubles – i.e., adds an extra copy – of all occurrences of that item in the stack. After the doubling, the original items should still be in the same order with respect to each other. For example, if you have a stack that contains (from top to bottom) {5, 2, 7, 2, 10}, if you use the method to double all occurrences of 2, the resulting stack should contain (from top to bottom) {5, 2, 2, 7, 2, 2, 10}.Important guidelines:Your method may use either another stack or a queue to assist it. It may not use an array, linked list, or other data structure. When choosing between a stack or a queue, choose the one that leads to the more efficient implementation.
You should assume that the method does not have access to the internals of the collection objects, and thus you can only interact with them using the methods in the interfaces that we discussed in lecture.
Although you aren’t writing this method as part of a class, you should use appropriate Java syntax. The methods should be static and should not return a value.
Write a method doubleAllQueue(Queue queue, Object item) that takes a queue and an item, and that doubles – i.e., adds an extra copy – of all occurrences of that item in the queue. After the doublings, the original items should still be in the same order with respect to each other. For example, if you have a queue that contains (from front to rear) {5, 2, 7, 2, 10} and you use the method to double all occurrences of 2, the resulting queue should contain (from front to rear) {5, 2, 2, 7, 2, 2, 10}. The same guidelines that we specified for doubleAllStack() also apply here.
SuggestionWe have not given you a Java file for this problem, but we strongly recommend writing a program to test your methods before you copy them into your ps7_partI file. All of the necessary classes can be found in the ps7.zip file that you will download for Part II.
Problem 4: Binary tree basics
11 points total; individual-only
We will complete the material needed for this problem during the week of April 10.
Consider the following binary tree, in which the nodes have the specified integers as keys:
Edit
What is the height of this tree?
How many leaf nodes does it have? How many interior nodes?
If a preorder traversal were used to print the keys, what would the output be?
What would be the output of a postorder traversal?
What would be the output of a level-order traversal?
Is this tree a search tree? Explain briefly why or why not.
Is this tree balanced? Explain briefly why or why not.
Problem 5: Tree traversal puzzles
6 points total; 3 points each part
We will complete the material needed for this problem during the week of April 10.
When a binary tree of characters (which is not a binary search tree) is listed in postorder, the result is IKHAFLMBCQ. Inorder traversal gives IAKHQCFLBM. Construct the tree by editing the diagram we have provided in section 5-1 of ps7_partI.Click on the diagram and then click the Edit link that appears below the diagram.
Edit the diagram. It includes the necessary nodes and edges, but you will need to move them into the appropriate positions and connect them.
When you have completed your edits, click the Save & Close button.
When a binary tree of characters (which is not a binary search tree) is listed in preorder, the result is BAFCIDGEHJ. Inorder traversal gives FCAIBGHEJD. Construct the tree by editing the diagram that have provided in section 5-2 of ps7_partI.
Problem 6: Binary search trees
6 points total; 3 points each part; individual-only
We will complete the material needed for this problem during the week of April 10.
Consider the following tree, which is a binary search tree.
Edit
Show the tree as it will appear if 33 is inserted and then 60 is inserted. Show the resulting tree by editing the diagram that we have provided in section 6-1 of ps7_partI.
Suppose we have the original tree and that 42 is deleted and then 26 is deleted, using the algorithm from the lecture notes. Show the resulting tree by editing the diagram that we have provided in section 6-2 of ps7_partI.
Below is the link to the questions above: https://www.cs.bu.edu/courses/cs112/problem_sets/ps7.html