Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Part A: The Warmup
0. [5 marks] Do at least 1 of the drills on cuLearn from Lec 5, 6, or 7.
(Usually this is just part of your overall grade and you can do them at your leisure, but I want you to do at least one per assignment to move you towards the 10 required by end-of-semester.)
Part B: The Interface
As with assignment 1, the file Part0.java in the zip file actually does something (although it’s a different something than assignment 1). You can use its doIt(x) method as a starting point for your solutions. Compile it. Run it. Test out the various ways of inputting and outputting data. You should not need to modify Part0.java, it is a template.
You can download some sample input and output files for each question as a zip file (a2-io.zip). If you find that a particular question is unclear, you can possibly clarify it by looking at the sample files for that question. Note that these are very limited tests; you can and should add to them to test your code more thoroughly as the server tests are much more extensive.
1. [10 marks] Read the input one line at a time and output every x’th line, starting with line 0, where x>0 is a parameter to the doIt method. To get full points, try to use as little extra space and time as possible.
2. [10 marks] Read the input one line at a time and output every x’th line from the end, starting with the last line, where x>0 is a parameter to the doIt method. To get full points, try to use as little extra space and time as possible.
3. [10 marks] Read the input one line at a time, and output the last x lines in reverse order, where x>=0 is a parameter to the doIt method. If there are fewer than x lines, print the n < x existing lines in reverse. (The lines themselves are forwards, their order is reversed. See the sample input/output to clarify if you need it.) To get full points, try to use as little extra space and time as possible.
Part C: The Implementation
Files Provided
The starter code contains MyStack and MyDeque interfaces, which are modified Stack and Deque interfaces described below. Part C involves you completing implementations of these interfaces, MyFastStack and MyFastDeque, in the files MyFastStack.java and MyFastDeque.java, respectively. These are described in more detail in Parts 4 and 5 below.
Interface Semantics
Both MyStack and MyDeque represent a sequence of items where any neighbouring duplicates have (both) been removed. For example, the original sequence [a,b,c,c,b,d] would shrink to just [a,d] (since once the neighbouring c,c are removed, b and b become neighbouring duplicates and are also removed.)
As another example, the sequence [a,b,c,c,c,b,d] would shrink to [a,b,c,b,d] since once the first neighbours c,c are removed, a third c remains.
The individual elements are atomic (i.e. indivisible), so [ab,ab] shrinks to [], and [ba,ab] does not shrink at all.
Finally, if you have the sequence [a,b,c,c,b,a], this would shrink to the empty sequence [].
Your Tasks
4. [20 marks] For the MyStack interface, we only wish to access the most recently added element in this “shrunken” sequence (the sequence with pairs of duplicates removed). That is, we want 3 methods:
● push(x) – add non-null x to the sequence
● pop() – remove the most recent non-consecutive duplicate (null if no such element exists)
● size() – return the length of the shrunken sequence
For example, starting from an empty MyStack, the operations
● After push(a),push(b),push(b)
○ size() would return 1 and pop() would return a because the constructed sequence [a,b,b] shrinks to [a]
● After push(a),push(b),push(b),push(b)
○ size() would return 2 and pop() would return b because the constructed sequence [a,b,b,b] shrinks to [a,b]. Another pop() would return a.
● After push(a),push(a)
○ size() would return 0 and pop() would return null, since no element exists
● After push(a), push(b), push(c), push(c), push(b)
○ size() would return 1 and pop() would return a because the constructed sequence [a,b,c,c,b] shrinks to [a].
Your task is to implement the push(x), pop(), and size() methods in MyFastStack such that all three operations run in O(1) time. You may use JCF ADTs such as ArrayLists in your solutions.
5. [25 marks] For the MyDeque interface, we wish to access the shrunken sequence from either end (for both adding and removing). That is, we want the 5 methods:
● addFirst(x) – add x to the beginning of the sequence
● addLast(x) – add non-null x to the end of the sequence
● removeLast() – remove the “right-most” non-consecutive duplicate (null if no such element exists)
● removeFirst() – remove the “left-most” non-consecutive duplicate (null if no such element exists)
● size() – return the length of the shrunken sequence
For example, starting from an empty MyDeque, the operations
● After addFirst(a),addFirst(b),addFirst(b)
○ size() would return 1 and removeLast() would return a because the constructed sequence [b,b,a] shrinks to [a]
● After addLast(b),addFirst(b),addLast(b),addFirst(a)
○ size() would return 2 and removeFirst() would return a because the constructed sequence [a,b,b,b] shrinks to [a,b]. Another removeFirst() would return b.
● After addFirst(a),addLast(a)
○ size() would return 0 and removeFirst() would return null, since no element exists
Your task for this question is to implement all 5 operations in O(1) time per operation in MyFastDeque. You may use JCF ADTs such as ArrayLists in your solutions.