academicdrift

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

admin

April 19, 2024

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