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
equired filename. The PDF file could be generated using LATEX(recommended), Microsoft Word (saved as PDF, not the
.docx file), or other edito
tools. The submission must be typed. Handwritten submissions are not accepted.
Due Fe
uary 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
co
ectness, but also on clarity. Answers that are technically co
ect that are hard to understand will not receive full marks.
Mark values for each question are contained in the [square
ackets]. Your submitted file does not need to include
epeat
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. a
ay (like the Java a
ay)
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 (a
ay), 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 e
or.
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 bette
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 a
itrarily
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
ule about moving a puck into/out of the buffer line is that the puck can only turn left as indicated by the turning
a
ows 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 a
ay, and returns K, the largest
number of the pucks that can be moved out in the exact order of 1, 2, . . . , K. If the a
ay 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 a
ay 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 co
ect. 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 co
ect. 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 co
ectness of the code in A1Q2.java (passed test cases in
auto-testing), and 50% based on the written answers provided in the PDF file.