can you answer this question please
EECS 2011 Z, Winter 2023 – Assignment 1 Remember to write your full name and student number prominently on your submission. To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources (people, print, electronic) outside of the course materials, and the course staff, that you consulted. You must submit a PDF file and Java files (if any) with the required filename. The PDF file could be generated using LATEX(recommended), Microsoft Word (saved as PDF, not the .docx file), or other editor/tools. The submission must be typed. Handwritten submissions are not accepted. Due February 3, 2023, 10:00 PM (on eClass); required file(s): a1sol.pdf, A1Q2.java Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity. Answers that are technically correct that are hard to understand will not receive full marks. Mark values for each question are contained in the [square brackets]. Your submitted file does not need to include/repeat the questions — just write your solutions. The assignment must be completed individually. 1. [10] Consider the following data structures for implementing the List ADT. A. array (like the Java array) B. singly-linked list, with “next” only, and with “head” only. C. singly-linked list, with “next” only, and with “head” and “tail”. D. reverse singly-linked list, with “prev” only, and with “tail” only. E. doubly-linked list with “next” and “prev”, and with “head” and “tail”. F. circular singly-linked list, with “next”only, and with “tail” only. G. circular doubly-linked list, with “next” and “prev”, and with “tail” only. Note: None of the above data structures, except for A (array), keeps a “size” attribute. For the following operations, think about the efficiency of implementations based each of the above data structures. Assume that the operations always receive inputs that don’t cause any error. Operations: (a) Search for an element. (b) Get the middle element, i.e., with the list size being n, return the bn/2c-th element in the list. (c) Insert a new element at the beginning of the list. (d) Insert a new element at the end of the list. (e) Delete an element from the beginning of the list. (f) Delete an element from the end of the list. What to include in your submission (the PDF): for each of the above operations, divide the given data structures (A, B, C, D, E, F, and G) into two categories: “fast” and “slow”. “Fast” means that the operation can always be completed within a constant number of steps, and “slow” means that the number of steps taken by the operation is proportional to the size of the list. Note that it is possible that all data structures fall into the same category. Also, provide a concise justification for each of your categorization. Programming Question The best way to learn a data structure or an algorithm is to code it up. In this assignment, we have a programming exercise for which you will be asked to write some code and submit it. You may also be asked to include a write-up about your code in the PDF file that you submit. Make sure to maintain your academic integrity carefully, and protect your own work. All code submissions will be checked for plagiarism at the end of the term. It is much better to take the hit on a lower mark than risking much worse consequences by committing an academic offence. 2. [10] Consider the game of “Sorting Hockey Pucks” as depicted in the following diagrams (Figure 1 and 2). Initially, a sequence of N hockey pucks are placed at the START area. The pucks are numbered 1, 2, 3, . . . , N but are arbitrarily ordered. The goal of the player is to move the pucks out of the EXIT on the left side in the exact order of 1, 2, 3, . . . , N . However, it might not be possible to move out all N pucks in that exact order. We will write a program to determine K, the largest number of the pucks that can be moved out in the exact order of 1, 2, . . . , K. As you can see in the diagram, there is a BUFFER LINE that you may temporarily move the pucks to. One important rule about moving a puck into/out of the buffer line is that the puck can only turn left as indicated by the turning arrows in the figures. Figure 1: Example of the initial state of a game Figure 2: The final state of the above game example. Download the starter file A1Q2.java, and complete the solve function. It takes an array, and returns K, the largest number of the pucks that can be moved out in the exact order of 1, 2, . . . , K. If the array is of length N , then its elements are guaranteed to be a permutation of the N integers from 1 to N . Your implementation must make use of one or more Stack or Queue objects, and you will explain the usage of them in your PDF file. Read all instructions in the starter code carefully. In particular, make sure to NOT modify the parts of the starter code that says “DO NOT MODIFY” in the comments, e.g., the package declaration “package A1” and the import lines. As an example, for the game shown in Figure 1, the input array would be [4, 5, 2, 1, 3], and the solve function should return 3, according to the final state illustrated in Figure 2. The main function of the starter code includes a few test cases that you may use to test your own code. These test cases are not meant to be exhaustive so passing them does not necessarily mean your program is correct. You’re encouraged to create more test cases to test your program more thoroughly. You may setup the Java project using any programming IDE of your choice such as IntelliJ, Eclipse, VSCode, or Notepad — it doesn’t matter as long as the A2Q2.java file is correct. Be careful: sometimes the IDE automatically inserts lines of code such as the package declaration and imports. Make sure to double-check your code before submission to remove any unnecessary those extra lines since they may cause all test cases to fail in auto-testing. What to include in your submission: • In the PDF file a1sol.pdf, provide a clear description of how your algorithm works. In particular, explain clearly why a stack or a queue is used and how you use it. Your writing for this part should be concise: one or two paragraphs should be enough, and do not exceed one page. • Your A1Q2.java file with the complete implementation your solution. This is the only Java file you submit, i.e., any new class that you add must be included within this file. The marking of this question will be 50% based on the correctness of the code in A1Q2.java (passed test cases in auto-testing), and 50% based on the written answers provided in the PDF file.